构造一个检索系统

1、数学建模（A）构造一个检索系统组号：第三组摘 要 学术论文是我们不可缺少的学习、研究的参考资料。对于怎样将论文的合理地分类管理和快速准确地检索成了一个重要的研究项目。 针对问题要求：怎样科学合理地将论文进行分类并且能够通过关键字快速准确地检索到相应地论文，我们使用不同地检索算法，建立了两个不同地模型。模型一 矩阵模型，通过ASCII 码将字符数字化，同时构造出字符串的ASCII累加值，并利用矩阵记录关键字的相应的ASCII码值序列；根据矩阵维数的大小，能科学有效地把论文分类并且大大提高了检索地速度；建立关键字相关度，按相关度大小进行论文的输出，提高了检索的准确性。 模型二，模拟网页制作中的搜索

2、引擎与信息获取技术建立模型。为了模型的推广，首先对所要查找的文章进行文件预处理，这样就保证输入的关键词能有效的检索到有关的文章。借用向量模型中的求解关键词在文档中的权重计算方法。这样更能快速且准确的搜索到与关键字有关的文章。然后把录入信息库中的文档进行倒序构造。倒排文件构造除了在搜索速度上具有较好的性能以外，维护起来叶比较简单。利用顺序查找法算法进行倒序文件的搜索。最后用加权后的总指标来评定搜索引擎的性能。关 键 词： 符号数字化 矩阵模型 相关度 文件预处理 文档倒序构造 算法 总指标一、问题的重述 根据某次学术会议所收到的150篇学术论文的关键词（key words），将这些论文按照关键字

3、分类，并构造一个检索系统，使得当给出所要查找文献的一组关键词，例如（eigenvalue problem，inverse，solvability）或（risk perceptions，mental models，bias，synergistic risk），即可从上述150篇中找出有关的文章；进一步要求使用的方法应能适用于文献数量更大的。除少量明显错误外，关键词（包括大小写）均原文照录。二、基本假设 1、为了检索地快速有效，我们不再区分大小写字母；2、在有限地论文中，相连的ASCII累加值相等的字符串出现的概率是很小的，即可以忽略不计；3、用户在输入关键词时，我们认为关键词的重要程度和输入顺序

4、同方向变化，即最重要的放在最前面。三、主要变量符号说明为了便于描述问题，我们用一些符号来代替问题中涉及的一些基本变量。其他一些变量将在文中说明。 文章的编号 字符串的ASCII累加值 关键字的相应的ASCII码值序列 第篇论文关键字的总相关度 为信息库中文档的数目 关键词在文档中的权重 两个文档的相似程度 搜索引擎的总指标: 表示对这篇文章进行倒排处理后所得的结果四、问题的分析题目中主要提到检索系统的三个要求：一是将学术论文进行科学合理地分类；二是输入关键字时，能够快速准确地检索到相应地论文；三是所建模型可以大量推广，应用到文献数量更大的情行。我们分析认为，论文科学合理地进行分类，不仅仅是为了

5、管理上的方便，更大程度上是为了提高检索的速度；论文篇数和关键字都比较多，系统能够准确地记录下所有信息，所需要地存储空间也较大。因此，关键字进行数字化，并用一个个矩阵记录下来显得格外重要。一是助于关键字的位置符号化，利于数据管理，关键字与论文的统一，不会与其它论文混淆；二是节省了存储的空间。系统能够准确而不遗漏地将相关地论文检索出来，其输出的信息量也比较大，对于用户来说不易于筛选。因此，建立关键字相关度，并按从大到小排序输出，才能更大地提高准确性。五、模型建立与求解模型一、矩阵模型及相关度(一) 准备工作：为了更好的建立模型一，我们做了如下准备工作：1. 字符处理：为了简化模型，我们将字符a,b

6、,cz不区分大小写重新附上ASCII码值如下： aA1bB2cC3. . . . .zZ26为了便于研究，对于特殊符号，如破折号、罗马数字等，我们统一附值为0。2. 关键字顺序处理：为了给模型带来方便，我们将每一篇论文中的关键字按字符串的个数重新排列如下： 1Drazin inverse，moore-penrose inverse，reverse order law； 2applications ,Nonlinear approximation problems； 3 Hermite element，Wilson element，Carey element，P1 element，Nonnest

7、ed multilevel preconditioning method; 3. ASCII码累加值的定义：字符串的ASCII累加值等于字符串的各个字符的ASCII码值之和。例如，Matlab这个字符串ASCII码值累加值为：。4. 关键字的位置符号化：设第篇论文的关键字的个数为,其中第个关键字的字符串个数为，取，第个关键字的第个字符串计为;例如，第篇论文中，关键字的个数为，第个关键字的字符串个数为,第1个关键字的第2个字符串为，。5. 关键字的数字化：分别计算第篇论文第个关键字的第个字符串的ASCII累加值；并用维向量记录，不足元素记为0。同样以第1篇论文为例，因此，；同理可以计算出，。6、

8、关键字的数字化存储和论文的分类：通过前面的准备工作，我们建立矩阵用来记录第篇论文的关键字的相应的ASCII码值序列：（1）因此，我们很容易得到第1篇论文关键字的字符串相应的ASCII码值序列：同理，我们将篇论文的关键字按照的准备工作的第2步进行处理，并把重新排列后的数据带入（1）式中，分别得到个记录关键字的ASCII码值序列矩阵： 。由于每一篇论文的关键字个数和每个关键字的字符串个数都不可能完全相等，那么记录论文关键字ASCII码值序列矩阵的维数也是不完全相等。它们的维数是由决定的。为了提高以后论文的收索速度，我们按照（）的大小，把论文分成类，并将它们存储到数据库中。7、关键字的收索原理：（1

9、）当用户输入一个关键字时，可能是一个或者多个字符串，计算机立即计算的字符串个数 和每个字符串相应的ASCII累加值 ，并用矩阵临时记录。 （2）计算机检索：利用维数相等原理，提取出维数为的ASCII码值序列矩阵，若存在并且元素之间连续，则可以从数据库中调出第篇论文给以用户筛选。例如，输入order law这一个关键字，则计算机会立刻计算出，此刻会调出维数为的ASCII码值序列矩阵，通过对比，中，第1篇论文符合用户关键字的要求。（二）模型的建立：由于用户输入的关键字可能是一个或若干个，而且每个关键字都可能是一个或若干个字符串。所以，为了评价出关键字收索的准确性和论文输出顺序，我们建立了关键字相关

10、度： （2） 式中 ，、表示和的元素个数。因此，第篇论文符合用户输入的个关键字的总相关度为：（3）最后，计算机计算出每篇论文符合用户的关键字的总相关度。（三）模型的求解：在检索论文时，速度和准确性是相当重要的。利用关键字进行检索时，提高速度的有效方法是：对用户输入的关键字进行快速计算关键字字数和每个关键字的字符串大小，取；根据向量维数大小，要使得，就必须有，因此第类论文就可以排除掉了；如果每一类论文的篇数基本相同，那么收索速度由原来的提高到。而提高收索的准确性方法是：计算机快速计算用户输入的关键字的ASCII累加值序列；再从第 类论文中进行查找，根据上诉模型一的（2）（3）式，可以快速计算出剩

11、下各篇论文符合用户的关键字的总相关度。最后对从大到小进行排序，并从数据库中将标号为的论文按照总相关度的大小进行输出，以供用户筛选。模型二、模拟网页搜索引擎模型1、模型提出的背景：我们知道基本的查询方式可以通过顺序扫描文本的方式来进行，这种查询方式叫作顺序查找或在线查询。在用户查询的时候，直接在文档中进行字符串的匹配。但这种在线分析方法只适用于文档比较小的情况（比如只有几兆），且它的搜索速度比较慢。对于信息库中的文本，另外一种查询的方法是先对文档进行预处理，然后再用索引的基本技术进行搜索。这样会大大提高搜索的速度。本模型提出的索引的基本技术是倒排文件的搜索。2、模型的原理：模型二的建立分为四个步

12、骤：第一：把要搜索的文本进行文本预处理；第二：构造倒排文件：第三：进行倒排文件的搜索；第四：对搜索结果进行筛选。3、模型的准备：（一） 文本预处理 就本题而言不需要对其进行文本预处理，因为本题在检索时给出就是一些关键字，但为了模型的推广我们引入“文本预处理”这个概念。文本预处理就是我们对所给的文章进行一定的处理而得到的由关键词所组成的词汇树。 我们知道不是所有的单词都能等同地表示一个文本的语义。在书面语言中，一些词汇与其他词汇相比能够表达更多的意思。一般来说，名词是最能够表达文档内容的。这样就有必要对文档进行预处理，以决定对哪些词汇建立索引。在对文档进行预处理的过程中，还有一些其他有用的文本操

13、作，比如无用词汇的删除、词干提取技术、词典的生成和文本的压缩等。 文本预处理的过程可以分为如下五个步骤：i. 文本的词法分析：它主要是处理文本中的数字、连接符、标点符号和字符的大小写。词法分析的过程是将字符串（文档中的文本）转换成词条的过程，这些词条可能被用来作为索引词条。因此词法分析的主要目的就是识别文本中的词条。在对英文进行分词的过程中，要对空格分隔符、数字、连字符、标点符号进行处理。（由于假设不区分字符的大小写，因此不需要对字符的大小写进行处理）ii. 无用词汇的删除：它主要是过滤掉那些对于信息获取过程来说区分能力底的词汇。在信息库的文档中太频繁出现的单词将不会成为具有良好区分能力的词汇

14、，即无用词汇。在选择索引词条的时候，这些词条常被过滤掉。一般说来，冠次、介词、连词等都可以算作无用词汇。iii. 词干提取：它主要是去除词缀（前缀和后缀），这样可以允许所获取的文档包含一些查询词条的变换形式。所谓词干是指将词的词缀（前缀和后缀）删除后剩下的部分。因此可以将文档中的词汇用它们的词干来代替。iv. 索引词条/词干的选择：在选择的时候通常按照单词的习惯用法，实际上名词往往要比形容词、副词和动词包含更多的语义；通常我们选择句子中的名词来作为索引词条。对于两个或两个以上的名词我们可以先设置一个阈值，然后计算文本中词汇之间的距离，如果该距离小于阈值，则将这些词汇放在一起构成名词组。v. 构

15、造词条的分类结构，例如词典或者结构抽取，利用它可以进行查询的扩展。（二）倒排文件的构造 所有已知的单词都防在一棵树结构中。在构造倒排索引的时候，对于每个读入的单词，首先在该树结构中查找，如果没有找到，就在该树中加入一个空的词汇出现情况列表；否则将该词汇的新位置加入到树中对应词汇出现情况列表的末尾。在对要加入的文本中的每个单词都处理完以后，该树将被写到磁盘上。 在实际操作中，索引一般被分成两个文件存放。第一个文件顺序存放词汇出现情况列表，第二个文件以字典序存放树中的词汇，还为每个词汇存放一个指向第一个文件中该单词对应的词汇出现情况列表的指针。这样的话，第二个文件由于比较小而可以在搜索的时候放在内

16、存中。倒排索引的例子见下图：2.Nonlinear approximation problems，applications3 11 13 27 37 48文本词汇树（三）倒排文件的搜索 倒排文件的搜索算法一般分成三个步骤：第一：词汇查找：将查询串中的单词和模式分割成独立的部分，短语和近视查询串被分割成单个词汇；第二：查找词汇出现情况：获取与查询串中所有词汇相关的出现情况列表：第三：词汇出现情况的操作：主要是通过对上一步中获取的词汇出现情况的操作实现短语查询。（四）顺序查找法 该查询的一般过程是，给定一个长度为的模式和长度为的文本，在该文本中寻找所有出现模式的位置。我们采用的是算法。 在介绍算法

17、之前，先给出如下函数：当时当此集合不空时其他情况 2.1 其中， 表示当模式中第个字符与文本串中相应字符“失配”时，在模式串中需重新和文本串中该字符进行比较的字符的位置。 假设以指针和分别指示文本串和模式串中待比较的字符（和的初值均为1）。若在匹配的过程中（表示文本串的第个字符，表示模式串的第个字符），则和分别增1，否则退到的位置再比较，若相等，则指针各自增1，否则再退到下一个值的位置，依此类推，直至出现下列两种情况：一种是退到某个值时字符比较相等，此时指针各自增1继续进行匹配；另一种时退到值为零（即模式的第一个字符“失配”），此时需将模式串继续向右滑动一个位置，即从文本串的下一个字符起和模式

18、串重新匹配。（五）借用向量模型 在性两模型中，信息获取系统如果涉及个关键词，则建立维的向量空间，每一维都代表不同的关键此方法，信息库中的文本以及用户的查询都通过该空间中的向量来表示。查询向量中的权重表示对应关键词对于用户来说的重要程度，一般来说权重1表示期望在文档中出现的词条，而0表示不希望出现的词条。而词条的权重一般基于词条在文档中出现的频率。利用多种词条权重的计算方法。定义关键词在文档中的权重如下： （2.2） 其中，为关键词在文档中出现的频率即词频；为信息库中文档的数目；为信息库中包含词条的文档的个数；为文档中所有关键词的个数。（六）搜索引擎的主要指标 搜索引擎的主要指标由响应时间、召回

19、率、相似度。 （1）响应时间：为了说明响应时间，我们引入时间频度和时间复杂度。时间频度指一个算法中的语句执行次数。设为问题的规模，则记为时间频度。若有某个辅助函数,使得当趋近于无穷大时，的极限值为不等于零的常数，则称是的同数量级函数。记作,称 为算法的渐进时间复杂度，简称时间复杂度。时间复杂度反映了响应时间。给定一个长度为的模式和长度为的文本，利用顺序查找法的算法的时间复杂度为。 （2）召回率：利用精度和召回率可以度量所获取的文档在相关性方面是否满足了用户的需求。表2-1给出了在信息获取系统中所获取的文档与用户及整个信息库的关系。其中，表示信息库中文档的数量，为信息库中与用户查询相关的文档，表

20、示信息库中与用户查询不相关的文档，为用户该此查询所获取的文档，而为信息库中在该次查询中未被获取的文档。表2-1 相关文档的集合定义文档集合相关不相关所获取的文档集合为获取的文档集合 从表中可以得到信息获取系统的评价： 精度： 召回率： （2.3） 基于该表，就可以计算精度召回率的值。 （3）相似度：对于包含个词条的查询向量和一个文档向量来说，它们之间的相似度可以通过2.4公式来计算： （2.4）4、模型的建立 在模型的原理中，我们有提过将给的文章进行预处理。也就是提取出我们要查找的关键词。针对本文就不需要了。然后我们把信息库中的文章进行倒排文件处理。表示对这篇文章进行倒排处理后所得的结果。接着

21、我们在用户搜索界面输入关键字。计算机通过顺序查找法找到相关文章，由常识可以知道也许搜索的相关文章不止一篇，这时我们按照关键词在文档中的权重进行排序。查找出来的文章与要查找的文章的相似度越大排序就越靠前。最后通过搜索引擎的主要指标（响应时间、召回率、相似度）写出其总指标: （2.5）其中，为加权系数。总指标是对模型的搜索引擎的一个评价。下面我们举个例子来说明我们整个模型。（一） 提取关键词设有两篇文章1和40 1文章1的内容：Drazin inverse，moore-penrose inverse，reverse order law；40文章40的内容：Inverse singular valu

22、e problem，inverse eigenvalue problem；由于文章中给出的已经是关键词，因此我们不需要进行预处理。文章1的关键词为：Drazin inverse moore penrose inverse reverse order law文章40的关键词为：Inverse singular value problem inverse eigenvalue problem(二)建立倒排文件有了关键词后，我们就可以建立倒排索引了。上面的对应关系是：“文章号”对“文章中所有关键词”。倒排索引把这个关系倒过来，变成：“关键词”对“拥有该关键词的所有文章号”。文章1，40经过倒排后变成

23、 关键词   文章号Drazin 1eigenvalue 40Inverse 1，40law 1moore 1order 1penrose 1problem 40reverse 1singular 40value 40 通常仅知道关键词在哪些文章中出现还不够，我们还需要知道关键词在文章中出现次数和出现的位置，通常有两种位置：a)字符位置，即记录该词是文章中第几个字符（优点是关键词亮显时定位快）；b)关键词位置，即记录该词是文章中第几个关键词（优点是节约索引空间、词组（phase）查询快）因此加上“出现频率”和“出现位置”信息后，我们的索引结构变为：关键词 

24、0;  文章号出现频率    出现位置Drazin 11 1eigenvalue 401 6Inverse 12，402 2，5，1，5law 11 8moore 11 3order 11 7penrose 11 4problem 402 4,7reverse 11 6singular 401 2value 401 3以Inverse这行为例我们说明一下该结构：Inverse在文章1中出现了2次，文章40中出现了2次，它的出现位置为“2，5，1，5”这表示什么呢？我们需要结合文章号和出现频率来分析，文章1中出现了2次，那么“2，5”就表示Inverse在文章1中出现的两个位置，文章40中出现了2次，而“1，5”就表示Inverse是文章40中出现的两个位置。以上通过简单的例子说明倒