（计算机应用技术专业论文）元搜索排序合成研究与应用.pdf

摘要 论文题目：元搜索排序合成研究与应用 专业：计算机应用技术 硕士生：张文升 指导教师：汤庸教授 摘要 随着信息化的不断发展和网络资源的日益膨胀，人们对于资源获取的方式， 包括准确性、多样性、便利性等要求也越来越高。在这种背景下，传统搜索引擎， 如g o o g l e 、y a h o o 、百度等，虽然得到了突飞猛进的发展，但同时也存在着网页 覆盖率不足、处理能力有限、搜索接口不统一等许多问题。 元搜索技术是解决这些问题的有效方法之一，它通过联合多个搜索引擎，对 返回结果进行处理，并提供统一的查询与结果返回接口，从而提高搜索查准率与 查全率。基于元搜索技术的这些优点，本文紧紧围绕理论和应用两个层面，对元 搜索技术展开探索和研究。 理论上，当前有关元搜索技术的研究主要集中在排序合成算法( d a t af u s i o n ) 。 排序合成算法可依据它们需要的信息进行分类，包括是否需要相关度分值或排序 位置信息，以及是否需要训练数据。然而，根据数据合成性质，越优秀的成员搜 索引擎返回的文档准确性也越高，成员引擎的权重值也应当是排序合成的一个重 要考虑因素。据此，本文以加权分值类算法为基础，利用d a r kh o r s e 效应以及 文档和成员搜索引擎之间互为推荐的对偶关系，根据各文档的“共识度”构建成 员搜索引擎的自生成权值。并且，利用s k i m m i n g 效应，在算法中引入“浏览者 模型 ，只由排序位置信息即可计算文档相关度分值。 与其他加权类算法不同的是，这些改进不依赖于包括相似度函数在内的成员 搜索引擎技术细节的先验知识，同时也不需要训练数据。并且，这些改进也不是 针对某一特定算法，而是可以应用到任何加权分值类算法中的一种改进。基于这 两项主要改进并结合c o m b m n z 算法，提出改进c o m b 的自生成加权排序合成算 法。最后，通过t r e c 数据集进行实验，证实了这些改进的有效性。 在应用方面，本文以个人学术信息协同软件平台“s c h o l 为依托，将 元搜索技术应用到垂直学术搜索引擎中来，探索并设计实现了基于个人学术信息 1 中山大学硕士学位论文 的个性化w e b 学术搜索引擎。该引擎主要提供中国期刊网、i e e e 、g o o g l es c h o l a r 等数据源的中英文学术论文和著作信息检索，为学者提供有效的学术信息提取， 以及学术信息检索服务。通过实验和分析可以看出，基于元搜索技术的学术搜索 引擎的有效性确实得到了提高。 关键词：信息检索，元搜索，排序合成，学术搜索 i i a b s t r a ( 玎 t i t l e ：r e s e a r c ha n da p p l i c a t i o no nm e t a - s e a r c hd a t af u s i o n m a j o r ：c o m p u t e ra p p l i c a t i o n n a m e ：w e n s h e n gz h a n g s u p e r v i s o r ：p r 0 免s s o rt a n gy o n g a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , a n dt h ei n c r e a s i n ge x p a n s i o n o f n e t w o r k r e s o u r c e ，p e o p l ea r em o r e a n dm o r ep a r t i c u l a ra b o u tr e t r i e v i n gi n f o r m a t i o n , i n c l u d i n g i t sa c c u r a c y , r e s o u r c ed i v e r s i t y , c o n v e n i e n c e ，a n ds oo i lu n d e rt h i s b a c k g r o u n d ，t h o u g ht h et r a d i t i o n a ls e a r c he n g i n e ss u c ha sg o o g l e ，y a h o o ，b a i d u , m a k eag r e a ti m p r o v e m e n t ，t h e ya l s o f a c es o m e p r o b l e m s l o ww e br e s o u r c e c o v e r a g e ，l i m i t e dp r o c e s s i n gc a p a b i l i t ya n dn ou n i f o r mu s e ri n t e r f a c e ，f o re x a m p l e m e t a - s e a r c hi sag o o dc h o i c et os o l v et h e s ep r o b l e m s i tc o m b i n e ss e v e r a lo t h e r t r a d i t i o n a ls e a r c he n g i n e s ，p r o c e s s e st h e i rs e a r c hr e s u l t sa f t e rt h es e a r c hr e q u e s t ，a n d o m p m sau n i f o r ms e a r c hr e s u l tl i s tt ot h eu s e r t h r o u g ht h i sw a y , i ti n c r e a s e st h e s e a r c h i n gp r e c i s i o na n dr e c a l l c o n s i d e r i n gt h ea d v a n t a g e so fm e t a - s e a r c h , t h i sp a p e r f o c u s e so ns t u d yo fm e t a - s e a r c ht e c h n o l o g y , f r o mt h e o r ya n da p p l i c a t i o n t h e o r e t i c a l l y , t h ec u r r e n ts t u d yo fm e t a - s e a r c hi sm o s t l yf o c u s i n go nd a t af u s i o n , w h i c hi sab r a n c ho fm e t a - s e a r c h d a t af u s i o nc a nb ec h a r a c t e r i z e db yt h ed a t at h e y r e q u i r e ：w h e t h e rt h e yn e e dr e l e v a n c es c o r e so ro n l yr a n k s ，a n dw h e t h e rt h e yr e q u i r e t r a i n i n g d a t ao r n o t h o w e v e r , a c c o r d i n gt o t h ec h a r a c t e r i s t i c so ff u s i o n , t h e d o c u m e n t sr e t u r n e db yab e t t e rs e a r c he n g i n ew i l la l w a y sh a v eb i g g e rc h a n c et oh e r e l e v a n tt ot h es e a r c hr e q u e s t t h e r e f o r e ，t h ew e i g h t so ft h em e m b e rs e a r c he n g i n e s s h o u l da l s ob ep a i da t t e n t i o nt ow h e nf u s i n gt h er e s u l t s f o c u s i n go nw e i g h t e ds c o r e s a l g o r i t h m s ，t h i sp a p e rm a k e su s eo ft h ed a r kh o r s ee f f e c ta n dt h ea n t i t h e t i c r e l a t i o n s h i pb e t w e e nt h ed o c u m e n t sa n dt h em e m b e re n g i n e s ，b a s e do nw h i c ht h i s p a p e rd e v e l o p sw e i g h t so fm e m b e re n g i n e s b e s i d e s ，t h i sp a p e ra l s oi n t r o d u c e st h e i m p a t i e n tr e a d e rm o d e li n t ot h ea l g o r i t h ma n dg e tt h ef i n a ld o c u m e n tr e l e v a n c es c o r e s u s i n go n l yt h er a n k i n gi n f o r m a t i o n i l i 中山大学硕士学位论文 d i f f e r e n tf r o mt h eo t h e rw e i g h t e ds c o r e sa l g o r i t h m , t h ei m p r o v e m e n t sd on o t d e p e n do nt h et e c h n i q u ed e t a i lo ft h em e m b e re n g i n e s t h e yn e i t h e rn e e da n yt r a i n i n g d a t a b e s i d e s ，t h e s ei m p r o v e m e n t sa r en o tf o rap a r t i c u l a ra l g o r i t h mb u tf o ra l lt h e a l g o r i t h m sw h i c hm a k eu s eo fe n g i n ew e i g h t sa n dd o c u m e n tr e l e v a n c es c o r e s w i t h t h e s ei m p r o v e m e n t s ，t h i sp a p e rp r o p o s e sa ni m p r o v e dc o m b m n zd a t af u s i o n a l g o r i t h m f i n a l l y , e x p e r i m e n tw i t ht r e cd a t as e t ss h o w st h ee f f e c t i v e n e s so ft h e n e wa l g o r i t h m r e l y i n go nt h es c h o l a rc o o r p e r a t i o np l a t f o r m ”s c h o l ”，t h i sp a p e ra l s o a p p l i e st h em e t a - s e a r c ht e c h n i q u et ov e r t i c a ls c h o l a rp a p e rs e a r c h i td e s i g n sa n d i m p l e m e n t sap e r s o n a l i z e dw e bs c h o l a rp a p e rs e a r c he n g i n e t h ee n g i n ep r o v i d e sb o t h c h i n e s ea n de n g l i s hs c h o l a rp a p e rs e a r c hs e r v i c ef r o md a t as o u r c ei n c l u d i n gc n k i ， i e e e ，g o o g l es c h o l a r , a n ds oo n f i n a l l y , t h ee x p e r i m e n ta n da n a l y s i sa l s os h o w st h e i m p r o v e m e n t sw i t ht h eh e l po fm e t a - s e a r c ht e c h n i q u 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 a - s e a r c h , d a t af u s i o l l ，a c a d e m i cs e a r c h i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 丛叁辞 日期： 211 1 ：堕：墨2 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名： 涨乏群 1 日期： 2 。1 4 年s 月二7 日 导师签名：t h 日期： 抄，年y 月7 日 第l 章引言 1 1 研究背景和意义 1 1 1 背景介绍 第1 章引言 互联网从诞生以来，无论是用户数量，还是互联网的内容，都得到了飞速的 增长。据中国互联网络信息中心发布的第2 5 次中国互联网络发展状况统计报告 显示，截至2 0 0 9 年1 2 月，中国网民规模达到3 8 4 亿，增长率为2 8 9 ，互联网 越来越深入到人们的生活和工作中。而与此同时，伴随网民规模的增长的是网络 内容的迅速膨胀。2 0 0 9 年，仅中国网页总数就达到了3 3 6 亿，年增长率超过了 1 0 0 。 网络资源的增长，一方面极大地丰富了人们的生活，但另一方面，“信息过 载”以及“资源迷向”，也使人们获取准确信息的难度越来越大。因此，信息检 索工具的重要作用日益突显。在日常生活中，g o o g l e 、y a h o o 、百度等传统搜索 引擎，已经成为人们上网必不可少的工具，它为查询和获取信息带来了便利。根 据g o o g l e 公司公布的数据，以及一些学者的估计，2 0 0 4 年底，g o o g l e 索引了近 8 0 亿个网页，至2 0 0 6 年中，索引网页达到2 5 0 亿个。然而，相比于网络资源的 膨胀速度，网页索引的增长速度仍然存在着数量级上的差距。据估计，常用搜索 引擎能够索引到的网页数量不到网页总数的十分之一，平均只能覆盖到整个网络 资源的5 一2 0 【1 1 。除了覆盖率上的不足，传统搜索引擎还存在着许多其他的缺 陷，包括数据库维护和更新困难、查询语义不统一、稳定性不高等。 为了提高搜索覆盖率，减少用户的重复搜索，元搜索技术由此出现。它通过 提供统一接口，联合多个搜索引擎，并对多个搜索引擎的返回结果进行合成与处 理，提高了单一搜索引擎的网络覆盖率，并避免了用户对多个搜索引擎进行重复 搜索。 从1 9 9 5 年e r i es 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 、p r o f u s i o n 、s a v v y s e a r c h 、m e t a f e r r e t 、 i n f i n d 、v i v i s i m o ，d o g p i l e ，以及国内的万纬、比比猫、搜魅网等。其搜索覆盖 中山大学硕士学位论文 率以及维护的简易性，使得它在理论上，以及应用中，都获得了越来越多的重视， 成为信息检索领域的一个研究热点。 1 1 2 研究意义 目前，许多传统搜索引擎虽然能够满足人们一定的需求，但在迅猛增长的网 络资源面前，也暴露出许多需要解决的问题，包括网页覆盖率的被动下降、查全 率有限，数据库更新慢、维护困难，冗余数据多等问题。相比之下，由于元搜索 引擎结合多个成员搜索引擎，所以从设计原理上看，利用了多个搜索引擎的长处， 扩大了查询覆盖率。并且，它也不需要有自己的数据库，从而避免了维护和更新 的难度。优点具体包括以下几点1 2 ： ( 1 ) 提高了查询的网页覆盖率以及查全率。 根据l a w r e n c e 和l e eg i l e s 的研究指出【3 】，传统的单一搜索引擎网页覆盖率 正在稳定地下降，其主要原因在于传统搜索引擎索引的网页数量增长率远远不及 全球网络资源的增长速度，单一搜索引擎平均只能覆盖到整个互联网资源的 5 2 0 。而元搜索引擎通过联合多个搜索引擎，无形中融合了多个引擎的底层 索引数据库，从而扩大了查询搜索的索引范围，获得比单一搜索引擎更高的查全 率以及查准率【4 1 。 ( 2 ) 避免了索引数据库维护难的问题。 网络信息的高速增长为传统通用搜索引擎带来的第二个难题是其索引数据 库的维护。一方面，传统通用搜索引擎如果要跟得上网络资源的高速增长，索引 数据库的规模也需要不断扩大，使得对数据库的维护难度也相应的提高：另一方 面，由于网络上信息的更新一般来说是不间断的，要使数据库中的信息及时性得 到保证，就要加强索引数据库的更新频度，而面对着越来越庞大的索引数据库， 索引更新的难度也越来越高。由于元搜索引擎是建立在其他成员搜索引擎的基础 之上，一般不需要有自己的索引数据库，从而间接地避免了索引数据库维护难的 问题。 ( 3 ) 提高搜索的稳定性。 对于单一搜索引擎来说，如果系统出现故障，就意味着搜索服务的中断。相 比之下，调用了多个成员搜索引擎的元搜索引擎，当其中某一成员搜索引擎出现 2 第1 章引言 故障时，仍然可以通过其他成员搜索引擎获得搜索结果。因此，元搜索具有相对 更高的稳定性。 ( 4 ) 有效地提高用户的查询效率。 在网络资源的不断增长，单一搜索引擎只覆盖一小部分资源的情况下，用户 在需要更为全面的相关信息时，只能通过多个搜索引擎进行多次查找，并根据自 己的判断从多个返回列表中选择自己需要的信息，这样的查询过程显然是重复、 效率低下的。另一方面，随着专业搜索引擎的发展，很多时候我们也需要从多个 索引数据库中获取所有的相关信息，例如，从a c mp o r t a l 、i e e e 、s p r i n g e r 等获 取某一主题的所有相关论文。显然，在这些情况下，如果通过单一搜索引擎，则 用户需要“遍历”多个搜索引擎的返回结果才能找到所有自己想要的，而且还需 要自己对这些信息进行消重，并根据自己的需要从多个列表中寻找自己有用的信 息。而通过元搜索技术，用户面对的是统一的接口，从而为用户提供更为便利的 查询服务，提高用户的查询效率。 ( 5 ) 灵活度高，可扩展用户个性化需求。 由于元搜索的组成部分基于多个成员搜索引擎，所以在实际应用中，可以根 据需要灵活地调用具体的成员搜索引擎，获得更为贴近用户需求的结果集，这也 是元搜索研究领域中的一个重要技术调度策略的目的所在。特别是对于具有 不同专业背景的用户，通过其个人信息库，可确定其领域范围，例如可根据用户 的专业信息，调用与其相关的专业搜索引擎，获得更为精确的数据。更深一步， 也可通过学习用户的搜索需求，使调度更趋合理。 基于以上的多方面优势，元搜索技术在信息检索领域中，无论是理论上还是 应用上均占有重要的地位。而同时，排序合成又是元搜索技术中最为关键的技术， 其算法优劣直接影响到元搜索的性能和返回结果的效果。并且，排序合成也是应 用层面上势必需要解决的重要问题，所以在元搜索技术中，排序合成具有重要的 研究意义。 1 2 研究内容和创新点 在元搜索技术的研究中，排序合成是一个关键的研究热点，甚至在许多外国 3 中山大学硕士学位论文 文献中，把排序合成( d a t af u s i o n ) 等同于元搜索( m e t a s e a r c h ) 进行研究。本文紧 紧围绕理论研究和应用这两个方面，对元搜索技术，尤其是排序合成技术展开探 索。 理论研究上，对元搜索最为关键的技术排序合成算法进行研究，具体以 无先验相似度函数、无先验成员搜索引擎权重、无训练数据下的排序算法研究为 重点，理论方面的主要工作如下： l 、透过传统搜索引擎与元搜索技术的基本原理的对比，分析了目前元搜索 技术存在的关键问题及主要的研究热点，指出了排序合成是元搜索技术中最为关 键的环节； 2 、对元搜索排序合成进行全面的综述，并主要对c o m b 系列算法、b o r d a 投票模型算法、贝叶斯概率模型算法等经典算法进行了深入的分析； 3 、目前已有的加权合成算法中，成员搜索引擎的权重值来源主要有两种， 一种是采用成员引擎的精确值，而现实中很难获取成员引擎的这些技术细节；另 一种通过机器学习的方法，对引擎权重值进行估计，但这种方法依赖于大量的训 练数据，对于新生的元搜索引擎来说也不太现实。本文以数据合成理论为基础， 并注意到文档和成员引擎之间相互推荐的关系，提出一种只基于各成员引擎返回 文档排位信息的自生成成员搜索引擎权重值的计算方法。 4 、以概率模型类算法的分值分布为启发，将浏览者模型引入分值的计算中， 得到不依赖于成员搜索引擎相似度函数的新的文档分值计算方法。 5 、结合自生成成员搜索引擎权重值，以及浏览者模型分值计算方法，提出 了改进的c o m b m n z 算法。并通过t r e c 9 进行实验，证实了自生成加权模型以 及浏览者模型对于算法具有显著的改进效果。 应用层面上，本文主要围绕科技攻关项目个人学术信息协同软件平台 “s c h o l ，将元搜索技术应用到垂直学术搜索中，设计并实现了基于个人学 术信息的个性化w e b 学术搜索引擎s c h o l s e 。该引擎主要提供中国期刊网、 万方、维普、i e e e 、a c m 、g o o g l es c h o l a r 等数据源的中英文学术论文和著作信 息检索，为学者提供有效的学术信息提取，信息补全以及学术信息检索服务。最 后，通过实验对比目前国内其他主要学术搜索引擎，证实了s c h o l s e 的有 效性。 4 第1 章引言 1 3 本文的结构 本文以元搜索排序合成为主线，主要从理论研究与应用两个层面对元搜索技 术展开研究。全文的组织结构主要如下： 第一章为绪论，主要介绍研究课题的研究背景、研究意义，并概述主要研究 内容和创新点； 第二章主要概述并对比传统搜索引擎以及元搜索技术的工作原理，并着重分 析元搜索的关键技术，提出排序合成研究是元搜索技术中最为关键的研究点； 第三章主要对国内外关于元搜索技术中的关键技术排序合成算法进行综述 与分析，并着重对三大经典排序合成算法进行介绍； 第四章基于数据合成特性，提出了一种自生成成员搜索引擎权重值，以及文 档相关度分值计算方法，并结合c o m b m n z 提出一种改进的排序合成算法； 第五章围绕基于个人科研信息协同软件平台“s c h o l ”，介绍了基于该平 台的w e b 学术搜索引擎的设计与实现； 第六章总结与展望主要是对全文进行总结，并对元搜索技术的未来研究方向 进行展望。 5 第2 章搜索引擎与元搜索技术 第2 章搜索引擎与元搜索技术 在这一章里，我们将要讨论本文所涉及到的基础知识，包括搜索引擎的基本 原理、分类、发展趋势等。基于搜索引擎的介绍，本章将引出元搜索技术以及其 关键技术。 2 1 搜索引擎概述 搜索引擎，就是在一定的模型或策略等的指导下，利用计算机程序获取互联 网上的信息，对这些信息进行处理组织，并在用户查询时将处理后的信息进行重 新组织排序返回给用户的应用，从而帮忙用户在浩瀚的网络海洋中找到自己所需 要的信息。 2 1 1 搜索引擎的发展历史 搜索引擎的发展理念应当追溯到1 9 9 0 年，加拿大麦吉乐大学计算机学院的 三名学生a l a ne m t a g e 、p e t e rd e u t s c h 以及b i l lw h e e l a n 发明了“a r c h i e 。它通 过定期搜集并整理f t p 服务器上的文件名信息，为用户提供“文件一主机 的 查询服务。只要用户输入想要查找的文件名，a r c h i e 就会告诉用户该文件的所在 主机地址。从“a r c h i e 的原理来看，它并不是一个真正意义上的搜索引擎，但 无可否认的是，它确实具备了搜索引擎的基本特征：自动搜索资源信息、建立文 件索引、提供查询服务等。并且，它也确实具备了搜索引擎的一些理念特征，即 为用户获取信息提供便利的查询服务。 1 9 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 的爬虫器装入索引程序中，创 建了第一个具有现代意义的搜索引擎一“l y c o s ”。同年，斯坦福大学的两名 博士生与美籍华人杨致远共同创办了目录索引“y a h o o 。这两者也可算是 全文检索系统和目录索引的鼻祖。自此，搜索引擎开始深入人心。 时隔一年，华盛顿大学硕士生e r i es 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 ”。该引擎的特点是用户只 7 中山大学硕士学位论文 需要提交一次请求，便可获得多个分散的搜索引擎所获取的结果。该引擎也标志 着元搜索技术的开始。 1 9 9 8 年，斯坦福大学的博士生l a r r yp a g e 、s e r g e yb r i n 等人在b a c k r u b 项 目的基础上构建了g o o g l e 搜索引擎。该引擎主要基于p a g e r a n k 技术，通过爬行 网页链接，判断网页的重要性，从而使搜索返回结果的相关度得到提高。现如今， 据估计，g o o g l e 索引的网页数据已达数百亿，并连续多年蝉联 t o p1 0 s e a r c h e n g i n e s 第一名。 此后，搜索引擎进入了突飞猛进的发展时期，众多搜索引擎陆续出现，包括 国内的百度、搜狗、搜搜等。搜索引擎也开始成为互联网的重要应用之一。 2 1 2 搜索引擎的原理和工作机制 虽然传统搜索引擎已经发展了很长时间，各个搜索引擎的具体实现也不尽相 同，但一般来说，传统搜索引擎可以分为网络机器人、网页分析器、索引器、检 索器和用户接口【5 1 ，具体结构如图2 1 所示。 图2 1 传统搜索引擎结构图 下面将简要介绍各主要部分功能： ( 1 ) 网络机器人 网络机器人也叫网络蜘蛛，主要负责网络资源的搜集。它通过递归执行“访 问链接地址、抓取网页和网页中新的链接地址、访问新的链接地址的过程，遍 历w e b 子空间，并通过多个网络机器人的同时运作，实现对网络资源的获取。 8 第2 章搜索引擎与元搜索技术 由于权限受限等原因，网络机器人并不能实现对需要访问权限的网页，以及基于 框架的页面、动态生成页面等的访问，这也是传统搜索引擎只能覆盖部分网络资 源的原因之一。 ( 2 ) 网页分析器 网页分析器1 5 1 对网络机器人抓取到的文档进行内容分析，以用于索引器进行 索引构建。网页分析器通常会对获取到的文档进行分词、过滤和转换等步骤。实 质上，这些步骤也可以看成是索引构建的预处理阶段。 ( 3 ) 索引器 索引器将【5 】文档表示成一种便于检索的方式并存储在索引数据库中，它对该 文档中分析得到的所有词条与相应出现的次数建立一种对应关系，使得查询时可 以通过这些信息和查询关键词计算相关度。一般来说，该模块是一个w e b 信息 检索系统能否取得成功的关键因素之一。目前，搜索引擎普遍采用的索引模型有 倒排文档、矢量空间模型、概率模型等。 ( 4 ) 用户接口 用户接口主要负责与用户进行交互，即为用户提供查询输入，并在查询完成 后进行结果输出。在输入页面中，用户依照搜索引擎的查询语法进行检索关键字 的输入，有些搜索引擎还提供高级检索设置；在完成检索后，用户接口将搜索结 果以线性列表的形式返回给用户。 ( 5 ) 检索器 检索器从索引中找出与用户的查询相关的所有文档，并按照相关度递减的顺 序进行排序。相关度的大小主要依据查询关键词与索引数据库中文档模型之间的 匹配程度。在最终返回的过程中，对与用户的查询是否相关的判断只是基于一个 阀值，而不一定需要与用户的需求完全一致。 2 1 3 搜索引擎的主要分类 目前，根据工作方式的不同，搜索引擎主要可以分为三大类f 6 】：全文搜索引 擎( f u l lt e x ts e a r c he n g i n e ) 、搜索目录索i ( s e a r c hi n d e x d i r e c t o r y ) 和元搜索引擎 ( m e t as e a r c he n g i n e ) 。层次结构如图2 2 所示。 9 中山大学硕士学位论文 。， 用户 ， 8 ： 信息检索a g e n t ， l i e夕 元搜索 l j 乞7 七多 气7 全文搜索搜索目录索引 弋 ， 88 网络资源 图2 2 信息检索信息层次图 ( 1 ) 全文搜索引擎 全文搜索引擎【6 】首先需要通过检索程序，如网络机器人，基于某种策略自动 在互联网中进行网页信息收集和抓取，由索引器根据抓取到的信息进行分析，并 建立索引数据库。用户查询时，通过w e b 索引数据库，检索与用户查询条件相 匹配的记录，并按照一定的方法对记录页面进行排序，最后返回给用户。 这种搜索引擎的特点是信息量大、更新及时、无需人工干预，但一般返回信 息多，多数情况下需要用户自行筛选。这一类搜索引擎的代表包括g o o g l e 、百 度、a r a v i s t a 等。此外，也有不需要网页爬虫，直接租用其他引擎的数据库进行 检索的搜索引擎，如l y c o s 。 ( 2 ) 搜索目录索引 搜索目录索引【6 1 ，是通过人工浏览发现各网页信息，采集后通过一定的分类 规则或知识体系进行分类，从而形成具有层次结构的w e b 信息资源目录清单。 目录中，每个分类对应一个专题，用户根据需要一级一级进行查找，直到发现目 标。 严格来说，目录索引并不算是真正意义上的搜索引擎，而是按目录分类的网 站链接列表。用户可以不通过关键词进行查询，而根据分类目录找到自己所需要 的信息。这种引擎的特点是目录结构清晰易懂、查找精确，但因为需要人工介入， 所以维护困难，而且信息更新不及时。这一类搜索引擎的代表有y a h o o 、o p e n 1 0 第2 章搜索引擎与元搜索技术 d i r e c t o r yp r o j e c t 、l o o k s m a r t 、a b o u t 等。 ( 3 ) 元搜索引擎 元搜索引擎是一种基于第三方搜索引擎的搜索引擎，它没有自己的索引数据 库，而是在用户发起请求时，将请求“翻译 成其他引擎的输入形式，并自动调 用多个第三方搜索引擎。在第三方搜索引擎返回结果后，元搜索引擎对结果进行 去重、排序等处理，最终按一定格式返回给用户。 这种搜索引擎的特点是间接地扩大了网络资源的覆盖率，返回的结果更多、 更全，并且不需要进行索引数据库的维护。但同时，由于它依赖于多个第三方引 擎，需要等待第三方搜索引擎返回结果，所以对网络质量依赖性较大，查询响应 时间可能较长。这类搜索引擎的代表有m e t a c r a w l e r 、d o g p i l e 、v i v i s i m o 、搜星、 万纬等。 2 1 4 搜索引擎的发展趋势 互联网日益增长的资源及信息，以及其信息异构性及动态特性，为搜索引擎 的发展带来严峻的挑战。人们在日益适应并依赖于搜索引擎的过程中，也开始关 心搜索引擎技术的下一步发展。有研究者提出，新一代搜索引擎应当在自然语言 处理、数据挖掘和机器学习技术、基于内容的多媒体查询技术、多通道用户界面 ( 语音、自然语言、多媒体) 方面有所突破f 7 1 。主要方面可以归结如下： ( 1 ) 查询自然化和友好化 目前的搜索引擎多为关键词全文检索或者目录式分类查找，前者不能很好地 理解用户想表达的查询诉求，导致查准率低；而后者则容易漏检，导致查全率较 低。 支持自然语言的输入，将极大地方便用户使用，同时也使搜索引擎可以更好 地理解用户的需求。目前已经出现了类似的自然语言智能问答系统，它通过分析 用户输入的结构及内容，从而识别用户查询的目的。用户只需要输入简单的疑问 旬，即可得到想要的答案，而不是像以前一样，根据关键词返回一个结果列表。 此外，在互联网丰富的多媒体资源背景下，未来的搜索引擎除了支持自然语 言的输入方式外，也应当支持包括声音、图像、视频等多通道查询输入。 通过对自然语言与多通道查询的研究和处理，可以拉近搜索引擎与人之间的 中山大学硕士学位论文 距离，使交互更为方便，同时也减小了用户从“列表 中查询结果的时间，提高 了查询效率。 ( 2 ) 查询个性化和本地化 具有不同年龄、性别、教育、专业背景、爱好等人群，对于相同问题的理解 以及搜索结果的要求都存在着差别，理想的搜索引擎应当能实现个性化的查找， 为特定的用户，或者用户群，搜索到特定的结果，以提高查准率。此前，y a h o o 、 e x c i t e 等公司曾推出一些本地搜索网站，实际上也提示了地域个性化和本土化的 搜索引擎发展趋势。 ( 3 ) 查询专业化和垂直化 在浩瀚的网络资源面前，传统通用搜索引擎很难对同一主题的网络资源都能 囊括其中。即使信息收集的足够全面，但由于引擎的针对性过于泛化，使得搜索 结果存在许多无用信息。正是在这种背景下，专业化、垂直化的搜索引擎应运而 生。各种垂直搜索引擎，如学术搜索、新闻搜索、股票查询系统等，以高度的用 户群针对性，为用户查询带来了较高的满意度，也使得它们在搜索引擎的发展趋 势中占据了重要的位置。 ( 4 ) 搜索结果的进一步优化 从搜索引擎的发展来看，最终的目的还是要提高查找的查全率和查准率， 个性化和垂直搜索使查准率提高了，但相应地由于各独立引擎只覆盖一部分资 源，而且以“专、精、深 为主要目标，使得相关结果的覆盖率可能有所下降。 因此，对搜索结果的进一步优化，使得在提高查准率的同时提高资源覆盖率，也 是研究中的一个重点。 从这一点上看，近十几年以来，元搜索技术不断得到发展，从原则上来说， 元搜索技术也应当能优化独立引擎的搜索结果，进而提高查全率。但实际应用中， 出于各方面限制，例如成员搜索引擎技术细节不可知等难题的存在，使元搜索的 优势并没有得到充分的发挥，而这些，正是有待进一步进行深入探索与研究的问 题之一。 2 2 元搜索引擎 据专家估计，传统搜索引擎平均只能覆盖5 至1 0 的网页，并且，由于各 1 2 第2 章搜索引擎与元搜索技术 搜索引擎的算法、采用机制及适用范围的不同，使得相同的搜索请求在不同搜索 引擎中的查询结果重复率不足3 4 。这也导致了传统搜索引擎在查全率和查准率 方面很难满足用户的需求f 8 】。因此，为了搜索到尽可能全面的信息，用户需要对 多个搜索引擎发起同样的检索请求，最后还需要自己对所有返回的结果列表进行 消重和重排序的处理工作。 为了提高用户的检索效率，提高搜索覆盖率，元搜 索技术应运而生。 2 2 1 元搜索引擎原理 元搜索引擎，实质上是基于一种双层“客户机一服务器的检索模型【9 1 ，如 图2 3 所示。当用户向元搜索引擎发起检索请求时，元搜索引擎采用一定的策略， 选择多个相应的第三方搜索引擎，并将请求按各引擎输入格式转化为实际请求； 第三方搜索引擎接收到实际请求后，做出响应，并将搜索结果返回给元搜索引擎； 元搜索引擎收集到各第三方引擎的返回结果列表后，根据一定的算法进行合并、 消重、排序；最后，元搜索引擎根据用户的定制模式将处理后的搜索结果返回给 用户。 画 画 用户 一次请求二次请求 图2 3 元搜索引擎双层请求模式 具体来说，元搜索引擎主要包括三大模块( 如图2 - 4 所示) f 1o 】：元搜索请求代 理、第三方搜索接口代理、搜索结果显示代理。 1 3 曰曰 中山大学硕士学位论文 图2 4 元搜索引擎结构图 下面将简要地对元搜索引擎的三个主要模块进行介绍： ( 1 ) 元搜索请求代理 元搜索请求代理【1 0 】主要进行“检索前设置 ，即根据需要对第三方搜索引擎 列表、搜索最长允许时间、返回结果最大数目等方面进行设置。目前，第三方搜 索引擎列表的确定方式主要有三种：一种是直接按照引擎默认设置调用固定引 擎，如w i d e w a y s e a r c h ；一种是由用户自己选择所要采用的第三方搜索引擎；还 有一种是利用个性化，通过用户的年龄、兴趣、专业背景等自动选择相应的第三 方搜索引擎。 目前，在这一模块上的研究主要集中在“调度策略 的研究上，即如何智能 地选择第三方引擎，以得到更为精确的搜索结果的问题。 ( 2 ) 第三方搜索接口代理 第三方搜索接i = 1 代型1 0 】主要进行“检索中设置 ，该部分介于元搜索和第三 方搜索之间，主要对用户的检索请求与第三方搜索引擎搜索规则进行组合，并负 责向第三方搜索引擎发送检索请求，在第三方搜索引擎处理结果后通过一定的机 制获取各独立搜索引擎返回的结果列表。其中，由于不同搜索引擎支持的检索方 式可能不同，表达方式也可能不同，为了在转化为实际检索输入时不丢失语义信 息，构建和维护好第三方搜索引擎规则库是这一模块中需要解决好的重要问题。 ( 3 ) 搜索结果显示代理 搜索结果显示代理【1 0 】主要负责对各成员搜索引擎返回的结果进行处理，具体 1 4 曰园 第2 章搜索引擎与元搜索技术 包括消除重复网页、合并结果集、重排序搜索结果，以及显示结果等方面。其中， 对返回的所有结果集的并集进行消重，以及对所有合并后的结果进行重新排序， 是该模块，乃至元搜索技术的关键所在。 从原则上来讲，元搜索合并技术得到的结果，应当是至少不劣于所调用的第 三方搜索引擎中的最优结果【1 1 1 。然而，由于大多数商业引擎的技术细节不是完全 公开的，尤其是相似度函数、排序算法、以及索引技术等。这使得元搜索引擎通 常很难实现无损合并。 目前排序合成的研究主要根据是否引用到各子引擎的相似度函数，以及是否 需要训练集对搜索引擎的权重值进行估计分为四大类。有关排序合成的具体概述 将在第三章进行，此处暂不详细描述。 2 2 2 元搜索引擎的分类 不同的元搜索引擎，在目标搜索引擎、检索提问的处理方式，以及如何编译 和显示结果等方面，都存在着比较大的差异。目前，对于元搜索引擎的分类主要 依据功能和运行方式两个方面【12 1 。按功能划分可以分为集成元搜索引擎和多线元 搜索引擎。 ( 1 ) 集成元搜索引擎 集成元搜索引擎【1 2 】实质上只是对第三方搜索引擎的简单罗列与介绍，并提供 这些搜索引擎的链接。当用户发起检索请求时，通过c g i 方式直接调用相应的 搜索引擎，并把返回结果直接内嵌到搜索结果页面，返回的内容一般不加任何处 理，与第三方搜索引擎上直接搜索到的结果一致。严格来说这类元搜索引擎不能 算是真正意义上的元搜索引擎，它没有统一的全局模式，也不对返回结果进行处 理。然而，它确实具备元搜索的一些特征，如不需要维护索引数据库、通过第三 方搜索引擎进行搜索等。 这类元搜索引擎的特点是技术实现简单，系统灵活性高，但由于没有对结果 进行处理，返回的数据对于查全率和查准率没有任何帮助。典型的集成元搜索引 擎有f r e e a l i t y 、p r o t e u si n t e r a c ts e a r c h 、q u e r y s t e r 等。 ( 2 ) 多线元搜索引擎 多线元搜索引擎【1 2 】是指通过统一的检索界面，对多个第三方搜索引擎同时发 1 5 中山大学硕士学位论文 起检索请求，并将检索结果以统一的格式返回给用户的元搜索引擎。与集成元搜 索引擎不同，这类元搜索引擎提供了统一的界面，除了提供给用户自由选择第三 方搜索引擎外，底层对第三方搜索引擎的调用对于用户来说也是透明的；在底层 调用上，多线元搜索引擎会根据知识库中存储的第三方搜索引擎的搜索方式、规 则等，自动将统一的用户输入格式转化为第三方搜索引擎的输入格式并转发给相 应搜索引擎；此外，更重要的是，这种搜索引擎会对搜索的结果进行处理，包括 合并、消重、重排序等，使得搜索的查询范围得到扩大。并且，最终也以统一的 格式返回给用户。 这类元搜索引擎的特点是用户交互界面简单，可以一次同时搜索多个第三方 搜索引擎。同时，由于其对结果集进行处理，根据一定的算法对结果集进行消重 和重排序，得到的结果只有一个列表，方便用户查看，也提高了查准率。目前比 较多的元搜索引擎都是采用这种方式，包括m e t a c r a w l e r 、万纬等。 另外，多线元搜索引擎按运行方式又可以分为桌面元搜索引擎和w e b 元搜 索引擎。 ( 1 ) 桌面元搜索引擎 桌面元搜索引