（管理科学与工程专业论文）个性化元搜索引擎若干关键技术研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 目前主要的搜索引擎的查准率都不高，且不同的搜索引擎返回的结果也不尽 相同，所以要想获得一个比较全面准确结果，就必须反复调用多个搜索引擎。元 搜索引擎的出现，在一定程度上解决了这些问题，这也使得元搜索引擎得到了较 为迅速的发展。另外，每个用户的兴趣爱好都不同，搜索的侧重点也不同，现有 搜索引擎千篇一律的查询结果已经无法满足用户的个性化需求。因此，个性化搜 索成为了当前的研究热点。 元搜索引擎能够集成利用多个成员搜索引擎，提高搜索的覆盖范围，使信息 查全率大大提高；个性化搜索能够有效满足用户的个性需求，寻找与用户最相关 的信息，使搜索引擎的查准率得到提高。个性化元搜索引擎结合两种技术的优点， 是改善现有搜索引擎不足的有效途径。 本文首先对元搜索引擎和个性化技术进行了概述，总结了元搜索引擎技术和 个性化技术的研究现状和发展趋势，综述了相关理论和技术。然后对实现个性化 元搜索引擎的相关理论、技术进行了深入研究和对比分析。在此基础上，提出了 实现个性化元搜索的相关算法。其中，针对用户查询的个性化需求，建立了基于 分类层次模型的用户兴趣模型，提出了用户兴趣树的建立算法，并基于隐反馈的 方式，提出了3 种用户模型的更新算法。针对结果合成处理，引入了决策理论， 提出了基于偏好选举法的查询结果排序算法，该算法考虑了查询结果在各成员搜 索引擎结果中的的位置信息，能够较好地将进行合并处理，满足用户的查询需求。 最后，设计并实现了原型系统，对提出的理论和算法进行了实验验证，并分析了 实验数据。 主题词：信息检索元搜索引擎个性化搜索用户兴趣模型结果合并 第i 页 国防科学技术大学研究生院硕士学位论文 a b s 丁r a c t t h ea v e r a g ep r e c i s i o no fs o m ef a m o u ss e a r c he n g i n e si sn o th i g he n o u g hc u r r e n t l y w h a t sm o r e ，d i f f e r e n ts e a r c he n g i n eg i v e sy o ud i f f e r e n tr e s u l t s oi fo n ew a n t st og e t m o r ec o m p r e h e n s i v e ，v e r a c i o u sr e t r i e v e di n f o r m a t i o n ，h em u s tu s el o t so fs e a r c h e n g i n e s t h e nt h em e t a - s e a r c he n g i n es y s t e mh a sb e e nd e s i g n e da n dr e s o l v e st h i s p r o b l e mi ns o m ew a ya n dt h i sg i v em e t a - s e a r c he n g i n ear a p i dd e v e l o p m e n t i n a d d i t i o n ，e v e r y o n e si n t e r e s t sa r en o tt h es a m e ，a sw h a tt h e ye m p h a s i z e do n e x i s t i n g s e a r c he n g i n ec a n ts a t i s f yu s e r sf o rt h e yc a no n l yr e t u r nt h es a m er e s u l t sf o re v e r y o n e s s e a r c h s o ，p e r s o n a l i z e ds e a r c hb e c o m e st h eh o tp o i n to fi n f o r m a t i o nr e t r i e v a lr e s e a r c h t h em e t as e a r c he n g i n ea d o p t sm a n ys e a r c he n g i n e s q u e r ya b i l i t yt oe n l a r g et h e s c o p eo fs e a r c h i n g t h ep e r s o n a l i z e ds e a r c hc a ns a t i s f yt h eu s e r sp e r s o n a l i z e dn e e d t h r o u g hp r o v i d i n gt h em o s tr e l e v a n ti n f o r m a t i o n ap e r s o n a l i z e dm e t as e a r c he n g i n e c o m b i n e st h ea d v a n t a g e so ft h e s et w ot e c h n o l o g i e sa n d p r o v i d e sa ne f f e c t i v em e t h o dt o i m p r o v et h es e a r c he n g i n e sq u e r y i n ga b i l i t y t h es t a t e - o f - t h e a r to fm e t as e a r c he n g i n e si sf i r s t l yo v e r v i e w e da sw e l la st h a to f p e r s o n a l i z e ds e a r c h as u m m a r yo fm e t as e a r c ha n dp e r s o n a l i z e ds e a r c h ss t a t u sq u oi s m a d e t h er e v i e wo fi n t e r r e l a t e dt h e o r i e sa n da l g o r i t h m sa r er e s e a r c h e d t h e nt h e a n a l y s e sa n dc o m p a r i s o n so fp e r s o n a l i z e ds e a r c ht h e o r i e sa n dt e c h n i q u e st h a th a v e b e e n p r o p o s e df o rp e r s o n a l i z e dm e t as e a r c he n g i n e sa r ep r o v i d e a f t e r w a r d s ，b a s e do nt h e r e s e a r c h e s ，w ep r o p o s es e v e r a la l g o r i t h m sf o r t h ei m p l e m e n to fp e r s o n a l i z e dm e t a s e a r c h f o c u s0 nt h eu s e r sp e r s o n a l i z e dd e m a n d ，au s e ri n t e r e s tm o d e lb a s e do n c l a s s i f i e dh i b e r a r c h ym o d e li se s t a b l i s h e d a n d ，t h r e ea l g o r i t h m so ne s t a b l i s ha n d u p d a t eo fu s e ri n t e r e s tm o d e l a r ep r o p o s e d f o c u so nt h er e s u l tm e r g i n g ，a na l g o r i t h mo f r e s u l t sm e r g i n gb a s e do nb o r d af u n c t i o no fd e c i s i o n m a k i n gt h e o r yi sp r o p o s e dw h i c h c a nm e r g i n gt h er e s u l t sf r o mm e m b e rs e a r c he n g i n e sw e l la n ds a t i s f i e dt h eu s e r d e m a n d s f i n a l l y ，d e s i g na n di m p l e m e n to fap r o t o t y p es y s t e ma r ee x p l a i n e d a n do ni t ，a v a r i e t yo fe x p e r i m e n t sh a v e b e e nc a r r i e do u t t h ea n a l y s i so fe x p e r i m e n t a ld a t a i n d i c a t e so u rm e t h o d sa r ee f f e c t i v e k e yw o r d s ：i n f o r m a t i o nr e t r i e v a l ，m e t as e a r c he n g i n e ，p e r s o n a l i z e ds e a r c h ， u s e ri n t e r e s tm o d e l ，r e s u l tm e r g i n g 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表3 1 各种用户行为的分类2 9 表3 2 查询结果得分表4 5 表3 3 成员搜索引擎权重表4 6 表3 4 查询结果最终得分表4 6 表4 1 兴趣参考模型表设计5 2 表4 2 用户基本信息表设计5 2 表4 3 查询结果表设计5 2 表4 4 成员搜索引擎信息表设计5 2 表4 5 用户兴趣表设计：5 3 表4 6 成员搜索引擎偏好表5 3 表4 7s p r i n g s u n 的初始兴趣类别和权重5 5 表4 8 对比测试实验结果5 8 表a 1 兴趣分类参考模型表7 1 第1 i i 页 国防科学技术大学研究生院硕士学位论文 图2 1 图2 2 图3 1 图3 2 图3 3 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 11 图4 1 2 图4 1 3 图目录 搜索引擎基本结构7 元搜索引擎的结构示意图9 用户兴趣树2 5 用户模型更新流程2 7 基于用户查询结果反馈的更新过程示意图3 2 系统总体结构4 8 系统工作图5 0 数据库e r 图。5 1 系统起始页面5 3 用户注册兴趣界面5 4 对“微软 进行个性化搜索的结果5 4 各兴趣类别下特征词统计图5 6 用户兴趣树内各个兴趣类别下的特征词与类别的从属度统计图5 6 用户兴趣类别权重比重变化图5 7 查询意图分析正确率统计图5 7 g o o g l e 对“李宁”的查询结果5 9 比比猫元搜索引擎对“李宁”的查询结果：5 9 p m e 对“李宁”的查询结果6 0 第1 v 页 独创性声明 本人声鼙；l 斯显突的学位论文楚我本人在导姊指导下进行的研究工律及取褥 的磷窀戎暴，尽我所知，除了文中特别如以标；圭和致谢的地方外，论文中苇包含 其缝人已经跫泰和撰写过的辑宠蔽聚，也不包含为获 蓦国防科学技术大学戏箕它 教育撬扮的学控或近参褥健镶过酶材 哮与我一嗣工作约河志对本研究所敛的任 蟛霓敞均已在论文申f # 了明确的说明并采示谢意 学位论文题强： 全蝰氇垂壁塞蔓i 鍪整至蕊整整塞塑登 学泣论文f # 音签名：j 囱辞杠 疆期：沙谚年f 月 日 学位论文版权使用授权书 本入党全了解国防科学技恭大学离关保留、使用学位论文的规定。本人授投 匿防辩学技术大学霹缀保留并向国家有关部门或概构送交论文的：踅印件和电予 文档免 蔓论文披查溪! 和港阕；可以将学位论文的全部或部分内容缟入有关数据 摩避，彳检索，可敬采躅彩带、缩印或扫描等复制手段傈存、汇缡学位论文。 ( 探密学位论文盔鬈密詹适用本授权譬，) 学位论文作者签名： 作者搔导教簿签骞： 日期：2 一，口岔年f 2 题 霉期：刃泸从明 馁 嚣 弦j 国防科学技术大学研究生院硕士学位论文 第一章绪论 近年来，随着计算机技术和网络技术的飞速发展，互联网成为人们生活中不 可缺少的组成部分，在互联网中查找信息更是人们使用互联网的重要目的。因此， 搜索引擎成为了现在研究的热点和重点。本章综述了相关研究背景，分析了传统 搜索引擎的缺点，引出了元搜索引擎的概念。本章还阐述了本文研究的主要内容， 并给出了文章的组织结构。 1 1 研究背景 i n t e m e t 自诞生以来，特别是从二十世纪九十年代末以来得到了迅猛发展，功 能不断扩展，信息容量呈爆炸性趋势增长。根据著名i n t e m e t 服务公司n e t c r a f t 的 统计【l 】，截至2 0 0 8 年8 月，i n t e m e t 上共有约l 亿7 千万个网站。中国互联网信息 中心( c n n i c ) 的第2 2 次中国互联网络发展状况统计报告【2 】中指出，截至2 0 0 8 年7 月，中国共有网站1 9 1 9 万个，年增长率为4 6 3 。i n t e r n e t 作为一个信息平 台在人们的生活和工作中发挥着越来越重要的作用。 i n t e m e t 上面有众多的服务和应用，但获取信息一直是用户上网的重要目的。 在i n t e r n e t 上获取信息的一种普遍方式是通过浏览器浏览网页，通过网页的超链接 来寻找所需信息的网页。但i n t e r n e t 上的信息量过于庞大，并具有变化较快等特点， 且没有一个权威机构对这些信息进行全面的整理和归类，这往往使用户面对五花 八门的各种各样的信息摸不到头脑，不知道如何快速有效地获取自己所需的信息， 陷入了“信息过载”和“信息迷航”的困境。因此，对于在i n t e m e t 上查找信息的 用户来说，功能强大、效率更高的信息检索工具的出现显得极为重要。 信息检索( i n f o r m a t i o nr e t r i e v e ) 一直是计算机研究中一个重要的方向，i n t e m e t 的迅猛发展使网络环境下的信息检索更是成为了个新的研究热点。各国的研究 者已经做了大量的工作，力图开发出高效、智能的信息检索工具，以使用户能够 更加方便、快捷地获取所需信息。在1 9 9 4 年，i n t e m e t 上出现了真正现代意义上的 搜索引擎l y c o s 。搜索引擎的出现大大增强了人们寻找和收集信息的能力，搜索引 擎通过收集众多的网络站点来提供全局性网络资源控制与检索机制，可以帮助用 户更好地在i n t e m e t 中寻找自己所需的信息。根据i r e s e a r c h ( 艾瑞市场咨询中 国网络经济研究中心) 的研究【3 】预测，截至2 0 0 6 年底，中国每天使用搜索引擎的 用户数量已到9 5 2 0 万人，每个用户日均使用7 7 次搜索引擎；而到2 0 1 0 年底，每 天使用搜索引擎的用户数将近2 亿人，用户日均使用搜索引擎次数将达1 2 1 次。 到目前，i n t e m e t 上出现了许多方便和帮助用户查找所需信息的搜索引擎，如 第1 页 国防科学技术大学研究生院硕十学位论文 g o o g l e 、y a h o o 、s o g o u 、a l t a v i s t a 、e x c i t e 、l y c o s 、百度等。 随着i n t e m e t 网络的普及和迅猛发展，信息膨胀的速度远远超过了搜索引擎检 索范围的扩展速度，搜索引擎对i n t e m e t 建立索引的能力受到越来越严峻的考验。 事实上，以今天i n t e m e t 的规模和发展速度，没有一个搜索引擎能够全面覆盖w e b 的文档。文献 4 】中指出，覆盖率最高的g o o g l e 覆盖了网络上约7 0 的页面；在中 文网页方面，清华大学i t 可用性实验室2 0 0 5 年1 0 月发布的报告【5 】显示，中文搜 索引擎对中文网页样本覆盖率最高的百度只有3 2 5 2 的网络资源覆盖率。2 0 0 8 年， 搜索引擎巨头g o o g l e 宣称其在网络上发现的页面数已达到一万亿之多，但仅索引 了其中约4 0 0 亿个页面；y a h o o 、s o g o u 等国内外搜索引擎也声称已索引1 0 0 亿的 页面，整体覆盖率呈降低趋势。同时，不同的搜索引擎的查询结果的重复率仅在 1 0 左右1 6 】。因而，仅使用一个搜索引擎用户很难找到自己所需的全部信息，必须 同时使用多个搜索引擎进行搜索，并在各结果列表中挑选对自己有用的信息。而 且，对于一个普通的查询，搜索引擎一般都会返回数以万计的查询结果，其中相 关信息和无关信息混杂在一起。根据统计，用户不需要的信息所占的比例高达7 5 以上，用户不得不逐个浏览各项查询结果，找到自己真正需要的信息如同大海捞 针一样困难。 出于以上所述的原因，一个能集成多个搜索引擎查询结果并能对此做整合处 理的检索工具元搜索引擎出现了。元搜索引擎产生于二十世纪9 0 年代中期， 定位于解决独立搜索引擎信息覆盖率不足和查准率不高的缺点，并在这短短的十 多年左右的时间里获得迅速发展。 搜索引擎技术相关领域的学术研究得到了大学和科研机构的重视。著名的国 际信息检索会议t r e c 从1 9 9 8 年开始增加了w e bt r a c k 课题，以考察w e b 文档与 其它类型文档在检索性质上的不同之处，并在大规模的w e b 库上对信息检索的算 法性能进行测试。由美国i n f o m o t i e s 公司主办的搜索引擎国际会议从1 9 9 6 年开始 每年举行一次研讨会，对搜索引擎技术进行总结、讨论和展望。由i e e e 主办的国 际万维网会议、人机交互会议已有越来越多关于搜索引擎技术研究的文章发表。 国内先后有北京大学、清华大学、国家智能研究中心等高校和研究单位对搜 索引擎技术开展研究，并研制出“天网 、“万维搜索 等搜索引擎。全国搜索 引擎和网上信息挖掘学术研讨会( s e w m ) 从2 0 0 3 年开始每年召开年会开展对搜索 引擎相关的理论和技术研讨和交流，逐渐成为该领域的学术交流平台，推动了中 文搜索引擎以及互联网技术的发展。 1 2 研究目的和意义 虽然搜索引擎确实能帮助人们发现和找到有用的信息，但是随着i n t e m e t 上信 第2 页 国防科学技术大学研究生院硕士学位论文 息资源的不断膨胀，人们发现传统的搜索引擎存在许多不足之处，其自身的局限 性，限制了人们对资源有效的获取： ( 1 ) 信息覆盖率低，查全率低 i n t e r n e t 上的信息资源是动态变化的，表现为信息量呈指数级增长，信息内容 不断更新，一个搜索引擎平均只能覆盖到整个i n t e r n e t 资源的5 2 0 ，在这样低 的信息覆盖率下，搜索引擎的查全率相对也很低。用户往往为了找到自己需要的 内容，而不断在多个搜索引擎间切换，耗费大量的时间和精力。 ( 2 ) 冗余和噪声信息含量大 传统的搜索引擎对提供的检索信息一般不进行综合处理，几乎所有的搜索引 擎返回的查询结果中都有大量重复和无关的内容，用户只能自己从浩如烟海的查 询结果中寻找自己所需的信息。近年来，广告商的介入使得搜索引擎的查询结果 并不完全按照相关度进行排序，排序靠前的很多都是广告信息，这使得用户查找 所需信息的过程更加繁琐。 ( 3 ) 各搜索引擎的信息资源差异大 传统的搜索引擎各自使用不同的索引技术、信息收集技术和关键词查询技术， 使得它们在各自搜索的信息资源在内容上、搜索范围上有相当大的差异，水平参 差不齐，这种情况给用户查询带来很大的不便。 ( 4 ) 索引数据库大，更新慢，响应时间长 搜索引擎的索引数据库随着i n t e m e t 的迅速发展，其规模不断扩大。对大规模 索引数据库的组织和维护较为困难，而且i n t e r n e t 上的网页信息更新快，往往会导 致索引失败。用户对查询结果进行链接浏览时，常常因遇到死链接而无法打开需 要的网页。 ( 5 ) 无差别的搜索模式，不考虑用户的个性化要求 现有的大多数搜索引擎，基本上都采用“一个搜索适用所有用户”的搜索模 式，不具有识别用户兴趣、爱好的能力，以至于不管什么兴趣层次的用户，只要 在同一个搜索引擎上使用同一关键词查询，所得到的查询结果都是一样的，这显 然不能满足各种用户的需求。同时，查询返回的结果往往成千上万，内容良莠不 齐，使得用户在寻找自己需要的信息时犹如大海捞针；其次，网络信息是动态变 化的，用户时常关心这种变化，要获得变化的信息，用户只能不断地在网络上查 询同样的内容，需要花费大量的时间。 ( 6 ) 机械的机器算法，忽视用户的反馈信息 现有的大多数搜索引擎在查询时大多采用基于查询关键词的匹配算法，在查 询结果排列时也大多采用基于词频或基于网页内链接的分析，很少考虑到用户对 查询结果的反馈信息。 第3 页 国防科学技术大学矽f 究生院硕士学位论文 上述问题的产生主要是由于传统的搜索引擎本身发展的局限性带米的，其局 限性限制了自身的发展。针对以上的问题，可以通过元搜索引擎的方式，在一定 程度上弥补传统搜索引擎的不足。 元搜索引擎为用户提供了一个统一的查询界面，用户的查询请求由元搜索引 擎根据其搜索引擎信息库中的信息转换成多个成员搜索引擎能识别的格式；然后 按照成员搜索引擎的调度算法，把转换后的查询分送到成员搜索引擎，由成员搜 索引擎完成实际的查询；最后元搜索引擎在收集到各个成员搜索引擎返回的查询 结果后，进行比较分析，再以统一的格式返回给用户。 利用元搜索引擎完成i n t e m e t 上信息资源的搜索，对于搜索引擎的设计人员来 讲，不需要建立和维护庞大的索引数据库，也不需要使用复杂的检索机制，可以 把精力集中在对成员搜索引擎的搜集、挑选上，将性能最优秀的通用搜索引擎和 各领域最专业的搜索引擎挑选加入到成员搜索引擎库中，同时设计出合理的成员 搜索引擎的调度机制，对用户的查询能自动去调用最合适的成员搜索引擎，还有 对查询结果进行优化合成处理；对用户来讲，元搜索引擎提供了一种能够同时查 询多个搜索引擎的集成机制，将各个搜索引擎的网址、接1 2 1 和查询语法格式等细 节屏蔽起来，简化和减轻了用户的操作负担，提高了查询效率，同时还提高了查 询的查全率和查准率。 虽然元搜索引擎只是简单地集成多个独立搜索引擎进行分发调用，对查询结 果进行合成处理，能够在一定程度上提高查询的查全率，方便用户查询的使用。 但如不考虑用户的个性化要求，同样会存在现有搜索引擎普遍存在的“一个搜索 适用所有用户”的搜索模式的缺陷。因此，将元搜索引擎上和个性化搜索技术相 结合，通过建立用户模型，识别用户兴趣、爱好，对用户的查询意图进行分析， 建立对用户查询过程反馈信息的机器学习以更新用户模型，对用户的查询进行优 化，能够更进一步提高用户查询的查准率。 总之，在元搜索引擎具有的优势之上，通过建立用户模型来记录用户的搜索 特征，实现个性化搜索，对满足用户对搜索的个性化要求，方便用户的搜索使用， 提高用户搜索的效率，都具有较好的意义。 1 3 论文的主要研究内容 本文围绕个性化元搜索引擎进行了研究，对其体系结构和相关关键技术展开 研究，主要完成如下工作： ( 1 ) 总结了元搜索引擎技术和个性化技术的研究现状和发展趋势，综述了相 关技术和应用。 ( 2 ) 总结了个性化元搜索引擎的若干关键技术，包括用户兴趣模型、用户模 篇4 页 国防科学技术大学研究生院硕士学位论文 型更新以及查询结果的合成处理。分析了相关工作中存在的不足和主要问题。 ( 3 ) 针对用户查询的个性化需求，建立了用户兴趣模型，提出了用户兴趣树 的建立算法，并基于隐反馈的方式，提出了用户模型的更新算法。 ( 4 ) 引入了决策理论，提出了基于偏好选举法的查询结果排序算法，能够较 好地将各成员搜索引擎返回的查询结果进行合并处理，满足用户的查询需求。 ( 5 ) 设计并实现了原型系统，对前文提出的理论、算法进行了实验检验，并 分析了实验结果。 1 4 论文组织结构 第一章为绪论，总体介绍本文的研究背景、目的和意义，说明了本文的研究 内容。 第二章首先概述了搜索引擎的现状和存在的不足，然后介绍了元搜索引擎产 生的原因以及其研究的意义，阐述了元搜索引擎的框架结构和分类，最后结合元 搜索引擎对个性化技术的研究现状和方法进行了分析。 第三章对实现个性化元搜索引擎的关键技术进行了深入研究，包括用户兴趣 模型、用户查询意图分析、成员搜索引擎偏好模型以及查询结果的合并处理。其 中，重点研究了用户模型的更新和查询结果的合并，提出了基于隐反馈的模型更 新算法和基于偏好选举法的排序算法。 第四章提出了一个b s 结构的个性化元搜索引擎框架。设计并实现了原型系 统，并在系统上进行了实验，给出了实验数据和分析。 第五章是对本文工作的总结以及展望。 第5 页 国防科学技术大学研究生院硕士学位论文 第二章搜索引擎、元搜索引擎与个性化技术 本章在第一节简要地介绍了搜索引擎的基本概念后，在第二节重点对元搜索 引擎进行了研究，包括元搜索引擎的产生、原理、分类、评价指标，并和传统搜 索引擎进行了比较，最后列举了近年了元搜索引擎领域的研究成果。第三节介绍 了个性化技术，并研究了个性化技术和元搜索引擎技术的结合。最后一节是本章 小结。 2 1 搜索引擎 2 1 1 搜索引擎的产生与发展 搜索引擎是人们在i n t e m e t 上检索信息的重要工具。公认的搜索引擎的祖先是 1 9 9 0 年由蒙特利尔大学学生a l a ne m a t a g e 发明的a r c h i e 。当时i n t e m e t 还未出现， 网络主要用于文件传输及f t p 等应用，使用者很难在各个分散的f t p 主机中查询 到所需的文件。因此，a l a ne m a t a g e 想到了开发一个可以根据文件名查找文件的 系统，并命名为a r c h i e 。a r c h i e 的工作原理与现在的搜索引擎很接近，它依靠脚 本程序自动搜索网络上的文件并对相关信息进行索引，供使用者以一定的表达式 查询。 现代意义上的搜索引擎的发展大体经历了三代r 7 】：最早现代意义上的搜索引擎 出现于19 9 4 年7 月，当时m i c h a e lm a u l d i n 将j o h nl e a v i t t 的蜘蛛程序( w e bw o r m ) 瞵j 接入到其索引程序中，创建了l y c o s ，被认为是第一代搜索引擎的代表，其缺点是 检索速度慢，且极少重新搜索网页刷新索引；1 9 9 6 年4 月，斯坦福大学的两名博 士生，d a v i df i l o 和美籍华人杨致远共同创办了超级目录索引y a h o o ，成功将搜索 引擎的概念深入人心，被认为是第二代搜索引擎的代表，其特点是采用了分类目 录索引和分布式方案；1 9 9 8 年以后搜索引擎进入了高速发展时期，目前，互联网 上较知名的搜索引擎己达数百家，其检索的信息量也己不可同日而语。截至2 0 0 8 年7 月，搜索引擎的领头羊g o o g l e 宣称其索引的网页已达一万亿之巨，并采用了 诸如云计算、p a g e r a n k 、动态摘要、网页快照、d a i l y r e f r e s h 、多文档格式支持等 集成搜索、多语言支持、用户界面等功能上的革新技术。它代表了第三代搜索引 擎。 近年来，搜索引擎在互联网应用中的地位越来越重要，导致了搜索引擎市场 急剧膨胀，竞争也越发激烈。从全球搜索引擎的竞争格局来看，目前全球搜索引 擎市场经过激烈的竞争和优胜劣汰，g o o g l e 、m s n 、y a h o o 的市场占有率较高， 但其中y a h o o 面临着掉队的危险。在国内，搜索引擎市场格局相对稳定，主要以 第6 页 国防科学技术大学研究生院硕士学位论文 2 12 搜索引擎的结构和原理 搜索引擎一般由信息收集器、分析器、索引器、检索器、查询接口和索引数 据库等六个部分组成州，其基本结构如图21 所示。 广一一一一一i 磊f 一一一一一1 镕口i 措 圈2 1 搜索引擎基本结构 下面对这六个组成部分的功能作简单介绍： ( 1 ) 信息收集器：通过s p i d e r 对i n t e r n e t 网上的信息进行遍历，访问网络上 可访问的每个站点里的网页并记录其u r l 地址，下载网页内容，并取出网页中的 链接地址添加到信息收集器的地址队列中，供下次访问。 ( 2 ) 分析器：对信息收集器下载的网页进行分析，建立索引，并将索引存八 索引数据库：分析技术一般包括分词、过滤和转换等，在分词时，大部分系统从 全文中抽取术语，建立全文索引，也有些系统仅肌网页的某些部分如标题、摘要 中抽取术语。 ( 3 ) 索引器：将文档表示为一种便于检索的方式并存储在索引数据库中。索 引一般按倒排文件格式存放。搜索引擎普遍借鉴了传统的信息检索中的索引模型， 包括倒排文档、向量空间模型等。 ( 4 ) 检索器：从索引数据库中找出与用户查询请求相关的文挡，并将相关度 大于闽值的所有文档按照相关度递减的顺序排序方式排列，返回给用户。 ( 5 ) 查询接口：为用户提供可视化的查询输入和查询结果输出界面。在查询 输入界面，用户按照搜索引擎的查询语法格式输入检索关键词以及各种检索条件： 在查询结果输出界面中，搜索引擎将查询结果按线形的文档列表显示，每个文档 一般包含了文档的标题、摘要和链接等信息，部分搜索引擎还提供了快照功能。 ( 6 ) 索引数据库：用于存放信息收集器从网上抓取的网页并经分析器处理、 第7 页 西 卧i 一 掣 b 一 厂莎一 国防科学技术大学研究生院硕士学位论文 索引器建立索引处理后的索引记录。 2 1 3 搜索引擎的分类 根据工作原理的不同，现有的搜索引擎主要可以分为以下四种【1o 】： ( 1 ) 基于目录的搜索引擎 基于目录的搜索引擎主要通过人工发现信息，依靠编目员的知识进行分类， 对w e b 信息资源建立层次结构的列表，将收集到的w e b 信息资源分类到某一个类 中，每一个分类目录针对一个专题或领域，用户通过层层目录逐步缩小查找的范 围，直到发现目标。y a h o o 、o p e n d i r e c t o r y 、s n a p 等搜索引擎都采用这种方式。这 类搜索引擎因为加入了人的智能，所以信息准确，缺点是需要人工介入、维护量 大、信息量少、信息更新不及时。 ( 2 ) 基于机器人的搜索引擎 由一个称为蜘蛛( s p i d e r ) 的机器人程序以某种策略自动地在互联网中搜集和发 现信息，索引器负责为搜集到的信息建立索引，检索器则根据用户的查询输入检 索索引库，并将检索到的查询结果返回给用户。服务方式是面向网页的全文检索 服务。这类搜索引擎的优点是信息量大、更新及时、毋需人工干预，缺点是返回 的无关信息过多，用户必须自行从结果中进行筛选。这类搜索引擎的代表有国外 的a l t a v i s t a 、e x c i t e 、i n f o s e e k 、l y c o s 、g o o g l e 等，国内的百度、网易、搜狗、新 浪等。 ( 3 ) 分布式的搜索引擎 分布式搜索引擎按区域、主题或其它标准创建分布式索引服务器。索引服务 器之间可以相互交换信息，且查询可以被重新定向。如果一个检索服务器没有满 足查询请求的信息，它可以将查询请求发送到具有相应信息的检索服务器。由于 分布式搜索引擎将索引数据库划分到几个分布的数据库中，每个数据库变得小一 些，但所有搜索引擎覆盖的范围变大，且很少有信息重复，而作为分布式系统特 征之一的可扩充性也是分布式搜索引擎的优点之一。然而分布式搜索引擎需要多 个索引数据库协同工作，实现较困难，目前尚未有真正的实用的分布式搜索引擎。 ( 4 ) 元搜索引擎 这类搜索引擎没有自己的索引数据库，而是将用户的查询请求同时向多个搜 索引擎提交，将返回结果进行去重、重排序等处理后，作为自己的结果返回给用 户。这类搜索引擎的优点是返回结果的信息量更大，信息覆盖率更高，缺点是不 能充分使用所调用的搜索引擎的功能。这类搜索的代表有d o g p i l e 、i n f o s p a c e 、 m e t a c r a w l e r ，以及国内的万纬等。 第8 页 国防科学技术大学研究生院硕士学位论文 2 2 1 元搜索引擎的产生 2 2 元搜索引擎 随着网上信息资源的膨胀发展，传统搜索引擎在搜索引擎的查全率和查准率 方面很难满足用户的要求。研究表明【2 j ，4 4 的用户仅使用1 种搜索引擎，4 8 的 用户使用2 到3 种搜索引擎，仅有7 的用户使用3 种以上的搜索引擎。而g o o g l e 和y a h o o 在5 0 0 个最热门的词条的检索中，仅有3 8 的结果是相同的。仅使用一 种搜索引擎，用户很可能错过需要的信息。因此为了查询相关的内容，用户经常 是同时使用多个搜索引擎查询相同内容，然后综合出最适合自己的内容。这对于 一般的网上信息搜集者来讲，肯定比较困难。因此如何准确选择搜索引擎、如何 减轻学习与操作负担、如何有效利用多个搜索引擎的集成资源与检索能力，就成 为制约网络信息检索技术进一步优化和发展的重要问题。正是面对这个挑战，检 索工具开发者设计了元搜索引擎j 。 元搜索引擎最早产生于2 0 世纪9 0 年代中期，是由华盛顿大学硕士生e r i c s 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 1 2 j 。它是指搜索引擎之后或之上的搜索 引擎，是在搜索引擎的基础上建立起来的可以同时或分时查询多个搜索引擎的网 络信息检索系统。 元搜索引擎自身并不收集网站或网页信息，通常也没有自己的数据库，而是 将用户递交的查询请求经过多种转换处理后提交给多个预先选定的成员搜索引 擎，并将所有查询结果集中起来以整体统一的格式呈现在用户。由于元搜索引擎 可以采用一系列的优化机制，它能够在尽可能短的时间内提供相对全面、准确的 信息，即使不能完全满足用户需求，仍可以作为相对可靠的参考源进行扩展搜索， 因此元搜索引擎己成为备受推崇的检索工具。 2 2 2 元搜索引擎的原理 、薅 客户端 浏览器 图2 2 元搜索引擎的结构示意图 元搜索引擎通过一个统一的用户界面帮助用户在多个搜索引擎中选择和利用 第9 页 国防科学技术大学研究生院硕士学位论文 合适的( 甚至是同时利用若干个) 搜索引擎来实现检索操作，是对分布式网络的多种 检索工具的全局控制机制。 元搜索引擎一般由三部分组成，即：查询分发、成员搜索引擎接口代理、结 果合成显示，其基本结构如图2 2 所示。 这三个部分的基本功能如下： 查询分发：负责实现用户个性化的检索设置要求，包括调用哪些搜索引擎、 检索时间限制、结果数量限制等。 成员搜索引擎接口代理：负责将用户的检索请求转化成不同的成员搜索引擎 本地化要求的格式，并调用成员搜索引擎，接收搜索结果。 结果合成处理：负责把所有成员搜索引擎查询结果去重、合并、排序并按一 定的格式显示。 元搜索引擎的出现，对于那些需要连续地使用不同的搜索引擎重复相同的检 索的人来说，是一个福音。使用元搜索引擎同时对几个搜索引擎进行检索，可以 获得更多更全面的查询结果。 元搜索引擎可以看成具有双层客户机j j l 务器结构的系统，用户向元搜索引擎 发出检索请求。元搜索引擎再根据该请求向多个搜索引擎发出实际检索请求；搜 索引擎执行元搜索引擎检索请求后将查询结果以应答形式传送给元搜索引擎，元 搜索引擎将从多个搜索引擎获得的查询结果经过整理再以应答形式传送给实际用 户。 2 2 3 元搜索引擎的分类 各个元搜索引擎在可检索的成员搜索引擎、检索提问的处理方式以及如何排 序和显示结果方面有着很大的差异。有些元引擎一个接一个的调用成员搜索引擎， 另一些则并行地进行搜索。有些搜索引擎将检索提问转变为成员搜索引擎的提问 语言，而有一些则原封不动的发送给成员搜索引擎。 按功能划分，元搜索引擎包括多线索式搜索引擎和a l l i n o n e 式搜索引擎；按 运行方式的差异可分为在线搜索引擎和桌面搜索引掣b 】。 ( 1 ) a 1 1 一i n - o n e 元搜索引擎 a l l 。i n o n e 元搜索引擎在其界面上以任意顺序或分类罗列的方式提供多个成 员搜索引擎的介绍信息和物理连接。这类元搜索引擎没有统一的全局外部模式， 而是直接把来自多个搜索引擎的查询结果列在一个页面上，不作重新计算或更改。 严格来说，这类元搜索引擎是对成员搜索引擎的罗列，不能算真正意义上的元搜 索引擎，只是元搜索引擎的初级形态。例如早期的搜星和a l l o n e s e a r c h 。 它们具有以下特点： 第1 0 页 国防科学技术大学研究生院硕士学位论文 仅提供一个简单的界面来帮助用户选择和使用各搜索引擎； 只能选择一个搜索引擎进行检索，是对各成员搜索引擎检索界面的全部复 制或部分复制； 直接利用所选搜索引擎的显示格式呈送给用户。 ( 2 ) 桌面元搜索引擎 桌面元搜索引擎又称软件式元搜索引擎，是一种客户端元搜索软件。它以软 件的方式直接运行在用户计算机上，代理用户递交提问，一次性检索多个成员搜 索引擎，并能获取实际的w e b 页面。它不仅可实现对多个成员搜索引擎的并行检 索，而且也能提供重要的后期处理功能( 如查询结果重排、删除重复记录等功能) 。 目前己经有许多这类产品，如w e b c o m p a s s 等。桌面元搜索软件的特点是结合客 户端环境，更容易提供个性化的检索服务，但一般不提供在线服务。 ( 3 ) 多线索式元搜索引擎 多线索式元搜索引擎，指利用统一的检索界面，实现对多个成员搜索引擎索 引数据库进行检索，并将查询结果以统一格式显示的网络检索工具。m e t a c r a w l e r 、 s a v v y s e a r c h 、p r o f u s i o n 等都属于多线索式元搜索引擎。这类元搜索引擎一般具有 以下特征： 统一检索界面：元搜索引擎提供统一界面，提供对各搜索引擎特点介绍和 选择机制，但所有目标搜索引擎构成一个逻辑整体，元搜索引擎检索界面构成唯 一的全局外部检索模式，用户通过这个全局界面实现对多个或任意一个搜索引擎 的检索。 检索指令转换：在具有唯一全局外部检索模式情况下，系统可提供统一的 全局指令语言，并自动地实现元搜索引擎指令与其目标搜索引擎指令的转换，用 户使用同一指令语言检索不同的搜索引擎的索引数据库。 统一结果集的组织与显示：元搜索引擎提供全局组织器，对各目标搜索引 擎返回的结果进行处理，形成全局结果集，并以统一格式显示，主要涉及数据格 式转换、去重、统一排序等。 2 2 4 元搜索引擎与传统搜索引擎的区别 搜索引擎与元搜索引擎的主要区别在于搜索引擎拥有独立的网络资源采集、 索引机制和相应的索引数据库，而元搜索引擎一般没有自己独立的数据库，却更 多地是提供统一界面( 或迸一步n 提供n - - 检索方式和结果整理) ，形成由多个分布 的、具有独立功能的搜索引擎构成的虚拟整体，用户通过元搜索引擎的功能实现 对这个虚拟整体中各独立搜索引擎数据库的查询显示等操作。元搜索引擎中各独 立搜索引擎被称为“目标搜索引擎”或“成员搜索引擎 ，它们各自保持其原来 第11 页 国防科学技术大学研究生院硕士学位论文 的局部数据模式和自己的检索指令；元搜索引擎给出一个全局外部模式，用以接 受用户检索输入和结果输出。总的来说，元搜索引擎与独立搜索引擎相比，具有 如下优点【1 4 】： ( 1 ) 信息的覆盖面更广 元搜索引擎集多个搜索引擎的查询结果为一体，其覆盖面自然较独立搜索引 擎更广。 ( 2 ) 查询结果更可靠 由于元搜索引擎对各个成员搜索引擎的查询结果还要进行合成处理，l e , 女n 将 在多个成员搜索引擎的查询结果中同时出现的同样的查询结果排列在显示的结果 的前面，这使元搜索引擎的查询结果具有更高的可靠性。 ( 3 ) 易维护 所谓易维护性是针对元搜索引擎的管理者而言的。元搜索引擎省却了独立搜 索引擎中收集和存储网页、建立和存储索引的工作。它将自