（计算机应用技术专业论文）基于主题精选算法的元搜索引擎的应用研究.pdf

辽宁工程技术大学硕士学位论文 摘要 搜索引擎是目前w e b 检索的主要工具。如果想得到全面、准确的搜索 结果，必须同时使用多个搜索引擎，在这样的背景下产生了元搜索引擎。 元搜索引擎的出现，在一定程度上解决了这些问题。虽然元搜索引擎能够 提高搜索的覆盖范围，但是它能够得到的网页排序信息却非常有限。因此， 在搜索结果返回用户前需要有一个检索后处理过程，即主题精选过程。主 题精选经典算法h i t s 的链接分析迭代往往会收敛于邻域图中与查询主题 不太相关的紧密交织区域( t k c ) ，从而导致主题偏移。 本文对h i t s 算法进行了改进，并在此基础上提出了一种基于用户对成 员搜索引擎信任度的主题精选算法。理论分析和实验结果表明：新算法能 避免主题偏移并能依据不同用户对不同成员搜索引擎的信任程度来识别 更为合理和有意义的权威信息源与中心信息源。 关键词：搜索引擎，元搜索引擎，主题精选算法，h i t s ，邻域图 辽宁工程技术大学硕士学位论文 a b s t r a c t s e a r c he n g i n e sa r em a i nt o o i sf o ru s e r st ol o c a t ei n f o r m a t i o no ni n t e r n e t i fw i s ht 0 g e tr e l a t i v e l yf u l l - s c a i e ， a c c u r a t es e a r c hr e s u l t sm u l t i s e a r c h e n g i n e ss h o u l db eu s e d ，s oi n t h i sb a c k g r o u n dm e t a - s e a r c he n g i n e o c c u r s t h eo c c u r r e n c eo ft h ew e bs e a r c he n g i n eo v e r c o m e st h i sp r o b l e mi ns o m e d e g r e e t h o u g ht h em e t a s e a r c he n g i n ei sa b l et op r o m o t et h ec o v e r a g eo f t h e s e a r c h i n gs c o p e ，t h es o r ti n f b r m a t i o no ft h ew e bp a g e si sv e r yl i m i t e d s oa p o s t - p r o c e s s i n go p e r a t i o n ， n a m e dt o p i cd i s t i l l a t i o n ，i sn e e d e db e f b r et h e s e a r c hr e s u l t sa r er e t u r n e dt ot h eu s e r t h ec l a s s i c a la l g o r i t h m ，h i t s ，i s l i k e l yt oc o n v e r g ea ta ni r r e l e v a n tt i g h t i yk n i tc o m m u n i t y ( t k c ) ，t h u sl e a dt o t o p i cd r i f t t h i sp a p e rp r e s e n t sa ni n l p r o v e da l g o r i t h m t h ea l g o r i t h mi sb a s e do n u s e r sc 6 n n d e n c eo n t a r g e t s e a r c h e n g i n e s t h e o r e t i c a l a n a l y s i s a n d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h en e wa l g o r i t h mc a na v o i dt o p i cd r i f ta n d i d e n t i f ym o r er e a s o n a b l ea n dm e a n i n g f u la u t h o r i t i e sa n dh u b so nt h et o p i c k e y w o r d s ：s e a r c he n g i n e ，m e t a - s e a r c he n g i n e ，t o p i cd i s t i l l a t i o n ， h i t s ，l i n kg r a p h 创新点声明 本人声明所呈交的学位论文是我个人在导师指导下进行的 研究工作及取得的研究成果：奎衷对原旦j 工曼篡珐丛凰友面进氖 工改进龛折三= 煮厦是垄玺域图胸形威部分丕蔑考虐屈= 靖虑缒内部链 接i 另二杰面就是在跌t 媾圜愿褪值魏筮k 采用王基奎集向量加撅擐影 篡法k 差在此基地上提出工= = = = = 弛基王月丘满意廛的霾攮塞孔擎圭 题撼逸熊序簋法点道过塞验分扳l 运箕法玉论是在捡索速度还是 在摊庄的赢教性上盒堡丝赢面都直= 庭施握赢三一 尽我所知，到目前国内外文献未见报道。 作者：童l 壁望日期： 辽宁工程技术大学硕士学位论文 l前言 1 1引言 近年来，互联网已成为巨大的、越来越普及的信息源，越来越多的结 构、团体和个人把互联网作为信息交流的场所。怎样在互联网上快速地， 经济地查询想要得到的信息是一个引起广泛兴趣的问题。搜索引擎正是为 了解决这个”迷航”问题而出现的技术。搜索引擎( s e a r c he n g i n e 简称s e ) 以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织 和处理，并为用户提供检索服务，从而起到信息导航的目的。现在，网上 的搜索引擎有很多，比较著名的有g o o g l e ，y a h o o ，百度等等。 据信，一个单一搜索引擎的网络覆盖率最多只能覆盖到整个i n t e r n e t 资源的3 0 5 0 【1 1 ，因而查全率便无法保障；再加上任何搜索引擎的设计， 均有其特定的数据库索引范围、独特的功能和使用方法，以及预期的用户 群指向，导致同一个搜索请求，在不同搜索引擎中查询结果的重复率不足 3 4 i 纠，因而查准率亦无法保证。因此，要想获得一个比较全面、准确的 结果，就必须反复调用多个搜索引擎，并对返回结果进行比较、筛选和相 互验证。元搜索引擎便应运而生。 元搜索引擎系统建立在多个现有的搜索引擎之上，提供对这些搜索引 擎进行统一访问的服务，一个复杂的元搜索引擎会维护一些关于底层搜索 引擎内容的信息。简而言之，当元搜索引擎接到用户查询后，它能将该查 询分送到适当的成员搜索引擎，再搜集和整理底层引擎返回的结果，并利 用自己的网页排序算法对得到的结果集进行排序，为用户提供统一的查询 界面与返回结果。 元搜索引擎的出现，提高了系统的查全率，但如何提高查准率，是个 棘手的问题。在此引入了基于主题精选的查询结果处理算法，采用这样的 算法旨在帮助元搜索引擎更加有效得到权威网页，以期更好地满足用户的 需求。 1 2 国内外研究现状 国外主要的元搜索引擎有：m e t a c r a w l e r ，p r o f u s i o n ，s a v v v s e a r c h ， m a m m a 。国内的元搜索引擎较少，如北极星等元搜索引擎。虽然中文元搜 辽宁工程技术大学硕士学位论文2 索引擎已经有很多在使用，但其检索功能、检索结果的排序、运行速度等 方面较国外尚有差距。中文元搜索引擎需要进一步研究和开发。论文对国 内外的几个著名的元搜索引擎进行了测试。分别向这些元搜索引擎输入6 0 个不同的中文关键词和短语以及6 0 个不同的英文关键词和短语，大致归纳 出了当前元搜索引擎的发展现状。 国外的元搜索引擎一般都有较高的查全率和查准率。但是，这些国外 搜索引擎对国内网页的覆盖率不是很高，因而在查准率上也受到很大的限 制。影响这些搜索引擎查准率的另一个因素是国内的许多网页制作和维护 不规范，时常有无用链接，像g o o g l e 这类使用链接数来确定网页优先级的 搜索引擎往往得不到很有用的结果。 国内的元搜索引擎一般都采用简单的位置排序算法，通过提取搜索引 擎返回结果的位置信息进行排序，没有充分利用这些搜索引擎所包含的其 它信息。对搜索结果的排序与用户的需求信息有出入，很难找到有用的信 息，但是去重效果不错，基本上消除了重复项。 众所周知，w e b 搜索引擎的目标之一就是要为某一特定的搜索给出n 条最有用的搜索记录。w e b 搜索引擎查找数据库中的记录并且针对某个查 询对这些记录进行排序。元搜索引擎也有同样的目标，即返回用户认为最 好的n 条记录。但是不同的是元搜索引擎不需要数据库，而是依赖于其它 搜索引擎返回的结果。同普通的搜索引擎一样，元搜索引擎也要对返回结 果进行排序，但是问题在于元搜索引擎必须能够在记录的相关信息较少的 情况下进行排序工作。因此元搜索引擎虽然能够增加搜索的范围，但是其 性能也受到下列问题的限制： 1 元搜索引擎在获取结果的数量上受到限制，这些限制要么是人为 施加在成员搜索引擎之上的，要么受到可用成员搜索引擎的限制。 2 元搜索引擎虽然可以访问其它搜索引擎的返回结果，但是这些结 果都只是从这些引擎的返回页面中获得，对每条记录的排序及其它一些重 要信息获取非常少，甚至没有。这也是元搜索引擎需要解决的一个问题。 3 元搜索引擎主要依靠外部的其它搜索引擎，这些搜索引擎的搜索 时间是元搜索引擎所不能控制的。因此，元搜索引擎有一个搜索时间问题 有待解决。 辽宁工程技术大学硕士学位论文 由此得出元搜索引擎的问题是：某一个搜索引擎的搜索结果的偏差直 接影响到元搜索引擎搜索结果的有效性。元搜索引擎必须对这个问题采取 相应的措施，保证元搜索引擎的搜索结果不会因为某个搜索引擎的偏差而 使整个搜索结果失准。为此必须对结果进行合理的排序并尽可能地为用户 得到更多有用的结果。这是本文研究的重点，也是作者要阐述的主要内容。 1 3课题研究的目的及意义 因特网上的信息浩如烟海，优劣混杂，缺乏统一的组织和管理，给人 们有效地查询和利用信息带来了很大的不便，搜索引擎就是为了开发和利 用这些网络信息资源而产生的网络信息查询工具，它已经成为因特网中最 重要的部分，是目前网络用户获取网上丰富信息资源的一个重要途径，但 传统的独立搜索引擎存在着信息资源覆盖率低、检索效率较低等问题1 3 巧1 。 因为任何一个独立的搜索引擎都无法穷尽所有的w e b 信息资源，而且对于 同一个查询请求，不同的搜索引擎因其工作机制不同，得到的结果中重复 率也较低。因此在很多情况下人们为了获得更高的查全率，需要同时使用 具有不同数据搜索范围的搜索引擎，这就增加了检索的不便，元搜索引擎 就是在这种情况下，诞生并发展起来的【6 ， 。现在已经出现了一大批元搜 索引擎，其中以英文元搜索引擎较多，发展较好，而中文搜索引擎发展缓 慢。目前运营的元搜索引擎各具特色，功能各有侧重，完全“理想”的尚 不多见。另外，很多主流的搜索引擎提供的服务没有考虑每个个体用户的 需求，没有考虑用户的差异。本文就是要在研究现有元搜索引擎存在的局 限性的基础上，设计出一个结构更合理，功能更优越，同时能够融合很多 相关领域技术，体现用户差异查询的元搜索引擎结果排序的结构模型，为 查询效率更高的检索工具的早日实现做出贡献8 1 。 1 4 作者所做的工作 通过调查发现，使用w e b 搜索引擎搜索信息时，用户并不一定能够得 到所要的内容。这个问题一方面是由于搜索引擎没有达到一定的覆盖率， 另一方面是因为搜索引擎不能正确地判断该文档的重要性造成的。元搜索 引擎虽然在覆盖率方面显示出较高的能力，但是由于在获取结果的排序信 息时受到诸多限制，从而降低了其判断文档重要性的能力。本文研究了一 辽宁工程技术大学硕士学位论文4 种更加有效的结果排序算法一一基于用户满意度的元搜索引擎主题精 选的排序算法，对每一个w e b 文档的有用性进行客观的评价。 作者在论文中做的工作主要有以下几个部分： 1 解析搜索引擎系统搜索到的网页。论文采用编译原理中的算符优 先算法解析搜索引擎中返回的网页，从中提取各个记录及记录中的元素， 比如标题、摘要、链接等。设计并实现了算法中需要的数据结构和相关算 法。 2 现有元搜索引擎结果排序算法的设计与比较。一般的元搜索引擎 的排序算法都采用位置排序和摘要排序算法。论文开发了一种新的基于主 题精选的算法对返回的网页结果进行排序并完成了这些算法的编码工作。 通过这些工作和对结果的分析，得出了比较理想的效果，算法能够充 分利用各个搜索引擎返回的有限信息得出比较客观的结果。 1 5 论文的主要内容 第一章主要介绍了元搜索引擎产生的背景，现阶段发展状况及其前 景。描述了普通搜索引擎的局限性，并在此基础上提出了元搜索引擎的优 势以及急需解决的几个问题。第二章主要介绍了元搜索引擎的结构，各个 部分的主要功能，以及各个部分相互协同运作的模式，对元搜索引擎做了 整体的描述。第三章介绍了w e b 链接结构与主题精选。第四章是对经典 主题精选h i t s 算法回顾、分析与评价，通过分析了解了主题精选算法 h i t s 存在的不足。并针对前面对h i t s 算法的分析来提出对其的改进方 案，最后提出了一种基于用户满意度的元搜索引擎的结果排序算法。第五 章是实验部分，通过实验比较出改进的算法在提高查询的有效性方面的确 有一定的提高。 辽宁工程技术大学硕士学位论文 2 元搜索引擎 本章主要介绍元搜索引擎的定义、工作原理，分类及元搜索引擎与传 统搜索引擎相比的优势。并从总体上对元搜索引擎的实现过程进行概述。 2 1元搜索引擎的概述 2 1 1元搜索引擎的定义 随着i n t e r n e t 的极度膨胀，我们越来越依赖于各种搜索引擎查找信息。 但是，他们的可信度到底有多大呢? 根据专家的评测，目前主要的搜索引 擎返回结果的比率不足4 0 ，而且由于机制、范围、算法等的不同，导致 同样一个查询请求在不同的搜索引擎中的查询结果的重复率不足3 4 。因 此，要想获得一个比较全面的、准确的结果，就必须反复调用多个搜索引 擎。元搜索引擎的出现，在一定程度上解决了这些问题，这也使得元搜索 引擎有了它的生存空间。也正是因为元搜索引擎是建立在其他已有搜索引 擎上，要受到其他搜索引擎的制约。所以也有着很多不足之处，其中元搜 索引擎的维护就是一个很大的问题，因为要依赖于其他搜索引擎。建立元 搜索引擎的目的就是要为用户提供精确而全面的搜索结果，但是要真正做 到这一点并非是件容易的事情。既然元搜索引擎能够提供给用户精确而全 面的检索结果，那么究竟什么是元搜索引擎呢? 元搜索引擎( m e t as e a r c he n g i n e 简称m s e ) ，是一种建立在独立搜索 引擎基础上，调用其它独立搜索引擎的引擎，亦称”搜索引擎之母”( t h e m o t h e ro fs e a r c he n g i n e s ) a 在这里，”元”( m e t a ) 为”总的”、“超越”之意，元 搜索引擎就是对多个独立搜索引擎的整合、调用，控制和优化利用。相对 于元搜索引擎，可被利用的独立搜索引擎称为一源搜索引擎“( s o u r c e ；e a r c he n g i n e ) ，或”成员搜索引擎。( c o m p o n e n ts e a r c he n g i n e ) 。从功 能上来讲，元搜索引擎像是一个过滤通道，以多个独立搜索引擎的输出结 果作为输入，经过一番提取、剔除、萃取等操作，形成最终结果，然后将 最终结果输出给用户。 2 1 2元搜索引擎的分类 元搜索引擎根据不同的标准可以划分为不同的类型。根据检索机制可 以划分为集中罗列式元搜索引擎和统一入口式元搜索引擎l7 1 ，以下对这两 辽宁工程技术大学硕士学位论文6 种类型的元搜索引擎做详细介绍。 集中罗列式元搜索引擎 集中罗列式元搜索引擎按照一定的形式将所有的独立搜索引擎集中 呈现在页面上，并提供了一个公共的检索入口，但实际上用户一次只进入 一个独立搜索引擎。这种类型元搜索引擎的结果反馈页面多直接引用原始 搜索引擎的结果页面。从表面上看，这类元搜索引擎与独立搜索引擎具有 更多的相似点，它们的特点是： ( 1 ) 一次检索一个搜索引擎； ( 2 ) 检索结果直接调用原始独立搜索引擎的结果页面； ( 3 ) 只支持原始独立搜索引擎支持的检索语法。 统一入口式元搜索引擎 统一入口式元搜索引擎为收录的独立搜索引擎建立了一个公共查询 入口，用户发出检索请求后，提问表达式被分别提交给多个独立搜索引擎， 最终反馈的结果是多个独立搜索引擎查询结果的融合。根据结果显示的不 同，这类元搜索引擎又可以分为直接调用原始页面型、混合综合型和分散 综合型。 ( 1 ) 直接调用原始页面型元搜索引擎，检索结果直接来自原始搜索引 擎站点的结果页面。 ( 2 ) 混合综合型元搜索引擎，将各个独立搜索引擎中查找的结果进行 融合，结果显示以记录为单位，记录描述包括该记录被检出的来源。 ( 3 ) 分散综合型元搜索引擎，这种类型与混合综合型元搜索引擎在结 果显示上有所不同，它以独立搜索引擎为单位进行结果显示，在同一个独 立搜索引擎得到的结果被集中列在该搜索引擎之下。 2 1 3元搜索引擎的构成 元搜索引擎由三部分组成： 检索请求预处理部分：实现用户的个性化检索设置的要求、成员搜索 引擎的调度方案、检索时间的限制、返回结果量的限制等； 检索接口代理部分：实现将用户的个性化查询请求转化为可被成员搜 索引擎识别的固定格式： 检索结果处理部分：实现把调用的成员搜索引擎检索到的结果去重、 辽宁工程技术大学硕士学位论文7 合并、排序和按一定的格式返回给用户。 元搜索引擎的软件结构示意图如图2 1 所示。根据箭头的流向可以看 出一个元搜索引擎在处理用户请求的查询时处理流程。 图2 l元搜索引擎的系统结构 2 1 4元搜索引擎的性能评价指标体系 作为一种搜索引擎，元搜索引擎也有搜索引擎的一些基本指标，如查 全率、查准率、召回率、响应速度、响应时间、用户负担等”。但是元搜 索引擎个体差异很大，很难进行精确的评价1 0 l 。元搜索引擎性能评价指标 体系主要包含四个部分：独立搜索引擎的调度策略、是否提供足够的检索 选项、对搜索结果的处理能力和相关度评价。 ( 1 ) 独立搜索引擎的调度策略有些元搜索引擎固定地调用几个独 立搜索引擎，用户不能修改；有些元搜索引擎的高级特性中让用户选择调 用哪些搜索引擎。这两种策略都有不足之处，前一种将跟不上搜索引擎的 发展潮流。后一种，对于不熟悉搜索引擎的用户来说可能选择不到适合自 己需要的搜索引擎。文【1 l 】提出了通过遗传算法实现独立搜索引擎的自动 调度方法。这种算法如能融入到元搜索引擎系统中，必会大大提高系统的 查准率。 ( 2 ) 是否提供足够的检索选项包括是否提供高级检索服务，是否可 以限定最长检索时间，是否可以设置每个搜索引擎返回的结果数量，是否 辽宁工程技术大学硕士学位论文 8 可以设置每页显示的结果数目，是否可以设置标题大小和摘要大小等。检 索选项越多，用户使用的时候就越灵活。这也是衡量一个元搜索引擎性能 的一个标准。但由于元搜索引擎的检索特性向它所调用的独立搜索引擎检 索特性的转换所具有的复杂性，许多元搜索引擎不提供复杂的检索特性。 ( 3 ) 对搜索结果的处理能力对独立搜索引擎返回的搜索结果的处 理能力，这也是评价元搜索引擎性能的又一重要指标( 1 2 】。它包括结果的处 理和结果的显示。不同的元搜索引擎提供不同的结果显示方式。如按照时 间、按照搜索引擎、按照相关度等来排序。相比之下按照相关度来显示搜 索结果更合理一些。 ( 4 ) 相关度评价每个搜索引擎开发商为了将最满意的结果放到越 前面，不遗余力地创建出各种相关度指标体系，虽然没有一种方法是完美 的，但都有创新和独到之处。面对这些众多的相关度评价指标，按照怎样 的方式对成员搜索引擎返回的结果进行一致性的排序是元搜索引擎结果 处理部分面临的主要问题。 2 1 s元搜索引擎的国内外相关研究工作 国内外的主要元搜索引擎根据谷歌、百度和雅虎等搜索引擎搜索出元 搜索引擎，并通过一些著名的引擎指南网站所提供的线索来确定有代表性 的中外元搜索引擎，然后对检索出的元搜索引擎进行简单的测试，、从中选 出如下2 个中文元搜索引擎和5 个英文元搜索引擎表2 1 中外元搜索引擎的 性能比较。 表2 1中外元搜索引擎的性能比较 万纬v i v i s i m os e a r c hc o m搜星 d o p l i e 主页设置较好较好好一般好 搜索范围9 个可选2 3 个可选5 个可选未显示6 个可选 响应时间可选可选 不可选不可选不可选 分类搜索无有有 有尢 高级检索有有无无无 a n do ra n d o ra n do r 布尔检索 a n do r 空格 n o t n o t n o t 限制检索无有无无有 二次检索无无有无无 辽宁工程技术大学硕士学位论文 续表2 1 相关检索无无有尤无 结果可选性可选可选可选可选可选 结果可排序方 相关度聚类相关度尢相关度 式 连接情况一般一般一般一般一般 检索结果是否 有无有有尢 有重 由此看来，目前运营的元搜索引擎各具特色，功能各有侧重，完全“理 想”的尚不多见。在出现的一大批元搜索引擎中以英文元搜索引擎较多， 发展较好，而中文搜索引擎的发展还比较缓慢。 2 2 元搜索引擎功能 元搜索引擎是一个搜索其他引擎的搜索引擎。一个元搜索引擎以用户 查询词作为输入，然后将输入内容提交给多个成员搜索引擎，并将这些结 果按照一定的算法重新排序并以网页的形式显示给用户。元搜索引擎是用 来提高单个搜索引擎的覆盖率和准确率而出现的一种新的搜索模式。 在这一节中，首先介绍w e b 搜索引擎的结构。之后，提出了实现元搜 索引擎所需解决的问题，以及限制元搜索引擎查找有用结果的原因。 辽宁工程技术大学硕士学位论文l o 元搜索引擎结构图如图2 2 所示。 图2 2 元搜索引擎的结构 元搜索引擎的结构和普通的w e b 搜索引擎的结构有很多相似之处m 1 。 两者之间的主要区别是：元搜索引擎用虚拟数据库( 例如机器内存) 替代了 w e b 搜索引擎中真正的数据库。组成元搜索引擎的其它组成部分有：用户 接口模块，网页解析模块，元搜索管理调度模块，其它的普通搜索引擎， 搜索代理模块以及结果处理与评价模块【1 4 l 。其中虚拟数据库用来模拟普通 搜索引擎中本地数据库的功能，利用它来实现查询的提交和结果的返回， 但是却不占用本地大量的存储空间。 2 2 1用户接口模块 任何搜索引擎( 元搜索引擎或普通搜索引擎) 的用户接口都是用户和系 统之间的接口。这个模块负责接收用户的输入并显示输出结果。元搜索引 擎和普通搜索引擎一样必须捕捉用户真正需要的信息。除了有几个额外参 数决定搜索信息的位置以外，元搜索引擎与普通搜索引擎几乎是一样的。 辽宁工程技术大学硕士学位论文 元搜索引擎和一般搜索引擎的另一个不同之处是搜索的响应时间】。 普通搜索引擎可以按照具体的性能要求来设计和优化，但是元搜索引擎却 从根本上受到其它搜索引擎的性能限制。这是由于元搜索引擎必须等待所 有成员搜索引擎返回结果，所以可能比普通搜索引擎花费更长的搜索时 间。这是元搜索引擎需要解决的一个问题。 用户接口模块的输入可以是任意形式的字符串数据，格式可以是单个 关键字，也可以是多个关键字组合( 关键字之间应用空格或逗号分开) ，还 可以是句子。字符串长度控制在1 0 0 个字节以内。 该模块的输出是一个称为r e c o r d l i s t 的数据结构，这个数据结构包括： 标题、超链接、摘要、搜索引擎出处以及其它一些排序信息。 2 2 2调度模块 元搜索引擎的调度模块和普通搜索引擎的查询处理模块很相似。元搜 索引擎的调度模块根据用户的输入产生搜索查询请求。调度模块必须决定 查询哪一个成员搜索引擎，以及按照不同成员搜索引擎的要求修改用户输 入的查询请求。 调度模块为元搜索引擎系统决定主要的搜索决策。这些都直接影响元 搜索引擎是否能够得到有用的结果。错误的选择成员搜索引擎或者提交无 用的查询请求都不能得到很好的结果，而且成员搜索引擎的数目越多意味 着需要的网络资源越多，这就要求更多的时间来完成搜索任务，所以必须 在满足要求的情况下尽可能少地选择需要查询的成员搜索引擎。调度模块 的作用就是根据以往查询的经验，采用自学习功能来决定选择哪些成员搜 索引擎能在尽量减少搜索引擎数目的情况下，获取尽可能多的有用结果。 调度模块首先确定查询的用户和查询的内容，然后形成一个合适的查 询请求。之后，该模块提交这些用户的查询请求、选择最适合的搜索引擎 以及修正查询内容。接下来该模块提交并等待这些请求返回的结果。与此 同时，该模块必须与底层的通信协议交互以确保能够正确的记录系统运行 时的异常和错误。 1 总体来说，该模块的功能就是从用户输入中提取出关键字，并将这些 关键字提交给最适合的几个搜索引擎，将结果转交给结果处理模块做进一 步处理。如果用户输入的是句子，则调用语义解析模块解析这些句子并从 辽宁工程技术大学硕士学位论文 中提取出关键字，如果输入的本身就是关键字或关键字的组合，那么该模 块也会做一些辅助处理，比如增加一些辅助查询字段，提高搜索精度。 2 2 3结果处理模块 元搜索引擎的结果处理模块从成员搜索引擎中获取网页结果，并根据 各成员搜索引擎的返回网页的不同格式提取元搜索引擎需要的内容。该模 块将处理结果发送到结果排序模块的过程，同普通搜索引擎从数据库中返 回结果的过程是类似的。图2 3 表示了结果记录模块的主要功能：首先从 搜索引擎中获取w e b 页面，如图2 3 中的。接收结果”部分；然后，开始解 析这些页面并从中提取结果，如图2 3 中的“提取结果”部分。 覆霰引覃“ 图2 3结果处理模块结构图 有几个因素限制了结果处理模块获取有用结果的能力即为准确性。例 如，从搜索引擎返回的页面中，每条记录所附带的其它相关信息很少。搜 索引擎对于每条搜索记录都有大量的相关信息存储在本地数据库中，但是 仅有很少一部分信息出现在其输出的结果网页中；而且不同的搜索引擎在 结果网页中所提供的信息可能大相径庭；每个搜索引擎也可能有不同的输 出格式，以及不同的附带信息。例如，某个搜索引擎可能提供一个标题、 u r l 和一个摘要，而另一些搜索引擎可能仅提供标题、日期、u r l 和查询 词环境。即使是同一个网页经过不同的搜索引擎返回的结果也可能完全不 同。 一个高级的结果处理模块能够进行信息收集，以补充每条记录中不完 辽宁工程技术大学硕士学位论文 1 3 整的数据。比较常用的方法是下载w e b 网页以提供完整的h t m l 文档，以 便获取尽可能多的信息得到较为准确的结果。 该模块的输出是经过排序生成的最终可以直接用来显示和生成x m l 文档的结果描述表，如果需要，也可直接生成表示最终w e b 页面。 2 2 4排序模块 同普通搜索引擎的排序模块一样，元搜索引擎的排序模块根据每条记 录的相关数据计算出它的最终分数。如果元搜索引擎不能够直接比较结果 记录，可以使用融合策略将多个搜索引擎的排序结果合并成一个单独的排 序结果【l “”】。同普通的搜索引擎不同的是：元搜索引擎只能获取每条结果 记录的有限信息，丢失的信息可能使元搜索引擎很难判断一条记录是不是 用户所需的信息。排序模块性能的好坏主要取决于排序算法的优劣，这也 是整个元搜索引擎的关键部分，本文采用的排序算法属于信息融合算法一 类。 ， 下面主要介绍一下融合算法的相关概念和常用的方法。 元搜索引擎仅仅基于每个搜索引擎返回的有限信息来融合不同的搜 索引擎的返回结果。因为信息有限，所以不可能对结果进行直接的比较， 这就要使用本小节所介绍的信息融合算法。 进行结果记录的融合通常需要考虑四个方面：记录的权值、记录原有 的排序位置、服务器的附加值以及文档本身的内容。例如文档中所描述的 记录标题、链接、摘要等信息。 除了这几项内容以外，一些元搜索引擎还考虑了记录中出现查询词的 次数、位置以及从多个搜索引擎返回的u r l 。一条在标题、摘要或者u r l 部分包含了查询词的记录被认为是更加相关的记录。一条被许多搜索引擎 放在前几个位置的记录也有可能是很重要的记录，因为几个搜索引擎通过 不同的排序算法都将这条记录放在很重要的位置上，这就更加说明了这条 记录的重要性，它比其他记录都更有可能满足用户的需要。 一种常用的排序算法是t f - i d f 算法【2 0j ，它被用来评估搜索引擎返回的 每条记录。该算法要求所有的记录下载完毕而且是一种用户指定的“短语” 搜索。当文档不能全部下载时，可以使用n o r m a l i z e d i s t r b u t e s u m ( n d s l 算法来融合不同的结果记录。n d s 将来自每个搜索引擎的记录的排名作为 辽宁工程技术大学硕士学位论文 1 4 一个重要的参考要素，而且采取措施防止某一个搜索引擎的搜索结果主导 元搜索引擎最终的排序结果。n d s 算法要求重新为每个搜索引擎赋予一个 权值，而且为那些在多个搜索引擎中排名都靠前的记录追加一个附加分。 2 2 5 搜索引擎代理 许多元搜索引擎在构造调度模块和结果处理模块的同时，也使用一种 特殊的模块来增强系统的整体性能，这一特殊模块就叫“搜索引擎代理”。 一般来说，搜索引擎代理都与某一个搜索引擎相对应，它执行一些与调度 和结果处理有关的予任务。 代理其实是一种设计模式【2 1 1 ，它模拟它所代理的真实事物的某些个行 为，但对外它提供统一接口，隐藏不同真实事物之间的差别。这样使用代 理模式的系统就具有更大的灵活性，当真实事物的属性或行为发生新变化 时，系统不需要任何改动，只需要修改代理的具体实现即可。采用这一模 式有利于减少系统维护的开销。至于代理的种类，根据其应用环境的不同 有很大区别。而就信息获取领域中搜索代理的设计而言，已经成为今年来 研究的热点。例如，替代某个独立实体的代理往往具有一定目的而且能够 做出一定判断。代理应用的领域之一就是数字图书馆。在元搜索引擎中使 用代理是非常有用的，因为采用这种结构有利于进行模块化设计，每个代 理都可以单独设计而且可以进一步应用于分布式系统中。元搜索引擎代理 其实是替代真实搜索引擎来接收用户的查询与输入并产生w e b 请求的一段 程序，同时它也替代相应的真实搜索引擎来处理结果。 搜索代理模块的输入是：调度模块输出的符合各搜索引擎的多个关键 字及辅助参数集合，并将这些数据组装成搜索引擎所需的提交格式来得到 查询结果。该模块输出的是结果描述表，其中包括搜索引擎返回的每个结 果记录的连接、摘要、日期、位置以及搜索引擎的出处等信息。 2 3 元搜索引擎处理过程 上面已经介绍了元搜索引擎的整体结构和各个模块的主要功能，下面 将介绍这些具有不同功能的各个模块是怎样协作，从而来完成用户提交的 查询请求的。首先，用户接口接收用户查询请求关键字或者这些关键字组 合，接着由分配调度模块解析用户的输入请求，调度模块在解析用户输入 请求过程中，结合各个成员搜索引擎的不同输入格式要求采用不同方法来 辽宁工程技术大学硕士学位论文 组合用户输入的关键字并将组合后的关键字提交给相应的成员搜索引擎。 用户输入的查询关键字通过该模块解释，之后应该是一个针对不同成员搜 索引擎的多个关键字组合的集合，每个关键字组合对应一个搜索引擎，其 中应该包括以下一些内容：用户原始输入的关键字、与各个成员搜索引擎 相关的附加关键字以及其它一些辅助查询参数。然后这些关键字组合被送 到搜索代理模块中，这里每个搜索代理模块对应一个成员搜索引擎，当某 个搜索代理模块获得符合其要求的数据后，便将其中的信息按照这个搜索 引擎所要求的格式提交，并等待此搜索引擎返回结果。返回结果通常都是 一些网页，搜索代理模块也要负责解析这些网页并从中提取最终的结果记 录，并将其按照“标题、链接，摘要、位置、成员搜索引擎权值”的格式 放入结果记录表中。最后由结果处理模块对结果记录表进行处理，按照一 定的相关度算法对结果进行排序，并通知用户接口模块排序完成，由用户 接口模块将结果显示出来。 这里需要注意的是，当用户访问系统时，用户接口模块最先接收到用 户请求，并将用户请求转发给调度模块。如果输入请求是一些句子，调度 模块还将调用语句解析模块，将用户输入文本内容解释成多个相关的关键 字，以便利用这些关键字向各个成员搜索引擎搜索结果。此时，语句解析 模块会根据“搜索引擎特征表”中每个成员搜索引擎的特点解析出不同的 关键字组合以达到最好的搜索效果。语句解析模块也会利用“配置脚本” 中的要求对搜索行为进行约束，例如限制响应时间，设定返回网页的数量 等，对搜索结果进行约束。 这里还需要再次说明一下搜索代理模块的功能。当调度模块获得了所 需的关键字组合时，将会调用各个成员搜索引擎的搜索代理模块。搜索代 理模块与成员搜索引擎一一对应，每个搜索代理模块仅代理一个成员搜索 引擎，模拟这个搜索引擎的搜索过程，调度模块在运行过程中仅与搜索代 理模块交互而不与真实的成员搜索引擎进行交互。这样就使得各个搜索引 擎独立于元搜索引擎系统，当这些成员搜索引擎发生变化时也不会影响元 搜索引擎。这些搜索代理模块在获得关键字组合以后会向独立搜索引擎提 交并等待结果返回，最后将这些结果写入结果记录表中。 当所有成员搜索引擎的结果得到之后，调度模块将控制权交给结果处 辽宁工程技术大学硕士学位论文 理模块，由这个模块对返回结果进行处理，也就是对结果记录表进行处理， 按照一定的排序算法对其进行排序整理。为了节省空间，将排序后的结果 仍然放入结果记录表中。一旦结果排序任务完成，结果处理模块将控制权 返还给调度模块，调度模块又重新调用用户接口模块将结果记录表中已经 排序好的记录按照规定的网页格式显示给用户。 辽宁工程技术大学硕士学位论文1 7 3 w e b 链接结构与主题精选 3 1w e b 链接结构 w e b 是超文本的文档集合页面之间相互链接并形成一定的链接结构。 w e b 上信息检索、w e b 数据挖掘等w e b 上数据管理的研究都需要对w e b 的 链接结构进行分析和研究。 3 1 1w e b 链接图 w e b 是一个超文本集合，页面和页面之间通过超链接( h y p e r l i n k ) 相连， 超链接所在的网页是该超链接的起始网页，而该超链接的u r l ( u n i f o r m r e s o u r c e l o c a t o r ，统一资源定位符) 所指向的网页是该超链接的终止网 页，也就是说超链接是有方向的。因此根据图论中有向图的定义，w e b 可 用称为链接图( 1 i n kg r a p h ) 的有向图来建模。传统的方法是以页面粒度来 建模链接图：结点表示页面，有向边表示从一个页面到另一个页面存在( 一 条或多条) 超链接。 由于一个w e b 文档通常是由其w e b 站点作者创作的多个页面链接而 成的超文本文档，因此也可以站点粒度来建模链接图。结点表示站点有向 边表示从一个站点中至少有一个页面包含( 一个或多个) 超链接指向另一 个站点中的某( 几) 个页面，此时称为站点图( s i t eg r a p h ) 2 2 1 。 3 1 2w e b 链接结构的自组织性 w e b 虽然是一个分散的( d e c e n t r a l i z e d ) 信息网络，但是大量研究表明， w e b 的链接结构具有自组织性。在全局上，信息源( 页面或站点) 问通过 超链接，按相同或相关的内容主题自然地聚合( c l u s t e r i n g ) 在一起，形成一 个个群( c o m m u n i t y ) ，群落内部的信息源之间密集链接，而群落之间稀疏 链接，甚至根本不相链接。在一个群落内部，信息源之间的链接结构也有 规律的特征模式一一一个群落主要由两类信息源所组成：一类主要被别 的信息源所链接；另一类则主要链接到别的信息源。前者被k l e i n b e r g 称为 权威( a u t h o r i t y ) 一一包含高质量主题内容的信息源；而后者别称为中心 ( h u b ) 提供对高质量主题内容存取的信息源( 如图3 1 左图所示) ，它 们均是用户想要的好信息源。如图3 1 左图所示的权威信息源被大量的中 心信息源指向，而中心信息源则很少被其它信息源指向，他们指向大量的 辽宁工程技术大学硕士学位论文 1 8 其它信息源。如图3 1 右图所示，图上有两个群落，每个群落中的信息源 之间密集链接，群落中的信息源大都指向本群落中的信息源，只要很少的 链接( 虚线) 指向其它群落。 图3 一1w c b 的链接结构 3 1 3链接分析 w e b 的这种自组织性为链接分析提供了依据。链接分析基于以下一个 或二个简单的假设： ( 1 ) 从页面a 到页面b 的一条超链接是页面a 作者对页面b 的一种推荐 和称赞( 意味着权威性或质量) ； ( 2 ) 若页面a 与页面b 被一条超链链接，则它们可能有相同或相近的 主题( 意味着相关性) 。 大多数像g o o g l e ( w w w g o o g l e c o m ) 这样的第二代搜索引擎已在其文 档数据库中维护了页面间的链接信息。链接分析在w e b 信息检索中已经 普遍运用。它主要有两个用途：一是爬行( c r a w l i n g ) 高质量的页面；二是 对检索结果使用质量度量( q u a l i t ym e t r i c ) 评分排序( r a n k i n g ) 一一称基 于链接的排序( c o n n e c t i v i t y b a s e dr a n k i n g ) 。 基于链接的排序有两种方案： ( 1 ) 独立于查询( q u e r y i n d e p e n d e n t ) ：是一种用户检索前处理，链接 分析算法计算页面“固有的”质量分值。在用户查询时，质量分值与相关 度分值等线性组合后对结果进行排序。典型的排序算法有g o o g l e 中采用的 辽宁工程技术大学硕士学位论文1 9 p a 2 e r a n k 算法【2 3 1 。 ( 2 ) 依赖于查询( q u e r y d e p e n d e n t ) ：是一种用户检索后处理，检索系统 响应用户查询后，返回结果集。链接分析算法依此为起点，获得一组与用 户查询主题相关的页面，计算各页面的质量分值，并据此精选出少量高质 量的信息源。因此，这种方案也称主题精选。典型的算法有i b m c l e v e r 项 目中提出的h i t s ( h y p e r t e x tl n d u c e dt o p i cs e a r c h ) 算法24 1 。 3 2主题精选 由于用户提交的宽主题( b r o a d t o p i cq u e r y ) 查询表达的用户信息需求 往往不够明确，而且不同的用户对w e b 信息间系统返回结果的质量的评判 标准是一种主观意见，这就导致w e b 信息检索系统返回的对某一用户来说 是“好的”结果，对大多数用户来说却是“不好的”或“不相关的”结果 【”。而主题精选的本质是：试图从大量的质量评判主观意见中找到一致公 认的客观评判结论。主题精选的目标是：找到与用户查询主题相关且权威 ( a u t h o “t y ，即认为是高质量) 的信息源。 3 2 1宽主题查询 提交给w e b 信息检索系统的查询主题可以分为两种：窄主题查询 ( n a r r o w t o p i cq u e r y ) 和宽主题查询( b r o a d t o p i cq u e r y ) 。窄主题查询只涉 及到w e b 上很少的相关资源，由于这样的查询表达的主题非常确切具体， 因此w e b 上的相关资源是较少的，所以，对于窄主题查询w e b 上的信息检 索系统要面临的是解决它的召回率( r e c a l l ) 的问题【”。 宽主题搜索是指用户向检索服务系统提交一个主题语义不太明确或 概念范畴太大的查询( 平均包含l 一3 个关键词) 而进行的搜索。由于宽主题 查询的查询主题不明确，因此宽主题查询涉及到w e b 上丰富的相关资源， 大多数用户并不对整个相关资源的集合感兴趣，而几个相关并且是权威的 结果就可以令他们满意，这时候w e b 上的信息检索系统面临的是解决搜索 精度( p r e c i s i o n ) 的问题。 宽主题查询可进一步分类2 5 i ：查询可能定义了较为明确单一的主题 ( 如：”j a v ap r o g r a m m i n g1 a n g u a g e “) 而属于单主题查询，单主题查询有时 候可能会因为有多个子主题( 如：“j a v ap r o g r a m m i n gl a n g u a g e ”主题下的 “s p e c m c a t i o n ”，”a p p l i c a t i o nd e v e l o p m e n t ”、和t o o l s 等) 对应多个w e b 辽宁工程技术大学硕士学位论文 信息源群落而表现为多子主题查询；宽主题查询也可能因关键词的一词多 义( 如：”j a v a ”一一j a v a 语言；爪哇岛；爪畦咖啡) 、涉及多个不同技术 领域( 如：”r a n d o m i z e da l g o r i t h m s ”) 或高度分化( 如：”a b o r t i o n ”一一支持 人工流产 ；反对人工流产 ) 而属于多主题查询。 调查表明：w e b 上绝大多数用户查询属于宽主题搜索。宽主题搜索面 临信息过剩( a b u n d a n c e ) 问题，即系统返回大量( 例如几千甚至上万个) 与查 询主题“相关的”信息项，以至于用户根本无法从中精选出几个权威( 即 认为是高质量) 的w e b 信息源。因此需要一个基于质量度