（计算机软件与理论专业论文）元搜索关键技术研究与实现.pdf

摘要 曼i i , i i i i i i i ii i i i_,i i l 燃笪曼曼曼舅簟蔓曼曼曼黑皇曼曼笪燃皇曼 摘要 随着互联网和w e b 技术的不断发展，搜索引擎凭借自身的特殊优势，在w e b 前进的道路上扮演着越来越重要的角色，同时也成为人们关注的热点。由于互联 阏上w e b 信息的海量化，异构及动态特性的不断升级，通用搜索引擎在解决网页 搜索阕题时越来越不能令人满意，于是出现了元搜索引擎。元搜索弓l 擎是一种 w e b 上应用的信息检索的软件系统，它通过将用户的查询请求转发给成员搜索引 擎，然后将各个成员搜索引擎返回的结果进行处理后提交给用户。 本文在对搜索弓| 擎、元搜索弓| 擎耀关原理与技术分析的基础上，深入遗研究 了元搜索引擎的搜索结果排序和搜索结果消重等两个关键技术。具体研究内容及 成果如下： ( 1 )参考网页与网页之间通过相互链接的评价关系，分析了性能好的成员搜 索弓l 擎返回结果的质量较好，而质量好的结果应该被性能好的成员搜索引擎返回 的相互评价的对偶关系，提出成员搜索引擎的h u b 值和搜索结果的a u t h o r i t y 值的概念。 ( 2 )分析发现一次查询中成员搜索弓| 擎评价指标h u b 僮波动的情况，提浅焉 一组属于某个特定主题的查询词对成员搜索引擎计算主题h u b 值的观念。这样成 员搜索引擎的性能按照主题领域进行划分：对于一个成员搜索引擎，不同的主题 查询领域具有不同酌主题h u b 值。 ( 3 )利用成员搜索引擎的主题h u b 值对搜索结果进行排序。 ( 4 )分析了基于网页的和基于搜索结果的结果消重技术；分析了静态的和动 态的摘要提取方式，特别是分析了动态的基于关键词的摘要提取方式；分析了转 载网页的关于某个查询词的结采摘要中出现大量的共同语句集合的现象。基予这 3 点，提出基于搜索结果的摘要语句相似度的结果消重算法。该算法通过计算摘 要的语句向量模型中向量的相似度判断结果对应的网页是否属同一个内容的不 同转载网页或同一个网页，进而实现结果消重。 ( 5 )实现了基于上述算法的元搜索m e t a s e a r c h ，并通过实验对上述算法的实 验结果和性能指标进行了分析和讨论。 关键词元搜索孳| 擎：搜索引擎；结果排序；结果消重 a b s t r a c t a b s t r a c t a sap o w e r f u lf o r c ei nt h ei n t e r a c ta n dw e bt e c h n o l o g yd e v e l o p i n gp r o c e s s ，t h e g e n e r a ls e a r c he n g i n ei sp l a y i n gam o r ea n d m o r ei m p o r t a n tr o l ei nw e bs e r v i c ef o ri t s s p e c i a la d v a n t a g e a n da tt h es a l t l et i m e ，i ti sb e c o m i n gt h ef o c u so ft h ep u b l i c w i t h t h eh u g ea m o u n to fw e bd a t a , d i f f e r e n th i e r a r c h i e sa n dd y n a m i c se s c a l a t i n g ，i t b e c o m e sm o r ea n dm o r ed i f f i c u l t yf o rp e o p l et ob es a t i s f i e d t h ep r o b l e ms o l v i n g c a p a b i l i t yo ft h eg e n e r a ls e a r c he n g i n ei sl i m i t e d ，a n dh e n c eh e r ec o m e st h em e t a s e a r c he n g i n e m e t as e a r c he n g i n e sa r es o f t w a r es y s t e m sw h i c ha r eu s e do nw e b a p p l i c a t i o n t h e yc a l lt r a n s l a t et h eu s e rs e a r c hr e q u e s t sf o r w a r dt ot h e i rc o m p o n e n t s e a r c he n g i n e s ，a n dt h e nr e t u r nt h er e s u l t sc o l l e c t e df r o mt h e i r s c o m p o n e n ts e a r c h e n g i n e st ot h eu s e ra f t e rt h ec o m p l e xp r o c e s s t h i sd i s s e r t a t i o nw i l lg i v eat h o r o u g hd i s c u s s i o na b o u tt h eg e n e r a ls e a r c he n g i n e a n dm e t as e a r c he n g i n e t h ec r u c i a lt e c h n o l o g i e so ft h em e t as e a r c he n g i n e s ，s e a r c h r e s u l tr a n k i n ga n ds e a r c hr e s u l td e - d u p l i c a t e ，a r ca n a l y z e dd e e p l y t h em a i n w o r ka n dr e s e a r c ha c h i e v e m e n t sa r ea sf o l l o w s ： ( 1 ) b ya n a l y z i n gt h ef a c tt h a tt h eg o o dp e r f o r m a n c ec o m p o n e n ts e a r c he n g i n e c a nf m d g o o dq u a l i t yr e s u l t sa n dt h a tt h eg o o dq u a l i t yr e s u l t sc a nb ef o u n db yt h e g o o dp e r f o r m a n c ec o m p o n e n ts e a r c he n g i n e ，a n dr e f e r e n c i n gt h ei n t e r r e l a t i o n s h i po f t h ew e bp a g el i n k a g e ，t h ed i s s e r t a t i o ng i v e st h ec o n c e p to ft h eh u bv a l u eo ft h e c o m p o n e n ts e a r c he n g i n ea n dt h ea u t h o r i t yv a l u eo ft h es e a r c hr e s u l t s ( 2 ) n o t i c i n gt h a tt h eh u bv a l u eo ft h ec o m p o n e n ts e a r c he n g i n ec a nf l u c t u a t ei n o n es e a r c hp r o c e s s ，t h ed i s s e r t a t i o ng i v e st h ea l g o r i t h mo f u s i n gas e to fc e r t a i nt o p i c w o r d st oc a l c u l a t et h et o p i ch u bv a l u eo ft h ec o m p o n e n ts e a r c he n g i n e s ot h e d o m a i no ft h ec o m p o n e n ts e a r c he n g i n ei sd i v i d e da c c o r d i n gt ot h et o p i c f o ro n e c o m p o n e n ts e a r c he n g i n e ，d i f f e r e n tt o p i cf i e l d sc a l lb ed e s c r i b e db yd i f f e r e n tt o p i c h u bv a l u e s ( 3 ) t h ed i s s e r t a t i o nr a n k st h es e a r c hr e s u l t su s i n gt h et o ph u bv a l u e so ft h e c o m p o n e n ts e a r c he n g i n e ( t h ed i s s e r t a t i o na n a l y s e st w od e d u p l i c a t et e c h n o l o g i e s ：w e bp a g eb a s e da n d s e a r c hr e s u l tb a s e d ；t w ot y p e so fs u m m a r yd i s t i l lm e t h o d s ：s t a t i cm e t h o da n dd y n a m i c m e t h o d t h ed y n a m i cm e t h o du s i n gk e yw o r d sa r ea n a l y z e d t h ep h e n o m e n o nt h a t t h e r ea r em a n yc o m m o ns t a t e m e n ts e g m e n t sf o rt h es u m m a r i e sf r o mt h es e a r c hr e s u l t s e x t r a c t e df r o mt h er e p r i n tw e bp a g eo rt h es a m ew e bp a g ea r ea n a l y z e dt o o t h e h i a b s t r a c t d i s s e r t a t i o np r e s e n t st h ed e d u p l i c a t ea l g o r i t h mu s i n gt h es t a t e m e n ts e g m e n ts i m i l a r i t y d e g r e e t h ea l g o r i t h mc o n s t r u c t st h es t a t e m e n ts p a c ev e c t o r su s i n gt h es t a t e m e n t ss e t f r o mt h er e s u l ts u m m a r i e s ，a n dt h u sg e t st h es i m i l a r i t yo ft h e m ( 5 ) m e t a s e a r c h ，am e t as e a r c he n g i n es y s t e m ，i sw e l li m p l e m e n t e d i ts h o w s t h a t o u ra l g o r i t h m sa r ev a l i da n de f f e c t i v e k e yw o r d s m e t as e a r c he n g i n e ；s e a r c he n g i n e ；r e s u l tr a n k i n g ；r e s u l td e d u p l i c a t e 1 v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 虢拇新签名羞也嗍地 第1 幸绪论 1 1 研究背景 第1 章绪论 互联网最近的l o 多年发展中，互联网上的信息，尤其是w e b 资源的增长非 常迅速。据谷歌( g o o g l e ) 、雅虎( y a h o o ! ) 、c y b e r a t l a s 和麻省理工学院( m i t ) 等机构的估计，至2 0 0 7 年7 月，互联网上大约有7 1 0 亿个公众可以访问的静态 w e b 页面，有6 5 亿只限在内部网上访问的静态w e b 页面，另外还有深藏在数据 库中的超过2 2 0 0 亿的动态w e b 页面。据中国互联网络信息中心( c n n i c ) 的调查， 至2 0 0 5 年底，中国大陆( 不包括香港、澳门、台湾地区) 的网站拥有网页总数 约为2 4 亿个，网页总字节数约为6 3 9 3 2 g b 。另外，还有在线数据库约2 9 5 万个。 搜索引擎的使用频率成为仅次于电子邮件和新闻浏览的互联网应用服务。据调 查，截止到2 0 0 7 年底，中国搜索引擎用户达到了1 7 2 亿，中国搜索引擎单月的 搜索请求量已经突破1 1 0 亿。w e b 资源是互联网上最丰富的信息资源，而搜索引 擎是w e b 资源的索引，是使用w e b 资源的导航和指南。在浩如烟海的w e b 信息世 界中，如果没有搜索引擎的导航，那么对于w e b 资源的有效利用来说将是不可想 象的。然而，正是由于w e b 信息世界的浩瀚，任何一个搜索引擎在它面前都显得 渺小，其覆盖范围只占了整个w e b 世界的一小部分。据谷歌公司的披露和学者的 估计，2 0 0 4 年底，谷歌大约索引了8 0 亿个w e b 页面，到了2 0 0 7 年中期，谷歌 收录的w e b 网页达到了1 2 5 亿。这个数字离互联网上w e b 资源的总量还差得很远。 据学者估计，至2 0 0 7 年中期，被常用搜索引擎收录的网页还不足互联网上全部 网页的1 0 。 搜索引擎的出现已经大大提高了用户的搜索效率，但是在搜索结果质量、搜 索代价方面仍然达不了用户的要求。为了解决独立搜索引擎的覆盖率和检索质量 等问题，于是出现了元搜索引擎。 元搜索引擎不同于谷歌、百度等通用搜索引擎，它是建立在多个搜索引擎之 上的集成系统。它可汇集多个搜索弓l 擎的搜索结果，同时主动帮用户获取各大搜 索引擎最佳结果，并按重要性和热门程度有序排列，以保障结果精准而全面。元 搜索发展历史在国外已逾十年，尤其在美国，已为人们广泛认可和应用。2 0 0 7 年秋季一项主题为“t o pi 0w e bs e a r c he n g i n e s d i r e c t o r i e s 的调查中， 参加调查的北美用户评出了最喜欢的1 0 大搜索引擎。元搜索引擎v i v i s i m o 与雅 虎并列第二。由于元搜索引擎无需建立自己的庞大的索引数据库和复杂的检索机 制，维护起来比较容易，因此是目前解决通用搜索引擎存在问题的最佳方案，元 搜索技术也越来越成为计算机界研究的热点。 北京t 业大学t 学硕十学位论文 1 2 研究意义 1 2 1 传统搜索引擎的局限性 搜索引擎的出现从某种程度上来说，方便了用户从浩瀚的信息海洋中搜索感 兴趣的信息。但是用户在用搜索引擎进行信息搜索时，常常会发现大量重复或者 不相关的结果也被搜索引擎检索出来，浪费用户的时间和精力。而且，不同的搜 索引擎由于w e b 资源的覆盖范围和检索算法的不同，往往返回不同质量的结果， 用户为了获得更满意的结果，通常要在多个搜索引擎间切换。这些问题的产生主 要是由于通用搜索引擎自身的局限性： ( 1 ) 单个w e b 索引数据库的覆盖范围有限，信息查全率低。w e b 上的信息资 源是动态变化的，主要表现为信息量呈指数级增长，信息内容不断更新，信息存 放位置的不断变更等。任何一个通用搜索引擎都不可能覆盖w e b 上的所有网页信 息。 ( 2 ) 冗余重复信息量大。尽管现有的搜索引擎对搜索结果进行了一定的消重 处理，但是几乎每个搜索引擎都会搜索出重复的或者基本与查询不相关的结果， 用户只能人工从这些结果中发现自己需要的信息。 ( 3 ) w e b 索引数据库规模大，更新周期长。由于w e b 信息的爆炸性增长，通 用搜引擎要跟上w e b 信息的增长速度，w e b 索引数据库的规模就会不断增大，对 大规模索引数据库的维护是比较困难的。而且w e b 上信息的更新快，经常会导致 链接失效；并且对大容量的、非结构化或者半结构化的信息进行增加、删除和修 改也是索引数据库维护的一个难点。 ( 4 ) 客观条件的限制。单个搜索引擎的索引数据库的覆盖率，索引机器人的 性能，索引数据库的大小和系统维护开销等都限制了单个搜索引擎的发展。 1 2 2 元搜索引擎的优势 针对前一节讨论的通用搜索引擎存在的诸如w e b 资源覆盖率低，检索结果质 量不高等局限性，通常有以下2 个可供选择的解决方案： ( 1 ) 各个独立搜索引擎不断扩大自己的索引数据库的覆盖率，改进网页内容 的提取质量和索引的组织结构，对搜索结果的质量进行严格的控制。 ( 2 ) 元搜索引擎。它可以同时对多个成员搜索引擎进行查询，并将返回的多 个查询结果综合处理，从而在一定程度增加了搜索结果的覆盖率和查全率，提高 了搜索结果质量。 第1 种方案对独立搜索引擎的要求比较高，因为索引的速率要跟w e b 信息的 2 第1 章绪论 增长速度相匹配，基本是不可能的。也就是说在信息飞速增长的今天，通用搜索 引擎的索引数据库覆盖率只会慢慢降低，而且随着数据库规模的增大，对其进行 更新和维护也变得越来越困难，搜索结果质量的提高也变得不容易。 第2 种方案中的元搜索引擎介于用户和通用搜索引擎之间，因而更易于实现 更多处理服务。元搜索引擎无需建立自己的w e b 索引数据库，因而实现起来比较 容易，并且任何一个成员搜索引擎的检索数据库的更新，都会反映到元搜索引擎 上，因此搜索结果质量更好。本文对元搜索的关键技术进行了深入的研究。 1 3 研究内容 1 3 1 问题提出 在元搜索领域里主要关注的问题是如何能在有限的时间和空间内高效的对 各个成员搜索引擎返回的搜索结果进行排序，消重，提高用户对结果的满意度。 因此，可以把上述2 个问题的研究分成以下几点： ( 1 ) 如何对各个成员搜索引擎返回的各个搜索结果质量进行评价。 ( 2 ) 如何对各个成员搜索引擎的性能进行评价，进而用于它所返回结果质量 的评价。 ( 3 ) 如何挖掘搜索结果的摘要信息与查询关键词的关系，如何挖掘摘要对网 页特征性的表征能力。 ( 4 ) 如何在只获取网页标题，u r l 和摘要的情况下进行转载网页的处理，并 将算法控制在一定的空间与时间复杂度内。 1 3 2 研究方向 当前，元搜索技术还在发展之中，尚未成熟。许多研究机构和研究人员都 致力于元搜索关键技术的研究和实现。本文的主要工作如下： ( 1 ) 对搜索引擎与元搜索原理和特点进行了分析对比。 ( 2 ) 对搜索引擎的结果相关度计算方法和排序算法进行了分析对比。 ( 3 ) 讨论元搜索中成员搜索引擎与其返回结果的相互评价对偶关系，提出一 次查询中成员搜索引擎的h u b 值和搜索结果的a u t h o r i t y 的观念。 ( 4 ) 讨论元搜索中成员搜索引擎的主题敏感性，提出对搜索引擎按主题领域 划分进行性能评价，提出搜索引擎的主题h u b 值的概念，用于刻画成员搜索引擎 关于某个领域稳定的性能。 ( 5 ) 提出利用主题关联性强的词对搜索引擎的主题性能进行学习得到搜索引 北京t 业大学t 学硕i j 学位论文 i_ i= i 。皇曼曼皇曼曼曼! 曼曼曼曼曼! 曼曼! ! 曼曼曼曼曼曼曼曼曼! ! ! ! ! ! 曼曼曼曼曼曼曼! 曼! 皇曼曼曼曼曼曼曼曼曼曼曼曼 擎的主题h u b 值的方法。 ( 6 ) 利用搜索引擎的主题h u b 值对成员搜索引擎的返回结果进行相关度的计 算实现结果排序。 ( 7 ) 对传统的镜像网页和转载网页的消重算法进行了讨论。 ( 8 ) 针对搜索引擎的动态摘要技术进行分析，动态摘要技术能很好提取网页 对关键词的转载特征性。 ( 9 ) 对搜索结果的摘要进行分析，提出按照摘要语句相似度来判别网页之间 的转载关系。 ( 1 0 ) 给出基于摘要语句相似度的结果消重算法，并分析了时间空间复杂 度。 ( 1 1 ) 利用本文研究成果实现了一个元搜索系统m e t a s e a r c h ，对上述算法 的实验结果进行了分析讨论。 1 4 本文组织 法。 法。 论。 本文将按照以下结构进行组织： 第1 章为绪论，主要介绍课题的背景、研究现状、研究内容和研究意义。 第2 章概述搜索引擎和元搜索，特别分析了元搜索的关键技术。 第3 章元搜索结果排序研究并提出基于搜索引擎主题h u b 值的结果排序算 第4 章元搜索结果消重研究并提出基于结果摘要的语句相似度的结果消重算 第5 章是m e t a s e a r c h 系统的实现，并对上述算法的实验结果进行了分析讨 最后对全文进行总结，并对今后的研究工作进行展望。 4 第2 审搜索引擎弓元搜索 2 1 搜索引擎 第2 章搜索引擎与元搜索 2 1 1 搜索引擎与互联网 上世纪九十年代以来，互联网迅猛发展，w e b 信息爆炸式增长。用户要在互 联网的信息海洋里查找感兴趣的信息，就像大海捞针一样。搜索引擎的出现恰好 解决了这个难题。目前搜索引擎可以为用户提供互联网信息检索服务，并正成为 计算机工业界和学术界争相研究的对象。搜索引擎最早出现于1 9 9 4 年，m m a u l d i n 将j l e a v i t t 的爬行器接入到其索引程序中，创建了l y c o s 。同年，斯 坦福大学的2 名博士生d f i l o 和杨致远( g e r r yy a n g ) 共同创办了超级目录索 引雅虎( y a h o o ! ) ，从此搜索引擎进入了高速的发展阶段。1 9 9 8 年斯坦福大学 研究人员在其实验型搜索引擎的基础上构建了谷歌搜索引擎。谷歌多年被用户评 为最受欢迎的搜索引擎，它的网页索引数量达到3 0 亿之多，响应速度和结果的 质量好于其它搜索引擎。该搜索引擎的关键技术有p a g e r a n k 技术和超文本匹配 分析技术h m a ( h y p e r t e x t m a t c h i n ga n a l y s i s ) 。p a g e r a n k 技术基于链接分析 理论，通过对所有爬行网页做超链分析，计算出网页的重要性。这种重要性是由 其它网页来确定的，不像其它搜索引擎是基于网页自身的文字内容，这使得网站 本身很难操纵自己的排名，使网页排序更加客观和准确。检索系统采用i b l a 技术 来计算查询词与网页之间的相关度。当用户提交查询的时候，系统就能将最相关、 最重要的网页返回给用户。 目前的搜索引擎大致可以分为4 类：目录搜索引擎，机器人搜索引擎，元 搜索引擎和垂直搜索引擎。 ( 1 ) 目录搜索引擎主要依靠人工维护网站索引，它虽然有搜索功能，但在严 格意义上算不上是真正的搜索引擎，仅仅是按目录分类的网站链接列表而已。用 户完全可以不用关键词查询，仅靠分类目录也可能找到需要的信息。国外比较著 名的目录搜索引擎有雅虎、o p e nd i r e c t o r yp r o j e c t 、l o o k s m a r t 等；国内的搜 狐、新浪、网易搜索也都具有这一类功能。目录式搜索引擎通过人工浏览各站点 的信息，按照一定的分类规则或分类体系，对网站进行分类。它的优势在于内容 比较好的站点更容易被编辑所认同，更容易被索引，所以它的索引质量比较高。 目录式搜索引擎分类结构清晰，错误较少，比较符合人们的阅读习惯。缺点是人 工工作量大，整理周期长，速度慢，人工干预成份多，不能适应w e b 资源的规模 发展。 北京t 业入学t 学硕十学位论文 曼皇曼皇曼曼曼量曼曼鼍i- - , i 曼曼曼曼曼曼曼曼 ( 2 ) 机器人搜索引擎是名副其实的搜索引擎，国外代表性的有谷歌，雅虎、 l i v e 搜索等；国内代表性的有百度、中搜等。它们都是通过从互联网上提取的 各个网站的网页信息而建立的w e b 索引数据库，检索与用户查询条件匹配的相关 结果，然后按一定的排列规则将结果返回给用户。 ( 3 ) 元搜索引擎是指在统一的用户查询界面与信息反馈形式下，利用多个成 员搜索引擎的w e b 索引数据库为用户提供检索服务的系统。元搜索引擎的最大特 点是没有自己的索引数据库，只提供一个统一的检索界面。当用户向元搜索引擎 提交查询式时，它将该查询表达式翻译成相对应的成员搜索引擎查询表达式并分 别发送出去，然后它接收各个搜索引擎的检索结果，按照一定的处理规则，将结 果返回给晟终用户。元搜索引擎的优势在于用户不需要知道不同搜索引擎的网络 地址和查询语法就能查询多个w e b 索引数据库，可以大大提高查询结果的覆盖 率。由于它不用维护庞大的索引数据库，而将工作重心放在检索结果的整合上， 可以更好地提高查询结果的满意度。但是元搜索引擎的网络资源开销比较大，从 多个搜索引擎返回的结果中常常有很多重复信息，重新排序比较困难。 国外著名的元搜索引擎有d o g p i l e 、v i v i s i m o 等；国内的元搜索引擎中具代 表性的有搜星、优客搜索等。在搜索结果排列规则方面，有的直接按成员引擎排 列搜索结果，如d o g p i l e ：有的则按特定的规则将结果重新排列组合，如 v i v i s i m o 。 ( 4 ) 垂直搜索引擎n 2 1 是搜索引擎最新的研究领域。大多数搜索引擎在满足搜 索结果全面性要求的同时难以兼顾专业性的要求。垂直搜索引擎面向特定领域， 专注于自己的特长，保证了对该领域信息的完全收录与及时更新。与通用搜索引 擎不同，垂直搜索的目标是尽可能多地搜集与某类主题相关的网页。专业网络蜘 蛛抓取到的网页如果与预定义主题相关，就做进一步的处理；如果不相关，则抛 弃该网页。这样处理的结果是：检索数据库最终只索引了w e b 上所有网页的一部 分，也就是与预定义主题相关的网页。这样处理的好处是可以节省大量的存储空 间和具有较高的更新频率。在较短的时间内就可以把主题领域内的网页全部更新 一遍，这样能够跟上互联网上w e b 信息的变化，而且对用户而言，如果它对该主 题感兴趣，那么该搜索引擎在该领域的信息是最优的。 这4 种搜索引擎各有优缺点，在不同的领域有不同的应用。目录式搜索引擎 和全文检索搜索引擎现在己经紧密结合在一起，如谷歌、北大天网等，它们在机 器人搜索引擎的基础上，提供目录服务。没有全文检索搜索引擎也就没有元搜索 引擎。这些搜索引擎技术可以互为补充，不会出现一种搜索引擎完全取代另一种 的局面。 212 搜索引擎原理 陶2 - 1 以谷歌“1 为例，描述了个典型的机器人搜索引擎系统架构。 图2l 谷歌的系统结十勾幽 f i g u r e 2 - 1a r c h i t e c t u r e o f g o o g l e 搜索引擎的各组成部分柑互交错相互依赖。机器人搜索引擎的实现可以归 结为4 个步骤： ( 1 ) 从互联网上抓取网页。利用能够从互联网上自动收集网页的网络爬行器 程序，自动访问互联网，并沿着任何网页中的任何u r l 爬行到其它网页，起初的 u r l 并不多，随着信息采集量的增加，也就是分析到网页有新的链接，就会把新 的u r l 添加到u r l 列表，以便继续采集网页。重复以卜过程，并把爬过的所有网 页收集到服务器中。 ( 2 ) 建立索引数据库。由索引系统程序对收集回来的网页进行分析，提取网 贞信息( 包括网页所在u r l 、编码类型、网页内容包含的关键词、关键词位置、 生成时间、网页大小、与其它网页的链接关系等) ，根据一定的相关度算法进行 大量复杂计算，得到每一个网页针对网页内容中及链接中每一个关键词的相关性 ( 或重要性) ，然后用这些相关信息建立网页索引数据库。 ( 3 ) 在索引数据库中搜索网页。当用户输入关键词进行搜索时，分解搜索请 北京t 业大学丁学硕卜学位论文 求，由搜索系统程序从网页索引数据库中找到所有与该关键词相关的网页。 “) 对搜索结果进行排序处理。所有相关网页针对该关键词的相关信息在索 引库中都有记录，只需综合相关信息和网页级别形成相关度数值，然后进行排序， 相关度越高，位置越靠前。最后由网页生成系统将搜索结果的链接地址和网页内 容摘要等组织起来返回给用户。 2 2 元搜索概述 因为任何一个通用的搜索引擎都无法覆盖所有的w e b 信息资源，而且对于同 一个查询请求，不同的搜索引擎因其工作机制的不同，得到的结果中重复率也较 低。因此在很多情况下人们为了获得更高的覆盖率和查全率，需要同时使用具有 不同w e b 覆盖范围的多个搜索引擎，元搜索引擎就是在这种情况下诞生并发展起 来的。自1 9 9 5 年华盛顿大学硕士生e r i cs e l b e r g 和o r e ne t z i o n i 推出第一 个元搜索引擎m e t a c r a w l e r 以来，这一新型的网络检索工具异军突起，发展迅速。 目前可用的元搜索引擎己近百种。尽管元搜索引擎也存在响应速度慢等缺陷，但 它以涵盖较多的w e b 资源，能够在尽可能短的时间内提供相对全面、准确的搜索 结果等诸多优异功能而受到用户的青睐，已逐渐成为一种功能强大并极具潜力的 网络检索工具。以下为一些知名的中文和英文元搜索： ( 1 ) 万纬( h t t p w w w w i d e w a y s e a r c h c o m ) 这是上海万纬信息技术有限公司 开发的一个中文元搜索引擎，它能并行搜索国内外多个著名的搜索引擎，支持简 单搜索和高级搜索，是目前国内较好的中文元搜索引擎。 ( 2 ) 搜星( h t t p ：w 唧s o s e e n c o m ) 为中文元搜索引擎，可以调用谷歌、百度、 搜狐、新浪和t o m 等著名引擎进行广泛搜索，可搜索精选网址，其搜索结果可以 过滤掉重复的网站，并将结果用同样的格式反馈在同一个网页。主页还设有精选 网址分类、全国省市网址等，便于进行分类搜索。 ( 3 ) d o g p i l e ( h t t p ：w w w d o g p i l e c o m ) 是国外的一个并行式元搜索引擎。 它可调用6 个著名独立搜索引擎，提供综合式的检索服务，检索内容包括网页、图 像、声音、视频、新闻等。它支持一般检索、高级检索、布尔检索、短语检索、 限制检索等。 ( 4 ) m e t a c r a w l e r ( h t t p ：唧m e t a c r a w l e r c o r n ) 于1 9 9 5 年由华盛顿大学的 科技人员创建，它支持调用7 个独立搜索引擎，提供涵盖近2 0 个主题的目录检 索服务。其检索特性非常丰富，包括一般检索、高级检索、定制检索、国家或地 区的资源检索等检索服务模式。其中通过高级检索模式可实现：搜索引擎的选择 调用，基于域名、地区或国家的检索结果过滤，最长检索时间设置，每页可显示 的和允许每个搜索引擎返回的检索结果数量的设定，设定检索结果排序依据( 包 第2 章搜索弓f 警j 兀搜索 括相关度、源搜索引擎) 等。以上内容均可作为定制检索的个性化选项并予以保 存。 ( 5 ) m a m m a ( h t t p ：w w w m a m m a c o m ) 于1 9 9 6 年面世，自称为“搜索引擎之母 的并行元搜索引擎。它可同时调用1 4 个独立搜索引擎，并且可查询网上商店、 新闻、股票指数、图像和声音文件等资源。特点是检索界面友好，检索选项丰富， 主要包括：可控制调用的独立搜索引擎，选择使用短语检索功能，设定检索时间， 设定每页可显示记录数等。另外，m a m m a 支持常用检索语法在不同搜索引擎中的 转换，还提供了专门检索网页文件标题的特殊检索服务，以及通过e - m a i l 传输 检索结果的特色功能。 ( 6 ) s e a r c h c o m ( h t t p ：w w w s e a r c h c o m ) 汇集了多个搜索引擎或指南。内 容涉及新闻、软件、新闻组等5 0 个主题范畴，一次可以并行调用5 个搜索引擎。 检索方式分简单检索和高级检索。支持布尔逻辑检索、短语检索等，检索结果按 相关性排序。 ( 7 ) v i v i s i m o ( h t t p ：w w w v i v i s i m o c o m ) 调用多种搜索引擎，并对返回的 结果自动分类，界面友好，简单易用。它被搜索引擎观察评为2 0 0 2 年最佳 元搜索引擎。 2 2 1 元搜索原理 元搜索引擎可看成具有双层客户机服务器结构的系统。用户向元搜索引擎 发出检索请求；元搜索引擎再根据该请求向多个搜索引擎发出实际检索请求；搜 索引擎执行元搜索引擎检索请求后将检索结果以应答形式传送给元搜索引擎；元 搜索引擎将获得的检索结果经过整理再以应答形式传送给用户。当然，一些元搜 索引擎还具有其它的特点。如图2 - 2 所示，一个真正的元搜索引擎由3 部分组成， 即检索请求代理、成员引擎代理、结果显示代理。 ( 1 ) 检索请求代理负责实现用户“个性化”的检索设置要求，主要包括调用 哪些搜索引擎、检索时间限制、结果数量限制等。 ( 2 ) 成员引擎代理负责将用户的检索请求“翻译”为成员搜索引擎“本地化” 要求的查询格式。 ( 3 ) 结果显示代理负责对所有成员搜索引擎检索的结果进行汇集、筛选、去 重、合并等优化处理后，以统一的格式在同一界面显示。 北京t 业人学t 学硕十学位论文 i 成员引擎 图2 2 兀搜索的组成 f i g u r e2 - 2a r c h i t e c t u r eo fm e t as e a r c he n g i n e 元搜索引擎虽然没有网页采集机制，也无独立的索引数据库，但在检索请求 代理、成员引擎代理和结果显示代理等方面，均有自己研发的特色元搜索技术支 持。如提交检索请求时，根据成员搜索引擎的特点和技术参数，指定优先顺序， 并对检索时间、检索结果数量进行控制；作为若干成员搜索引擎的检索请求代理， 必须具备较强的字符和语法转换功能，使用户的检索请求为各具语法格式的不同 成员搜索引擎所接受；而对检索结果的显示，不同的元搜索引擎有不同的处理技 术。由于元搜索引擎设定的检索结果排序依据、最大返回结果数量、相关度参数 及优化机制等不同，调用相同的成员搜索引擎的不同元搜索引擎显示检索结果的 数量多少，排序先后，结果信息描述选择也有较大差异。 2 2 2 元搜索的分类 元搜索引擎有多种分类方式，如根据用户功能模式，调用成员搜索引擎的方 式等。按功能划分，元搜索引擎包括集成搜索引擎和多线索式搜索引擎；按运行 方式可分为桌面型元搜索引擎和基于w e b 的元搜索引擎；按照工作方式可分为并 行处理式和串行处理式。 ( 1 ) 集成搜索引擎( a 1 1 i n o n es e a r c hp a g e ) ，也称为“多引擎同步检索系 第2 荦搜索引擎与兀搜索 统( 如生命家园网) 是指搜索引擎界面上以任意顺序或分类罗列多个搜索引擎， 搜索引擎本身主要提供各类搜索引擎的介绍信息和网络链接。这类元搜索引擎没 有统一的全局外部模式，而是以各搜索引擎的检索模式和数据格式直接面对用 户，即直接把来自多个搜索引擎的搜索结果列在一个网页上，不做重新计算或更 改。其实质是利用网页链接技术形成的搜索引擎集合。严格来说，这类元搜索引 擎只是成员搜索引擎的罗列，不能算真正意义上的元搜索引擎。集成搜索引擎不 需自建数据库，不需研发支持技术，当然也不能控制和优化检索结果。但集成搜 索引擎制作与维护技术简单，可随时对所链接的搜索引擎进行增删调整和及时更 新，尤其大规模专业( 如f l a s h 、m p 3 等) 搜索引擎集成链接，深受特定用户群欢 迎。典型的集成搜索引擎有搜星、生命家园网、搜索之家、p r o t e u s 和q u e r y s t e r 在占 于。 ( 2 ) 多线索式元搜索指利用统一的检索界面，实现对多个成员搜索引擎索引 数据库进行检索，并将检索结果以统一格式显示的网络检索工具。这类元搜索引 擎具有以下特征。统一检索界面：元搜索引擎提供统一界面，提供对各搜索引擎 特点介绍和选择机制，但所有成员搜索引擎构成一个逻辑整体，元搜索引擎检索 界面构成唯一的全局外部检索模式，用户通过这个全局界面实现对多个或任意一 个搜索引擎的检索。检索指令转换：在具有唯一全局外部检索模式情况下，系统 可提供统一的全局指令语言，并自动地实现元搜索引擎指令与其成员搜索引擎指 令的转换，用户使用同一指令语言检索不同的搜索引擎的索引数据库。统一结果 集的组织与显示：元搜索引擎提供全局组织机制，对各成员搜索引擎返回的结果 进行处理，形成全局结果集，并以统一格式显示，主要涉及数据格式转换、去重、 统一排序等。典型的多线索式元搜索引擎有万纬搜索、m e t a f i s h e r 、m e t a c r a w l e r 和d o g p i l e 等。 ( 3 ) 桌面型元搜索以桌面程序的方式提供用户服务，相当于用户自己拥有一 个元搜索引擎。它运行在用户的机器上，用户的查询请求直接由用户端分发给它 所调用的搜索引擎，然后对返回的搜索结果进行集成后以一定的方式显示。桌面 型元搜索引擎是一个包括多个成员搜索引擎的完整系统，它们往往允许用户自定 义检索式运行的搜索引擎集合( 例如一个或全部成员搜索引擎) ，甚至可由用户添 加新的搜索引擎。这些桌面型元搜索引擎不仅可以实现对多个搜索引擎的并行检 索，而且也能提供重要的后期处理功能，例如用户定义结果排序方式，删除重复 记录等功能。典型的桌面型元搜索有飓风搜索通。 ( 4 ) 基于w e b 的元搜索引擎。基于w e b 的元搜索引擎以w e b 方式为用户提供 元搜索服务。请求代理、检索接口代理和结果显示代理都存放在元搜索引擎所在 的服务器端。在这种方式中，用户的查询请求经过服务器端的请求提交代理和检 索接口代理分发给它所调用的成员搜索引擎。这些成员搜索引擎返回的搜索结 北京t 业大学t 学硕卜学位论文 果，由服务器端的结果显示代理处理后再返回给用户。 ( 5 ) 并行处理式元搜索引擎将用户的查询请求同时转发给它调用链接的多个 成员搜索引擎进行查询处理。串行处理式元搜索引擎将用户的查询请求依次转发 给它调用链接的每一个成员搜索引擎进行查询处理。 2 2 3 元搜索的特点 ( 1 ) 元搜索提高了用户检索质量。元搜索可以同时调度多个成员搜索引 擎，可以方便检索多个网页检索数据库。一般搜索引擎的检索范围仅局限于 t l 身的数据库，各个独立的成员搜索引擎因为定位关注不同从而网页覆盖范 围千差万别。即使是世界上功能最强大的搜索引擎，其网页检索数据库也只 是涵盖了不到世界上1 3 的网页。同时，由于不同搜索引擎自身的网页收集 范围、方式和相关度计算方法不同，同一检索表达式会得到大不相同的结果。 元搜索可以自动向成员搜索引擎索取结果，在短时间内把多个引擎的结果返 回给用户。元搜索有效屏蔽了各个成员搜索引擎的接口等实现细节，避免用 户在多个引擎系统之间切换和查询请求的格式转换。元搜索不仅仅提高了检 索的覆盖面，而且提高了用户的检索效率。 ( 2 ) 元搜索的可扩展性强，可以实现个性化搜索。个性化搜索更为复杂， 它要求搜索引擎构建用户的兴趣模型，对用户的兴趣进行挖掘学习，并以此 来对结果进行处理。这样的个性化搜索可以基于服务器端也可以基于客户 端。基于服务器端的个性化搜索能够追踪用户以前的查询和访问过的网页， 以此来推测兴趣。基于客户端的个性化搜索能追踪用户的浏览特征等更细节 的信息，以此来捕获用户兴趣。 ( 3 ) 元搜索系统实现复杂度低。元搜索引擎可以有也可以没有自己的数 据库。它是具有智能的中间代理，用户只需要提交一次搜索请求，由元搜索 引擎负责转换处理后，提交给多个预先选定的成员搜索引擎，并将成员搜索 引擎返回的所有结果集中起来，进行不同层次的处理( 删除重复结果，结果 排序) 后，做为自己的结果返回给用户，最后为用户提供一个统一的界面。 ( 4 ) 元搜索检索时间有时过长，响应时间不够理想。由于元搜索一次要 访问多个成员搜索引擎，要将用户的检索请求转化处理后提交给多个成员搜 索引擎，并将结果收集起来进行处理，然后呈现给用户。一般可以采用并行、 分布等一系列的优化运行机制，能够尽可能缩短响应时间。 ( 5 ) 元搜索对搜索结果的排序不够理想。典型的搜索引擎是基于查询时 关键词所在网页中的词条对网页进行排序的，不同的成员搜索引擎采用了不 同的网页相关度评价体系。由于一般元搜索无法获取成员搜索引擎的网页检 第2 章搜索引警与元搜索 索数据库中词条的词频等统计信息，并且搜索结果可供用于的排序的信