（计算机科学与技术专业论文）元搜索引擎技术的研究与应用.pdf

摘要 摘要 元搜索引擎是基于搜索引擎基础之上的搜索引擎，它可以同时检索多个成员 搜索引擎，对成员g 擎返回的结果信息进行融合、再加工后二次陈列给用户。元 搜索引擎是当今学术界研究的热门领域之一。 本文首先对搜索引擎和元搜索引擎的发展和搜索原理等进行了概述，然后分 别对元搜索引擎的几个关键技术，包括成员引擎的调度、搜索结果的整合、个性 化服务的实现等，进行了研究和分析，并在此基础上提出了本文设计的算法。本 文主要的研究工作如下： ( 1 ) 成员引擎调度算法的分析，并在此基础上报据本文的成员引擎的特点 提出本文使用的成员引擎调度算法。 ( 2 ) 跟踪用户的搜索行为( 包括隐式的点击浏览和显式的投票) ，并对用户 行为进行分析，动态地修改用户模型。这为成员搜索引擎的调度和搜索结果的整 合与排名提供了依据。 ( 3 ) 提出了基于用户行为的搜索结果合并算法。它根据对用，t 行为的分析 进行搜索结果的排名值计算，从而获得贴近用户偏好的搜索结果和排名。 最后，本文设计了一个基于用户搜索行为分析基础之上的元搜索引擎。相较 于其它的元搜索引擎，该引擎其有友好的用户冕面，为用户提供了一个快速查看 网页内容的捷径，并且由于是基于用户行为分析进行的成员搜索引擎调度和搜索 结果整合，因此更贴近用户对搜索引擎的偏好。 关键词：信息检索，元搜索，引擎调度，w 曲，结果整合 西北一【业大学硕十学位论文a b s t r a c t a b s t r a c t m e t as e a r c he n 百n ei sb a s eo nc o m p o n e n ts e a l c he n 舀n e s hs e n d st h eu s e fq u e r y t oan u m b c ro fc o m p o n e n ts e a r c he n 百n e ss i m u l t a n c o u s l y ，t h e nm e r g e st h er c s u l t sl i s t s f e t u m c df 幻mt h e mi n t oas i n 百er a n k e dl i s ta n dp r e s e n t st h em e r g e dr c s u l t st ou s e r s n h a sb e c o m eam a i l lp r o s p e do fr e s e a r c h f i r s t ，t h es t a t e o f t h c - a no ft h et r a d i t i o n a l a r c he n 酉n e sa n dt h em e t as e a r c h e n g i n e s 盯eo v e r v i e w e d ，t h e na n a l y s i so ft h es e v e r a lm a i nt e c h n o l o 西e so fm e t as e a r c h e n 舀n ea r ep r o p o s e d ，i n c l u d i n gt h es c h e d u l i n go fc o m p o n e n ts e a r c he n 舀n e s ，t h e m e 晒n go fs e a r c hr e s u l t s ，a n dp e r s o n a l i z e ds e n ，i c e b a s c do nt h e s er c s e a r c h e s ，t h e a l g o f i t h mo ft h cm e t as e a r c he n 百n ei i lt h i sp 印e ri sp r o p o s e d t 1 l em a i nw o r ko ft h i s p a p e ri n d u d e s ： ( 1 ) a n a l y z et h es c h e d u l i n go fc o m p o n e n ts c a r c he n g j n e s ，锄ds e l e dap r o p c r s c h e d u l i n gb a s e do nt h ec h a r a c t e r i s “c so ft h ec o m p o n e n ts c a r c he n g i n e si nt h i sp a p e l ( 2 ) ，i l a c kt h eu s e f s b e h a v i o r ( i n c l u d i n gc l i c k i n ga n dv o t i n g ) ，a n du p o nt h a t ，w e a n a i y z et h eb e h a v i o r sa n dm o d i f yt h eu s e rm o d e lc o n t i n u o u s l y t h i su s e rm o d e l p m v i d e st h ef o u n d a t i o no f m p o n e n t s e a r c he n 舀n es c h e d u l i n ga n df e 鲫l t sm e 画n 舀 ( 3 )p r o p o s et h er c s u l t sm e t 舀n ga l g o r i t h mb 弱eo nt h eu s e f s b c h a v i o r n c o m p u t e st h er 柚kv a l u eo fad o c i l m e mt oa u s e rq u e r y ，a n dr e m o v e sr c p e a t e dr c 鲫l t s a w a y s o a st og c t 簪，o ds e a r c hr e s u l l sd o s ct ou s e r s f a v o l i nt h ee n d ，w ed e s i g n e dam e t as e a r c he n 垂n eo nt h eb a s i so fa n a l y z i n gu s e 培 b e h a v i o lo 啪p a r i n gt ot h ee x i s t i n gm e t as e a r c he n 舀n e ，i th a saf r i e n d l yu s e fi i l t e 血c c ， a n dp r o v i d eac o n v e n i e n tw a yo fc h e c k i n gt h ef o u g hc o n t e n to faw e b p a g eq u i c l 【l y a i s o ，a si t sc o m p o n e n ts e a r c he n 舀n es c h e d u l i n ga l g o r i t h ma n d ”s u hm e r g i n g a l g o r i t h ma r eb a s e d t h eu s e r s b e h a v i o r ，i t ，sm o r ep r o n et ou s e 硌f a v o fo fu s i n g s e a r c he n g i n e k e yw o r d s ：h l f b 珊a t i o nr e t r i e v a l ，m e t a s e a r c h ，d a t a b a s es e l e d i 伽，w 曲，r e s u l t s m e r g j n g n l 西北工业大学 学位论文知识产权声明书 本人完全，解学校有关保护知识产权的规定，即：研究生柏：校攻读学位w 间论文j j 作的知识产权单位届丁舶北i ：业人学。学校有权保留：j i = 向国家有关部 或机构送交论文的复印什和电子版。本人允许沦文被亢阅和借阅。学校可以 将本学位论文的全部或部分内容编入有关数据库进行检索，可以采_ l f = | 影印、缩 印或扫描等复制手段保存和汇编本学位论文。同时本人保证，毕业厉结合学位 论文研究课题雨撰写的文章一律注明作者单位为两北：1 ：业大学。 保密论文待解密后适用奉声明。 学位论文作者签名，耋! 盈 抄7 年2 月细日 惰蚴臌。彩馓轰 指导教师签名：i ! ! ! ：。 7 年 一爿印日 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交的学位 论文，是本人在导师的指导下进行研究t 作所取得的成果。尽我所知，除文中 已经注明引用的内容和致谢的地方外，本论文不包含任何其他个人或集体已经 公开发表或撰写过的研究成果，不包含本人或他人已申淆学位或其它川途使川 过的成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。 本人学位沦文与资料若有不实，愿意承担一切相关的法律责任。 学位论文作者签名组 拶7 年2 ，月卯日 西北1 业人学硕十学位论文第一章引言 1 1 论文的研究背景 第一章引言 随着因特网的迅猛发展以及w e b 信息的飞速增加，因特网已成为人们查找 信息的主要来源。截止1 9 9 9 年2 月，调查表明万维网上已有大约8 亿被公丌索引 的网页；截止2 0 0 2 年7 月，g o o 甜e 的数据库已经索引了超过2 0 亿的网页。权威 机构的统计显示，i n t e m e t 正在以每天7 百多万网页的速率增长【。正是由于网上 信息种类繁多、信息数目庞大，以及新信息的不断出现和网页的快速更新等特点， 用户要想在信息的海洋中真正找到自己感兴趣的或所需的信息，就如同大海捞针， 劳心费神。 搜索引擎的出现正是为了解决这个“迷航”问题。搜索引擎利用一定的机制 ( 如网络蜘蛛，网络机器人等) 在互联网中不停的发现并搜集网页信息，然后依 掘相应的算法机制，对搜集到的信息进行理解、提取、组织和处理，最终存储到 数据库中，并建立相应的索引，为用户提供检索服务，从而起到信息导航的作用。 搜索引擎提供的导航服务已经成为互联网上非常重要的网络服务。搜索引擎技术 因而成为计算机工业界和学术界争相研究和开发的对象。 现今广为应用的几大主流搜索引擎，如g 0 0 硝e ，y a h o o ，m s n ，e x a 等， 由于采用的算法各不相同，数据库的覆盖范围的差异等，返回的检索结果集以及 结果集的排序通常有很大的差异。同时，独立搜索引擎的数据库覆盖率较为狭窄， 搜索效率较为低下。搜索出来的结果通常都是成千上万的( 如搜索w 曲2 0 ，g 0 0 9 l e 有7 ，7 9 0 ，0 0 0 项搜索结果，y a h o o 有1 1 ，1 0 0 ，o o o 项搜索结果，m s n 有1 ，4 5 0 j 7 6 项 搜索结果) 。在如此之多的搜索结果中，通常混杂了许多与用户的搜索关键字并不 相关的文章，造成信息过载；而且，用户经常需要在多个搜索引擎间切换查找， 以改善检索的效果，但各个搜索引擎的用户接口和查询语法各不榴同( 如对于逻 辑“与”，有的搜索引擎使用“+ ”，有的搜索引擎则使用“a n d ”等) ，给同时使 用多个系统的用户带来不便，浪费了用户的时间。增加了用户的搜索代价。虽然 与以前在信息海洋中盲目寻找信息相比，搜索引擎的出现已经大大提高了用户的 搜索效率：但是在信息呈爆炸性增长的互联网时代，独立搜索引擎在搜索质量、 搜索代价方面仍然满足不了用户的需求。 为了解决独立搜索引擎的数据库覆盖率问题和检索质量问题，一些搜索引擎 1 。 两北工业大学硕十学位论文第一章引言 致力于索引更多的网页，以及提高搜索结果的质量；还有一些组织歼始研究基于 多个搜索引擎基础之上的搜索，也就是元搜索引擎。由于元搜索引擎无需建立自 己的庞大的索引数据库和复杂的检索机制，维护起来比较容易，因此是解决独立 搜索引擎存在问题的较为经济的方案。因而元搜索技术也越来越成为计算机界研 究和歼发的热点。 1 2 论文的研究意义 1 2 1 传统搜索引擎的局限性 搜索引擎的出现从某种程度上来说，方便了用户从浩瀚的信息海洋中搜索出 感兴趣的信息。但是用户在用搜索引擎进行信息搜索时，常常会发现大量重复的 或者不相关的信息也被搜索引擎检索了出来，浪费用户的时问和精力。而且，不 同的搜索引擎由于数据库的索引范围和检索算法的不同，往往返回大不相同的结 果集，用户为了获得更准确的信息，通常要在多个搜索引擎问切换辗转，费神费 力。这些问题的产生主要足由于独立搜索弓 擎自身的局限健： ( 1 ) 单个索引数据库的覆盖范围有限，信息查全率低。i n t 啪e t 上的信息资 源足动态变化的，主要表现为信息量呈指数级增长，信息内容不断更新，信息的 存放位置的变更等。任何一个独立搜索引擎都不可能覆盖i n t e m e t 上的所有网页 信息。调查表明独立搜索引擎的平均网页覆盖率仅为5 一2 0 。 表1 1 搜索引擎的全球覆盖率1 2 1 排名搜索引擎， 覆盏率( ) 一 ln o r t h e ml i g l l t1 6 2a l t av i s t a 1 5 5 3 l n k t o m i ( s n a p ” 1 5 5 4l n k t o m i ( h o t b o t )1 1 3 5i n k t o m i ( m s ns e a r c h )8 5 6i n f o s e e k8 0 7 g o o 酉e 7 8 8l n k t o m i ( y a h o o ! ) 7 4 9e x c i t e5 6 1 0l v c o s2 5 1 1e u r o s e e k2 2 由表1 1 可以看出，覆盖率最高的n o n h e m “曲t 也只有1 6 ，即使所有搜 索引擎的覆盖率加起来，也只有4 2 【2 1 。而且最近的调查表明，单一通用搜索引 2 西北1 ：业大学硕士学仿论文第章引言 擎的数据库覆盖率正在逐步下降，因为索引的建立速度跟不上i n t e m e t 上信息的 增长速度。在这样低的覆盖率下，查全率也是很低的。 ( 2 ) 冗余重复信息量大。现有的传统搜索引擎没有对搜索结果进行综合处 理，几乎每个搜索引擎都会搜索出重复的或者基本不相关的信息，用户只能亲自 从这些大量的信息中提取自己认为与查询相关的信息。 ( 3 ) 索引数据库大，更新周期长。由于i i l t e m e t 信息的爆炸性增长，独立搜 索引擎要跟上这种信息的增长速度以满足用户的需求，索引数据库的规模就会不 断增大。对大规模索引数据库的更新和维护比较困难，而且h l t e m e t 上信息的更 新快，经常会导致索引的失效：再者，对大容量的、菲结构化或者半结构化的信 息进行增加、删除和修改，也是信息检索中的一个难点。 ( 4 ) 客观条件的限制。随着i i l t e m e t 上信息的快速增长，单个搜索引擎的数 据库的覆盖率、索引机器人的能力、索引数据库的大小以及系统维护开销等，都 限制了单个搜索引擎的发展。 1 2 2 研究元搜索的意义 针对前节讨论到的独立搜索引擎存在的诸多局限性，诸如数据库覆盖率 低，检索质量不高等，通常有如下两个可供选择的方案： ( 1 ) 各个独立搜索引擎不断扩大自己的索引数据库的覆盖率，改进网页内 容的提取质量和索引的组织，对搜索的质量进行严格的控铡。 ( 2 ) 元搜索引擎。它可以同时对多个成员搜索引擎的索引数据库进行查询， 并将返回的多个查询结果集综合起来，从而在一定程度上增加了搜索的覆盖率和 查全率。 第一种方案对独立搜索引擎的要求比较高，因为索引的速率要跟上信息的增 长速度，基本是不可能的，也就是说在信息飞速增长的今天，独立搜索引晕的索 引数据库覆盖率只会慢慢降低。而且随着数据库规模的增加，对其进行更新和维 护也变得越柬越困难，搜索质量的提高也变得不容易。 而元搜索引擎介于用户和独立搜索引擎之间，因而更易于实现个性化服务； 元搜索引擎无需建立其自己的大型索弓 数据库，因两维护起来比较容易，而且任 何一个成员搜索引擎的更新，都会反映到元搜索引擎上，因此实现起来更为经济。 本文着重讨论第二种方案。 3 西北工业大学硕十学位论文 第一章引言 1 3 论文的工作 当前，元搜索技术还在发展之中，尚未成熟。许多研究机构和研究人员都致 力于元搜索的关键技术的研究和个性化服务的实现。本文的主要工作如下： ( 1 ) 对搜索引擎的发展历史和发展现状进行深入的了解。对当前的几个主流 搜索引擎的算法机制进行了研究和分析比较，并对他们的查询请求发送 机制和搜索结果页的结构进行了详细的分析，为元搜索引擎的请求分发 和搜索结果的提取奠定基础。 ( 2 ) 对数据库调度算法进行了深入的研究和分析，并在此基础之上，针对我 们的实验条件，提出了本文设计的元搜索引擎采用的成员引擎调度方法。 ( 3 ) 跟踪并记录用户的搜索行为( 隐式的行为和显式的行为) ，建立用户模型， 并动态的更改模型。在进行结果的二次处理时，结合用户模型进行重排 序，以使得排序结果贴合用户模型。 ( 4 ) 用户界面的设计，包括查询界丽和结果显示界面。力求界面友好，操作 简单，且能满足大多用户的不同需求。在显示处理 ；的搜索结果时，本 文作了一个快速查询页面内容的简便处理，此处的设计也是现有的独立 搜索引擎和元搜索引肇所没有的一个特色。 ( 5 ) 搜索结果整合及排名算法的研究。在以上的研究基础之上，对多个成员 搜索引擎返回的搜索结果进行相应的处理。处理主要包括：去除不同搜 索引擎返回的重复的检索结果，根据用户模型对去重后的搜索结果进行 整合和排序并显示给用户。 1 4 论文的组织 第一章首先简单介绍了本文研究的背景，接着阐述了独立搜索引擎存在的种 种局限性，并由此引出研究元搜索引擎的意义。最后对本文的主要工作进行了大 概的介绍。 第二章对独立搜索引擎和元搜索引擎的发展历史，发展现状，检索原理等做 了介绍，并对个性化服务的现状进行了阐述，使得我们对元搜索引擎有一个大致 的概念。 第三章对元搜索引擎的几个最主要的关键技术和难点( 成员引擎调度，用户 4 西北一【：业大学硕十学位论文 第一章引言 建模和结果整合算法) 进行了研究和分析，并分别提出了相应的算法。 第四章中，基于对元搜索引擎的研究和本文提出的算法，我们设计了一个简 易的元搜索引擎，并就设计过程中使用到的知识和设计细节进行了描述，展示了 最终的显示效果。 文章的最后对所作的研究工作进行了总结，并对元搜索引擎未来的发展趋势 进行了论述。 5 西北工业大学硕十学位论文第二章搜索引擎概述 2 1 搜索引擎 第二章搜索引擎概述 自l i l t e m e t 出现以来，其信息量呈指数级增长，但是由于没有权威机构进行统 一地管理，它不像图书馆那样向用户提供经过选择的、有序的、系统的、完整的 信息；它也不同于商用联机检索系统，信息按照一定格式加工处理，并按类型或 学科分别建立数据库，以便于检索和利用。总结l i l t e m e t 上的信息，主要具有以下 几个明显的特点【3 1 1 4 l ： ， ( 1 ) 信息内容覆盖社会各个领域，涉及范围广，数量惊人。 ( 2 ) 信息分散无序，没有组织，都是自治式的，且多为非结构化或半结构化 的形式，机器难以进行处理。 ( 3 ) 信息内容经常是动态变化的，存放的位置缺乏固定性，信息的增加、删 除、修改，以及地址的变换时刻都在进行。 ( 4 ) 信息利用价值的差异较大，有用的、无用的甚至有害的信息都是相互混 杂交织在一起的。 i l l t e m e t 上信息的这些特点给用户查询信息造成了极大的障碍。为了获取所 需信息，用户需要自己在网上进行信息的搜集、组织和整理。而面对如此巨大的 信息量，即使是一个对i n t e r n e t 了解很深入的人，也往往面临许多不易解决的问 题，或是找不到有用信息，或是找到大量不相关的垃圾信息。因此人们需要一个 能在h l t e m e t 上高效查找信息的工具，这就是搜索引擎。 2 1 1 搜索引擎的发展历史 1 9 9 0 年之前，没有人能搜索互联网。搜索引擎的祖先，是1 9 9 0 年由m c g i l i u n i v e r s ；t y 的学生舢a ne m t a g c ，p e t 盯d e u t s c h 和b i nw h e e i a n 发明的c h i e 。当时万 维网还未出现，但网络中的文件传输已相当频繁。大量的文件散布在各个分散的 f r p 主机中，查询起来非常不方便，因此a ne m t a g e 等想到了开发一个可以用文 件名查找文件的系统，由此便产生了a r c h i e 。加c h i e 是第一个自动索引互联网上匿 名f 1 限网站文件的程序，但它还不是真正的搜索引擎。a r c h i e 能帮助用户在互联网 上的匿名f r p 服务器上查找文章和目录。a r c h i e 系统与l i i t e m e t 上所有已知的匿名 f r p 主机建立连接，并把这些存有公开文件的主机目录的完整清单存入名为i n t e m e t 7 西北丁= 业大学硕士学位论文第二章搜索引擎概述 a r c h i v e s 的数据库中。当用户查找某个文件或目录时，只需将所需查找的文件或目 录的名称告诉a r c h i e 系统，它就会把数据库中具有此文件或目录信息的匿名f t p 主 机的名字和准确的路径名告诉用户。 1 9 9 3 开始，一些服务站点为了方便用户浏览，将手工收集到的站点信息编成 r r m l 文件，并按一定方式组织起来，成为c a t a l o g 或是d i r e c t o r y 。该方式的优点是 人工进行索引，因而具有很高的准确性；缺点是难以跟上信息的飞速增长，而且 信息的整理带有很大的主观性。也是从这时开始，人们开始研究用计算机，如 r o b o t ，s p i d e r ，c r a w l e r s 等，代替人工自动地跟踪超链接，并记录站点的相关信息。 最早现代意义上的搜索引擎出现于1 9 9 4 年7 月。当时m j c h a e lm a u l d i n 将j o l l l l k a v i t t 的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的l y c o s 。同年4 月， 斯坦福大学的两名博士生，d a v i df i i o 和美籍华人杨致远( g e yy a n g ) 共同创办了 超级目录索引y a h o o ，并成功地使搜索引擎的概念深入人心。从此搜索引擎进入了 高速发展时期。 1 9 9 4 1 9 9 5 年，大批搜索引擎站点建立了起来，如w 曲q a w l e t ，l v c o s ，眺。西 e x c i t e ，t av i s t a 等。但这时候它们数据库容量相对较小，查询效率也不高。但是 它们的出现，已为i l l t e m e t 上的用户提供了极大的方便。这一阶段可看作是搜索引 擎的“初建期”。1 9 9 6 年，是搜索引擎的“容量建设期”。这一阶段竞争的焦点是 谁的数据库“最大”，谁的索引更新快。1 9 9 7 年，竞争焦点转向要做最好的索引， 搜索引擎处于“质量建设期”，这时的提法足“足够的而且较好”。 1 9 9 8 年之后，搜索引擎进入“多向型发展期”。发展趋势主要有：大型搜索引 擎在诸多技术方面走向成熟；一批小型搜索引擎从通用型转向专业化；元搜索引 擎的发展和完善。 2 1 2 搜索引擎的分类 搜索引擎可以有多种分类方法。按照检索方式，搜索引擎大致可以分为目录 式搜索引擎，全文检索式搜索引擎和元搜索引擎。下面简单介绍这三种搜索引擎 的检索方式和特点： ( 1 ) 目录式搜索引擎。目录式搜索引擎利用传统的图书资料分类方法，将 w e b 资源进行分类组织，依靠编目人员的知识进行分类，并建立一套目录体系。 y a h o o 是典型的目录式搜索引擎，它将相关主题的站点组成一个层次化的目录树。 y a l l 0 0 的目录结构由人工建立，分类按照内容、地名、名称以及字母顺序等符合人 8 西北工业大学硕士学位论文第二章搜索引擎慨述 们使用习惯的概念来构造。国内的搜狐( s o h u ) 也采用了树形结构束对站点进行 层次式分类。这种树形的分类方式符合人们逐层缩小范围的查询过程。 这类搜索引擎的优点是结构清晰，符合人们的使用习惯；由于加入了人的智 能，因此信息准确，导航质量高。不足之处在于：需要大量人力来搜集组织信 息，人工维护代价大，且信息量少，不能及时的更新信息；主题的分类具有很 大的模糊性和主观性。对于使用者来说，有时可能并不知道要查找的信息属于何 种分类；难以将一些偏僻的领域归入到某个分类中，不能全面反映h l t c m e t 上 的信息；站点的主题内容的概括依赖于编目人员的个人水平，因此可能存在质 量上的参差不齐，有一定的主观性；采用漫游查询的方式，工作效率不高，并 且随着目录查询树结构的不断增大，查询某一主题的代价越束越大，时间越来越 长。 ( 2 ) 全文检索式搜索引擎。这类搜索引擎的典型代表是g o o 舀e ，n o n h e m “g h t ，a l t a v i s t a 等。该类搜索引擎由一个称为网络机器人或是网络蜘蛛的程序( 统 称为搜索器) 自动发现和搜集i n t e m e t 上的信息，然后由索引器为搜集到的信息 建立索引，并存储到数掘库中，供用户检索信息时使用。通常这个索引是面向网 页建立的一个全文索引。 全文检索式搜索引擎的优点是：因为是由程序自动搜集网络上的信息，无需 人工干预，因而信息量大，更新及时，维护成本低。不足之处是：由于当前机 器人智能技术尚未成熟，无法跟人的智能相比。用机器进行信息的搜集和索引工 作，往往查询返回的信息过多，通常有很多无关信息，用户必须自己从结果中进 行筛选；网络负载大，服务器负担重；网络上有很多网页是无法为传统搜索 引擎的网络蜘蛛或是网络爬虫索引的。这些网页被称为d e e pw 曲1 1 1 ，也就是通常 所说的不可见网页。它们无法被索引，通常有如下几个原因：a 、网页的所有者不 允许其被索引；b 、动态生成的网页；c 、没有反向链接的网页，也就是没有网页 提供进入该网页的链接；d 、网页内容需要在某种控制下才能获得。然而，这些 d e e pw 曲绝大多数都是对外公开的。因此，检索式搜索引擎遗漏了这块信息源。 现在，越来越多的搜索引擎将目录式搜索和检索式搜索两种方式联合起来使 用，充分发挥各自的有点，相互弥补不足，以期达到更好的检索效果。例如，y a h o o 就曾与g o o 甜e 合作，以提商查询范围。2 0 0 4 年2 月，y a h o o 正式推出自己的全 文搜索引擎，并结束了与g o o g l e 的合作。 ( 3 ) 元搜索引擎。元搜索引擎是搜索引擎之上的搜索引擎。这类搜索引擎 9 西北f ：业大学硕十学位论文 第二章搜索引擎概述 没有自己的索引数据库，它将用户的查询请求同时提交给多个成员搜索引擎，对 成员引擎返回的结果进行二次处理，如删除重复结果、重新排序等，然后将处理 后的结果集返回显示给用户。后面我们将对元搜索引擎做更详细的介绍。 2 1 3 工作原理 一个搜索引擎通常有用户接口，检索器，数据库，索引器，搜索器五个基本 组成部分【5 】它们之问的架构和流程如图2 1 所示。 图2 1 搜索引肇原理图 每个部分的功能简单介绍如下： ( 1 ) 用户接口 用户接口的作用是接收用户输入的查询关键字、显示搜索结果、提供相关的 用户查看和反馈机制等。其主要目的是提供统一的查询接口，以方便用户使用搜 索引擎高效地、多方式地从搜索引擎中查询相关信息。用户接口的设计和实现应 考虑到大多数用户的使用习惯。 用户输入接口可以分为简单接口和复杂接口两种。简单接口只提供一个文本 框供用户输入查询串；复杂接口则允许用户对查询条件进行多种限制，如逻辑运 算( 与、或、非) 、相近关系( 相邻、n e a r ) 、域名范围( 如e d u 、c o m ) 、出现位 置( 如标题、内容) 、信息发布的时间等。目前一些公司和机构讵在考虑制定查洵 选项的标准。 ( 2 ) 检索器 检索器的功能是根据用户的查询关键字在数据库中快速地检索出相关文档， 主要工作包括：文档与查询关键字的相关度计算，文档集的排序，结果集的显示 l o 西北工业大学硕士学位论文 第二章搜索引擎概述 方式的确定。检索器的性能对用户的检索效率有着决定性的影响。 ( 3 ) 数据库 数据库用来存储站点的相关信息，包括站点的地址( u r l ) ，站点的标题和主 体内容，站点的索引信息，站点被点击浏览的次数等等。数据库的设计和优化是 搜索引擎重点关注的问题，因为数据库的性能关系到搜索引擎的整体性能。 ( 4 ) 索引器 索引器的功能是理解搜索器搜索到的站点的信息，分析页面结构，从中提取 索引项，用于表示文档并生成文档库的索引表。目前主要有两种索引建立的方法： a ) 对页面中的重要内容建立索引，如对网页的标题或者m e t a ，或是用租体或斜体 表示的词建立索引。这种方法会丢失许多有用信息；b ) 对网页的全文建立索引。 该方法不会造成信息丢失，但是会大大增加数据库的规模。 索引项有客观索引项和内容索引项两种：客观索引项与文档的内容无关，如 作者姓名、u r l 、网页建立和更新的时间、编码、网页内容的长度、链接流行度 ( i j i i l 【p o p u i a r i t y ) 等；内容索引项是用来反映文档内容的，如关键词及其权重， 短语、单词等。索引表一般使用某种形式的倒排表( 1 n v e 稻i o nl i s t ) ，即由索引项 查找相应的文档( 倒排表的概念请查看相应的参考文献) 。索引表也可能要记录索 引项在文档中出现的位置，以便检索器能计算出索引项之间的相邻或接近关系。 索引器采用的索引算法有集中式索引算法和分布式索引算法两种。当数据量 很大时，还必须实现即时索引，否则无法跟上信息量急剧增长的速度。索引算法 对索引器的性能( 如大规模峰值查询时的响应速度) 有很大的影响。一个搜索引 擎的有效性在很大程度上取决于其索引的质量。 ( 5 ) 搜索器： 通常有两种信息搜集方法：人工搜集和机器搜集。人工搜集是指由用户主动 向搜索引擎报告或者提交自己的资源，y a h o o 采用的就是这种方式，该方式要求用 户自己提交页面的相关信息，并自行维护信息的有效性；机器搜集由网络机器人 或是网络蜘蛛自动搜寻i n t e m e t 上的网站信息，是目前大多数搜索引擎采用的方法。 搜索器，也就是我们通常所说的网络机器人或足网络蜘蛛，它的功能就是在 i n t e m e t 上漫游，不断地发现和搜集信息。它通常是一个计算机程序，日夜不停地 运行。它要尽可能多、尽可能快地搜集各种类型的新信息，同时因为互联网上的 信息更新很快，所以还要定期更新已经搜集过的旧t i 息，以避免出现死连接和无 效连接的情况。 1 1 西北工业大学硕十学仿论文第二章搜索引擎概述 目前有丽种常用的机器搜集信息的策略： ( 1 ) 从一个起始u r l 集合开始，顺着这些u r l 中的超链接，以某种搜索策略， 如广度优先搜索、深度优先搜索或启发式循环搜索等，在互联网中不断地发现信 息。这些起始u r l 可以是任意的u r l ，但通常是一些非常流行的、包含很多链接 的站点( 如y a h 0 01 ) 。 ( 2 ) 将w 曲空| b j 按照域名、i p 地址或国家划分成多个子空间，每个搜索器分 别负责一个子空间内的穷尽搜索。 搜索器常采用分布式并行计算技术加以实现，以提高信息发现和更新的速度。 商业搜索引擎的信息发现可以达到每天几百万网页。 2 2 元搜索引擎 2 2 1 元搜索引擎的现状 按照检索原理和结果合成方式，我们可以将元搜索引擎大致分为三类： ( 1 ) a 1 1 i n o n e 元搜索引擎，也称为集成式搜索引擎。这类搜索引擎只是在 其界面上以任意顺序或分类罗列的方式提供多个搜索引擎的介绍信息和物理链 接，可以供用户选择要搜索的成员引擎。对成员搜索引擎的搜索结果也不做二次 处理，只是简单将各个结果集罗列在一个页面。这类元搜索引擎并不是真正意义 上的元搜索引擎，它只是多个成员搜索引擎的简单集合，易于实现，是元搜索引 擎的初级形态。 。 ( 2 ) 基于桌面的元搜索引擎，又称软件式元搜索引擎，是一种运行在客户 端的元搜索软件。它直接运行在用户的个人计算机上，帮助用户向多个成员引擎 的服务器提交查询关键字，能一次性检索多个成员引擎，并能获取实际的w 曲页 面。它不仅能够实现对多个成员搜索引擎的并行检索，而且也提供了对搜索结果 的二次处理功能，如对搜索结果重新排序、删除重复记录等功能。这类元搜索引 擎的显著优点是直接运行在客户端，因而无需服务器，也就不需要考虑到服务器 的性能和负载等问题；而且可以结合客户端环境，更容易地实现个性化的检索服 务。 ( 3 ) 多线索式元搜索引擎，是最具典型意义的元搜索引擎。它的使用更为 普遍，其特点是使用便捷、操作简单，通过浏览器可以直接访问，而且此类元搜 索引擎一般都有一个统一的检索界面；能进行查询指令的转换；具有统一的结果 1 2 璺些! ：些奎堂堡兰垡堡奎塑三至堡窒! ! 篁堕堕 合成机制和结果显示机制；具有独立的服务器用来响应用户请求，服务器上可能 存储了有关成员引擎的相关信息。w w w s e a r c h c o m 就是该类元搜索引擎的一个典 型的例子。 本文讨论的元搜索引擎是基于桌面的元搜索引擎和多线索式元搜索引擎的 综合体。一方面，本文设计的元搜索引擎也是运行在用户的个人计算机上的程序， 跟踪用户搜索行为，建立用户模型，以实现个性化搜索，这点与基于桌面的元搜 索引擎相似；另一方面，该元搜索引擎也具有统一的搜索界面，查询指令转换功 能，统一的结果合成和显示机制等，这点又与多线索式元搜索引擎类似。 2 2 2 元搜索引擎工作原理 元搜索引擎是建立在搜索引擎基础之上的搜索引擎，它通过接口向多个成员 引擎发送请求，调用成员搜索引擎返回的搜索结果，而无需自己建立和维护庞大 的索引数据库。元搜索引擎通常都包含用户接口，查询分发器，结果整合器三个 基本的组成部分。它们之间的流程关系如图2 2 所示，根据箭头的流向可以看出 元搜索引擎在处理用户的查询请求时的处理流程。 图2 2 元搜索引擎框架图 用户接口：负责提供一个统一的查询接口和结果显示界面。要力求界面友好， 操作简单，符合人们的使用和思维习惯。 查询分发器：该模块的功能根据元搜索引擎实现功能的不同而不同。通常有 两种情况：如果成员搜索引擎的数目较小，无需进行成员引擎的调度，那么该 模块的功能就是直接将用户的搜索请求分别转化为每个成员搜索引擎能够识别的 格式；如果成员搜索引擎数目很多，且不同的成员引擎所覆盖的领域大不相同， 那么该模块除了负责将用户的搜索请求分别转化为每个成员搜索引擎能够识别的 1 3 西北- i - 业人学硕士学位论文第二章搜索引擎概述 格式外，还有一个重要的功能就是进行成员搜索引擎的调度。这样可以有效地避 免调用与用户查洵不相关或相关度很小的成员引擎而引起的系统负担，并有效地 降低对结果筛选的难度。成员搜索引擎的调度算法目前主要有；粗略描述法，统 计学算法和基于学习的方法。 结果整合器：该模块负责对成员搜索引擎返回的结果页面进行结构分析，抽 取结果集，并对结果集进行二次处理，如删除重复的结果、结果整合、重新排序 等，并将处理后的搜索结果显示给用户。 上面介绍的三个模块只是元搜索引擎必不可少的基本组成部分。具体在设计 的时候，还可以在这些模块基础之上添加新的模块，以实现特殊的功能。例如可 以加上一个表示用户兴趣的模块，以便在成员引擎调度和结果整合时结合用户兴 趣，实现个性化服务。本文设计的元搜索引擎就是在此基础之上添加了表示用户 搜索行为的模块，第三章和第四章我们将详细描述该模块的建立和使用过程。 2 2 3 个性化服务的现状 现有搜索引擎，无论是通用的独立搜索弓擎( 如w w 札g o o g l e c o m ) 还是元 搜索引擎( 如w w w - s e a r c h c o m ) ，只要搜索关键诃相同，得到的搜索结果就相同， 而不会考虑到用户的信息偏好和需求差异。个人信息需求的有限性和互异性要求 网络信息服务实现个性化。个性化服务能够根据用户的兴趣和特点进行检索，返 回与用户需求相关的检索结果，它可以根据用户个体的不同，返回用户个体最关 心希l 感兴趣的结果，是一种智能的、自动的搜索服务。它能够在完全不打扰用户 正常使用的情况下得到用户的兴趣变化并动态地修改兴趣，跟踪用户的兴趣变化。 用户建模是个性化服务的基础和核心。简单地说，用户建模就是从捕捉到的用户 信息中构建用户模型。 个性化搜索服务主要体现在两方面f 1 6 】：( 1 ) 用户在表达自己的需求时可以使 用符合用户习惯的描述方式。( 2 ) 在返回检索结果时，只返回最贴近用户需求的 信息，即针对同一检索词，不同用户能够获得不同的检索结果，以满足不同用户 的个性化需求。比如，搜索关键字“s t o c k ”有三种含义，分别是会融方面的“股 票”含义，化工方面的“原料，树干”含义和计算机方面的“库存”。那么用户是 想查询哪一种含义的“s t o c k ”呢? 个性化搜索引擎可以根据用户平时的检索兴趣， 来自动进行检索意图识别，比如从以前该用户的检索行为中，发现该用户对金融 方面的信息更感兴趣，于是将“s t o c k ”自动匹配成“股票”含义进行查询。本文 讨论的个性化服务是指第二种方式。 1 4 西北1 ：业大学硕士学位论文第二章搜索引擎概述 当前的搜索引擎都在致力于个性化服务的研究与实现，以满足不同用户的不 同需求，更好的为用户服务。y a h o o ! 1 5 】站点1 9 9 6 年推出个性化服务m v y a h o o 。 用户登录m y y a h o o 站点后，系统会要求用户从成百上千的栏目中选择自己感兴趣 的栏耳，并提交给服务器。卡内基梅隆大学的、阮b w a l c h e r 则要求用户输入感兴 趣的关键词，系统将输入的关键词视作用户兴趣所在，并据此进行个性化的信息 推荐。加州大学i r v i n e 分校于1 9 9 6 年推出的个性化推荐系统s y s l 【i l l w e b e n 采 用示例来进行用户建模。在用户浏览w c b 网页的过程中，s y s k i l l & w 曲e n 要求用 户对每一个浏览过的页面标注“感兴趣”、“不感兴趣域者“一般”，然后系统会计 算页面中单词与类别的互信息( m u t u a li n f o 删a t i o n ) 以找出反映用户兴趣的关键 词，构造用户模型。p e r s o n a 】w e b w 机血c f 是卡内基梅隆大学于1 9 9 6 年推出的个 性化推荐系统。在用户的浏览过程中，p c 俗o n a l w 西w a t c h e r 记录用户浏览的页面， 观察用户对页面超链接的选择，由此推断用户浏览过的页面属于感兴趣的类别， 反之属于不感兴趣的类别。分别作为训练集的正例和负例。然后再通过计算单词 与类别的互信息选择反映用户模型的关键词，构建用户模型。 然而，当前的个性化搜索服务方面还存在诸多问题。比如y a h 0 0 、a l t a v i s t a 、 l l l f o s e e k 等搜索引擎，通过个性化配置( 如利用c o o k i e 机制或为用户建立配置文 件等) 来提高对用户搜索请求命中率。这种方式一般需要用户登记一些个人信息 并存储在服务器上，但这可能造成用户某些隐私信息的泄露。还有一些搜索引擎 如h o t b o t 、z d n e t 等设置一些选项让用户给出反馈信息。这种方式被动地接受 用户对搜索结果满意程度的反馈，需要用户的主动配合。 本文讨论的用户建模既可以在不干扰用户正常使用的情况下进行，因为考虑 到有的用户可能不愿意主动的进行标注等：也将用户的主动行为考虑了进去，因 为用户的主动行为通常能更明确的表示用户的兴趣所在。具体的建模过程将在3 2 节中详细描述。 2 2 4 元搜索引擎的优点 由于元搜索引擎是建立在搜索引擎基础之上的，是为了解决传统搜索引擎的 种种局限性而产生的，与独立搜索引擎相比，元搜索引擎有诸多的优越性： 1 统一的用户界面。用户只需在一个操作界面进行相应的操作，而不用去了 解各个独立搜索引擎的语法( 如：是用“a n d ”还是“+ 超；是空格进行关键字的组合 等) ，跟单独使用一个通用搜索引擎一样方便。 2 整合了多个搜索引擎的结果。由于各独立搜索引擎数据库的覆盖范围不尽 1 5 西北- 1 ：业人学硕 = 学位论文第二章搜索引擎慨述 相同，在相同的搜索关键字的情况下，通常会搜索大相径庭的结果集。用户为了 获得准确的搜索结果，通常要在多个搜索引擎问不停的切换查找。元搜索引擎技 术将所有成员搜索引擎的搜索结果进行了二次处理，并一次性显示给用户，给用 户一个清晰简洁的爨面，降低了检索的代价。用户只需一次输入搜索关键字，就 可以得到多个搜索引擎的搜索结果，提高了搜索效率和质量。 3 增加了w 曲搜索的覆盖范围。独立搜索引擎由于其各方面条件的限制， 索引数据库的覆盖范围窄，且搜索结果中常含有很多无用信息，给用户带来许多 困扰。元搜索引擎建立在多个成员搜索引擎基础之上，对多个数据库进行查询， 从一定程度上弥补了独立搜索引擎的缺点，信息检索的覆盖面宽广的多，查全率 也有了很大的提高。 4 由于元搜索引擎介于独立搜索引擎和用户之间，在设计元搜索引擎时，可 以方便地对用户的搜索行为和搜索兴趣进行跟踪，建立用户模型，并根据用户模 型进行成员搜索引擎的调度和搜索结果整合，便于实现个性化服务。 5 降低搜索引譬工程的复杂度。由于元搜索引擎是建立在其他搜索引擎的基 础之上的，因此无需建立其自己的庞大的索引数据库，也省去了维护的代价，大 大降低了工程的复杂度，实现起来更为经济。 2 3 小兰吉 本章首先对搜索弓l 擎的发展历史和搜索原理作了简单的描述，接着对元搜索