当前进步搜索引擎效率和精度的关键技术-计算机应用论文

1、当前进步搜索引擎效率和精度的关键技术-计算机应用论文     论文摘要：搜索引擎；聚类；相关度 论文摘要摘要：为了使用户快速地从网页中找到所需要的内容，在设计搜索引擎时，需要更好地进步搜索引擎效率和精度，该文阐述了六种进步搜索引擎效率和精度的技术。 互联网自诞生以来不断成长，其内容不断丰富，整个网络逐渐堆积成一个前所未有的超大型信息库。Internet作为一个信息平台在人们的日常生活和工作中发挥着越来越重要的功能，人们越来越多地通过Internet获取信息。然而伴随互联网的飞速发展，普通网络用户想找到所需的资料简直如同大海捞针，以至于迷失在信息的海洋中不

2、知所措。搜索引擎的出现正好缓解了人们面对互联网信息爆炸带来的压力，但是尽管如此，搜索引擎搜索得到的结果中仍然包含了和用户查询请求不相关的文档，用户必须逐个地浏览以找到相关文档，花费了大量的精力。当返回的结果数目众多时，这个新题目更为突出。因此如何更好地进步搜索引擎效率和精度，成为搜索引擎重点需要解决的新题目。目前进步搜索引擎效率和精度的方法主要有如下六个关键技术。 1 基于超链的相关度排序 排序搜索引擎的检索结果往往过于庞大，用户一般只会浏览前面的一部分结果。通过对检索结果进行相关度排序，搜索引擎试图使相关的文档尽可能地出现在结果的前面部分，以改进检索结果的输出。固然各个搜索引擎中相关度排序的

3、具体实现各不相同，但是基本上都采用了基于Web文档内容的方法，即考虑用户所查询的词条在文档中的出现情况，包括摘要：词条频率、逆文档频率、词条位置等因素。这种方法有很大的局限性。一方面，相关度高的页面不一定是用户普遍欢迎的页面；另一方面，有些Web页面的作者利用上述因素来欺骗搜索引擎（spamming），以进步其页面的排序。 事实上，Web中还蕴含了丰富的结构信息。页面之间的超链反映了页面间的引用关系，一个页面被其它站点引用的次数基本上反映了该页面的受欢迎程度（重要性）。超链中的标记文本（anchor）对链宿页面也起到了概括功能，这种概括在一定程度上比链宿页面作者所作的概括（页面的标题、关键字、

4、摘要）要更为客观、正确。因此，近年来出现了一些基于超链的相关度排序方法，作为基于内容方法的补充，例如，Stanford大学探究的PageRank算法等。这类方法通过为Web页面构造引用图，并综合考虑页面的被引用次数以及链源页面的重要性来判定链宿页面的重要性。一些搜索引擎已经开始使用基于超链的相关度排序方法。例如，以PageRank为核心技术的搜索引擎Google能够查询和用户请求相关的“权威”页面1。此外，Google通过分析超链中包含的文本，可以对链宿页面进行非全文索引，而不需要下载和分析实际的页面。目前，Google已经发展成为一个主要的搜索引擎，实际下载并索引了近100000000的We

5、b页面。但是通过超链分析，其覆盖度达到了300000000，超过了其它任何搜索引擎。 2 检索结果的联机聚类 尽管搜索引擎采用了各种方法来进步检索结果的精度，但是结果中仍然包含了和用户查询请求不相关的文档，其比例高达75%以上。此外，搜索引擎返回给用户的通常是一个线性的文档列表，固然经过了相关度排序，但是相关文档和不相关文档仍然混杂于其中。用户必须逐个地浏览以找到相关文档，花费了大量的精力。当返回的结果数目众多时，这个新题目更为突出。 为了方便用户的浏览，一些探究职员开始将聚类技术用于Web信息检索结果的可视化输出。聚类是指将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能地大，而不同

6、簇间的相似度尽可能地小。Hearst等人的探究已经证实了“聚类假设”，即和用户查询相关的文档通常会聚类得比较靠近，而阔别和用户查询不相关的文档。因此，我们可以利用聚类技术将搜索引擎的检索结果集合S划分为若干个簇(S1，Si，Sm)，并以簇Si的质心averagedSi(d)作为簇Si的描述。这样，用户只需要考虑那些相关的簇，大大缩小了所需要浏览的结果数目。当一次聚类天生的簇Si中仍然包含大量文档时，可以对该簇中的文档再次聚类得到若干个子簇(Si，1，Si，j， ，Si，n)，直到用户满足为止2。Etzioni等人的实验结果表明，使用一些改进算法来对检索结果进行联机聚类不但是可行的，而且十分有效

7、。 3 基于概念的检索 大多数搜索引擎提供的检索服务是一种关键字检索（KeywordSearch），即检索出那些显式地包含用户指定词条的文档。由于自然语言中广泛存在同义和多义现象，关键字检索显然是不够的。一些搜索引擎，例如Magellan，开始在关键字检索的基础上引进基于概念的检索（ConceptSearch）。该方法利用了词条在概念上的相关性，因此可以检索出那些并不显式地包含用户指定的词条，但是却包含其同义词或者下位词的文档。例如，用户向Magellan查询“robot”时，Magellan除了返回包含“robot”的结果，还会找到提及“crawler”，“spider”，“wander”等

8、词条的结果。这样，既方便了用户请求的输进，也进步了信息检索的召回率。 搜索引擎在实现基于概念的检索时，一般通过对用户的查询进行概念/词条扩展，然后转化为关键字检索。概念/词条关系的获得可以有以下两种方法。 1) 手工建立词典来存储概念层次及词条之间的交叉联系，该工作通常由领域专家来完成。 2) 使用语法分析、统计等技术从文档集合中自动学习。 4 相关度反馈 在很多情况下，用户难以提出查询，其初始的查询请求q通常是不精确、不完全的。和基于概念的检索类似，相关度反馈技术也可以帮助用户形成查询请求。但是，基于概念检索的目的是通过扩展查询请求来进步系统的召回率，而相关度反馈技术则是通过对查询请求不断地

9、进行修正以进步系统的精确度。 具有相关度反馈功能的系统中，系统按照下述过程对用户的查询请求进行逐步求精。 1) 索引器给出查询q的检索结果集合S。 2) 用户对S中文档的相关度进行评估，并反馈给系统。所有被用户标记为“相关”的结果组成了正反馈集合S+，标记为“不相关”的结果组成了负反馈集合S-。 3) 系统根据用户的反馈对查询q进行修正。例如，在矢量空间索引模型中，可以将正反馈集合中的文档矢量加到查询矢量上，同时减往负反馈集合中的最不相关的若干文档矢量，即V(q)V(q)+dS+V(d)-dargmax(S-)V(d)。 4) 重复步骤1)，2)，3)，直到用户得到满足的结果为止3。 一些探究

10、和实验结果表明，利用相关度反馈可以较好地改进检索效果。但是，目前很少有搜索引擎支持该功能。其原因可能是由于相关度反馈需要用户的参和，而普通用户在使用搜索引擎时不太愿意花时间利用这些附加功能。 5 分词技术 网上的中文信息具有分词复杂、多内码转换等特征。因此，中文智能搜索有其独占的特征。 对中文信息的访问，不可避免的会碰到分词，这也是中文搜索引擎要解决的主要新题目。现有的汉语分词算法有很多，如基于词库的最大匹配法、逆向最大匹配法、最佳匹配法、高频优先分词法；基于语法和规则的分词法；基于频度和统计的分词法；基于神经网络的分词法和专家系统分词法等4。这些算法适用于不同要求的场合但又存在各自的缺陷，在

11、具体应用时一般使用几种算法相结合的方式来弥补单纯使用一种分词法所带来的不足。分词技术中的基于词库的算法日前使用较广，也较为成熟。这类算法分词的正确性很大程度上取决于所建的词库。一个词库应具备完备性和完全性两方面。词库的完备性，简单来说就是对任意一个字串，总能按词库找到对它进行切分的方法。词库的完全性，意味着词库应包含所有的词。通常先构造一个最小完备词库，然后在此基础上进行扩展，建立一个完全词库。 6 数据库中增量式信息更新方法 增量式信息更新方法的基本思路是摘要：在WWW中包含大量的文档资源，这些资源的变化周期是不一致的摘要：有的变化无常，有的十分稳定。因此应该以文档的变化周期作为进行有效性验

12、证的依据，在每一次索引信息库的更新过程中，只对那些最可能发生变化的（部分）文档进行验证。 一个文档的变化周期就是它相邻的两次变化之间的时间间隔。 值得注重的是，一个文档的变化周期可能是不固定的。在某个时期内，它可能变化得比较频繁，而在另一个时期内，它则可能比较稳定。一般地说，无法正确地计算一个文档变化周期，只能根据文档在一个时期内的变化情况来估算它的变化周期。下面给出一个启发式规则，作为估算文档变化周期的一个依据。 假如在一个时间间隔内一个文档的内容没有发生变化，那么可以以为它处在一个稳定期，在下一个相同的时间间隔内它也很可能不会发生变化。反之，假如在一个时间间隔内一个文档的内容发生了变化，那

13、么在这个时间间隔内它就很可能发生了多次变化。 从实用的角度出发，通常以索引信息系统的信息更新周期作为度量文档变化周期的时间单位，也就是说，一个文档变化周期的取值只能是系统信息更新周期的倍数。给出如下的增量式信息更新算法摘要： /*假设当前正在进行的是第k(k1)次信息更新过程。*/ Begin While（索引信息库中还有文档信息的有效性没有验证时）任取一个未验证的文档作为当前文档; If（当前文档的变化周期f是k的因子）Then 验证当前文档的有效性; If（当前文档已不能被访问）Then 从索引信息库中删除对应的记录 If（当前文档已经发生了变化）Then 把当前文档URL加进到目标列表;

14、 把当前文档的变化周期修改为Max(1，f/2); Else 把当前文档的变化周期修改为2f; 以目标列表中的URL作为浏览出发点，启动机器人开始新一轮信息收集工作; End5 当一个文档第一次进进系统时，它的变化周期被假定为1。也就是说，假定它会在系统更新周期内发生变化。随着信息更新过程的不断进行，将根据文档的实际变化情况，不断地调整它们的变化周期。假如一个文档的索引信息在一次信息更新过程需要予以更新，也就是说，文档的内容发生了变化，我们以为它很可能会在近期内再发生变化，因此，把它的变化周期缩短为原来的一半。假如在预计的变化周期内文档没有改变，那么就以为它在近期是比较稳定的，因此把它的变化周期扩展为原来的两倍。 增量式信息更新方法可以极大地减轻搜索引擎进行索引信息库维护的负担。由于我们以系统信息更新周期作为度量文档变化周期的基本时间单位，而且文档变化周期只能是系统信息更新周期的2的幂次，因此可能会影响少量文档索引信息的时效性。但是，考虑到WWW庞大的规模，从整体上看，增量式信息更新方法是一个能够进步搜索引擎工作效率的有效手段。 总的说来，在搜索引擎的发展过程中，固然出现了上述众多的技术来进步引擎工作效率，但不管是那种技术，短期内,要完全使搜索引擎在实现技术上都超过人脑仍然是