（计算机软件与理论专业论文）一种并行元搜索引擎的设计及相关问题研究.pdf

摘要 摘要 在这个信息爆炸的年代里，快速地、有效地在i n t e m e t 查询信息是一项 艰巨的任务。搜索引擎增强了人们定位和收集信息的能力，但现有的搜索 引擎在搜索效率、信息维护、信息重复、网络及站点负载等方面还存在着 很多不足，研究开发功能强大、覆盖面广、接口友好、返回信息准确的网 络搜索引擎已成为亟待解决的课题。 元搜索引擎正是满足这种需求的产物：它利用现有的独立搜索引擎的 查询性能，将它们看成一个整体，为用户提供一个统一的查询界面与返回 结果。本文针对现有元搜索引擎的局限性，改进了一个并行元搜索引擎的 框架，并探讨其内部的各个模块的具体功能、各模块的相互调用关系、系 统性能的评价与系统的应用前景。 成员搜索引擎调度技术是元搜索引擎的技术核心，本文提出了一种通 过基于搜索引擎性能评价的搜索引擎调度策略。面对着各成员搜索引擎不 同的参数入口，本文在抽取其它搜索引擎语法的基础上，形成了一个统一 的规范语法。 ， 针对一般元搜索引擎返回的信息相关性差，与用户最相关的信息不一 定排列在前面，本文改进了基于文摘，位置的加权排序算法。并且对该算法 进行评价。 最后，本文还提出了一个快速的“死链接”检测算法，并描述了无效 链接检测的过程。 关键词信息检索；搜索引擎；元搜索引擎；并行元搜索引擎；调度策略 燕山大学工学硕士学位论文 a b s t r a c t i nt h ee r ao fi n f o r m a t i o n e x p l o s i o n t 1 1 e f a s ta n de f f i c i e n ti n f o r m a t i o n s e a r c h i n g i ni m e m e ti sa l la r d u o u st a s k s e a r c he n g i n e se n h a n c eu st h ea b i l i t yo f l o c a t i n ga n dg a t h e r i n gi n f o r n q a t i o n 。b u tt h ee x i s t i n gs e a r c he n g i n e ss t i l l h a v e l o t so fd e f i c i e n c yo ns e a r c n n ge f f i c i e n c y , i n f o r m a t i o nm a i n t e n a n c e ，i n f o r m a t i o n r e p e t i t i o n ，l o a do f n e t w o r ka n dw e b s i t e s s oi t sa ne a g e r l yd e m a n dt or e s e a r c h a n dd e v e l o pas e a r c he n g i n ew i t hp o w e r f u lf u n c t i o n ，w i d ec o v e r i n g ，f r i e n d l y i n t e r f a c ea n da c c u r a t ef o e d b a c k 1 h em e t a s e a r c h e n g i n ei s t h e e x a c t l yr e q u i r e dt e c h n i q u e ，w h i c ha d o p t s t h e s ee x i s t i n gs e a r c he n g i n e s q u e r ya b i l i t y , r e g a r d st h e ma sa nu n i t y , a n db r i n g s l a s e r sa nu n i f o r mi n t e r f a c ea n df e e d b a c k r e s u l t s c o n s i d e r i n gt h el i m i t a t i o no f t h e e x i s t i n g m e t a - s e a r c h e n g i n e s ，t h i sp a p e r a m e l i o r a t e daf r a m eo fp a r a l l e l m e m - s e a r c he n g i n e s ，d i s c u s s i n gt h ed e t a i l e df u n c t i o n so fe a c hm o d u l ea n dt h e t r a n s f e r r i n gr e l a t i o n s h i p b e t w e e n t h e m ，m a k i n g e v a l u a t i o nt ot h e s y s t e m p e r f o r m a n c ea n df o r e c a s t i n go n t h ea p p l i c a t i o no f t h es y s t e m ， t h ed i s p a t c h i n gf o rm e m b e rs e a r c n n g e n g i n e i st h e k e yt e c h n o l o g yo f m e t a s e a r c he n g i n e t 1 1 i sp a p e rb r o u g h tf o r w a r dad i s p a t c h i n gs t r a t e g yb a s e do n t h e p e r f o r m a n c e e v a l u a t i o no f s e a r c h i n ge n g i n e c o n f r o n t t h ed i f f e r e n t p a r a m e t e ri n l e to f e a c hm e m b e rs e a r c he n g i n e ，t h i sp a p e rf o r m e dau n i t e da n d s t a n d a r dg r a m m a rb a s e do nt h ee x t r a c t i o no f o t h e rs e a r c he n g i n e s w i mt h ec o m m o nm e t a s e a r c he n g i n e s t h ei n f o r m a t i o np e r t i n e n c eo ft h e f e e d b a c k si si n s u f f i c i e n t t h em o s tr e l e v a n ti n f o r m a t i o nw i t l lu s e r sm a yn o tb e l i s t e da tt h ev e r yb e g i n n i n go ft h es e a r c hr e s u l t c o n c e r n i n gt h i s ，t h i sp a p e r i m p r o v e d t h ea l g o r i t h mo f w e i g h i n ga n do r d e r i n g b a s e do nt h ed i g e s t sp o s i t i o n a n df u r t h e re v a l u a t e dt h ea l g o r i t h m a tt h el a s tp a r to ft h i sp a p e r , t h ep a p e ra l s ob r o u g h tf o r w a r daf a s td e t e c t i n g a l g o r i t h m a b o u tf i x e dd e a d l i n ka n dd e s c r i b e dt h e d e t e c f i n gp r o c e s s o f i t a b s t r a c t i n e f f i c i e n tl i n k k e y w o r d si n f o r m a t i o nr e t r i e v a l ；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 ；p a r a l l e l m e t a - s e a r c h e n g i n e ；s t r a t e g yo f d i s p a t c h i n g 第1 章绪论 第1 章绪论 i n t e m e t 上的信息呈几何级数增长，网络用户越来越依赖于各种搜索引 擎查找信息，但快速有效地查询信息是一项艰巨的任务，这个需求直接导 致了广域网信息检索技术的快速发展，各类搜索引擎层出不穷。但是如同 网络的信息一样，搜索引擎的发展本身也是无序的，如何设计最符合需要 的搜索引擎是一个需要研究和解决的课题。 1 1 研究背景及意义 从商业角度来看，搜索引擎作为最有效的产品和信息查找工具的普及， 以及广告商寻求和获得客户的最佳途径，逐渐成为继广告、短信、邮箱后 的又一收入增长点，将是未来几年内成长最快的网络广告形式。 在国外，根据2 0 0 3 年7 月，美国知名投资银行b a n c o r pp i p e rj a f f r a y 发布 最新的搜索引擎研究报告。报告显示，在过去的1 8 个月中，作为最有效的 在线市场推广工具的搜索引擎发生了巨大变革。据u s b a n c o r pp i p e r , j a f f r a y 发布的搜索引擎市场研究报告表明，2 0 0 2 年全球的搜索引擎市场总收入共 为1 7 9 9 亿美元【l 】。其中收入的前四位依次为o v e r t u r e 、g o o g l e 、y a h o o 、m s n s e a r c h 。o o o g l e 、y a h o o 、m s ns e a r c h 的收入排名与浏览量排名形成正比。 预计2 0 0 3 年的全球收费搜索服务市场的规模将达至j j 2 0 亿美元，接近整个网 络广告市场2 5 的销售额。未来4 年里，搜索市场每年将以3 5 的速度增长， 至1 j 2 0 0 7 年，全球整个搜索市场的规模将达n 7 0 亿美元左右。而g o o g l e 、雅 虎、m s n 将是搜索引擎领域最重要的三家公司。 在国内，根据艾瑞市场咨询i r e s e a r c h 1 】统计，中国的搜索引擎市场2 0 0 3 年达到了5 亿元人民币，i = l 2 0 0 2 年的2 3 亿一年增长了1 1 7 显示了搜索引 擎市场的强劲增长。根据i r e s e a r c h 估计，今后三年内中国搜索引擎市场将 每年增长6 0 至7 0 之间，2 0 0 4 年中国搜索引擎市场可达8 4 亿元左右，2 0 0 6 年更可达2 3 亿元。这是一个巨大的诱人的市场。 1 燕山大学工学硕士学位论文 从网络用户使用普遍度情况来看，搜索引擎作为连接互联网的一座桥 梁，越来越受到人们的重视，现在有9 5 2 的网络用户在网络生活中会使用 搜索引擎，只有4 8 的人从不使用搜索引擎。此比例说明搜索引擎已经成 为网民在使用网络过程中不可或缺的重要工具。 虽然搜索引擎现在已成为用户利用因特网信息资源所不可缺少的工 具，但是搜索引擎现在的性能还不能令人满意，性能亟待优化。根据中国 互联网络信息中心的调查报告【2 j 显示，信息作为国家战略资源，2 0 0 3 年数 量成倍增长，但质量与利用效率却不高。i e e ei n t e r n e tc o m p u t i n 9 2 0 0 1 年的 统计也表明，一方面互联网每年产生2 x 1 0 ”字节的信息量，另外一方面却 只有2 1 0 1 3 字节被公众访问，利用率为0 0 0 0 1 5 ，著名的搜索引擎g o o g l e 只能搜索到8 1 x 1 0 9 网页【3 】。如何有效地利用网络信息资源，消除“信息孤 岛”，是摆在计算机科研及工程人员面前的迫切课题。现有搜索引擎的检索 技术已很难满足用户的要求，因此，结合传统的信息检索技术，综合利用 计算机网络技术、数据库新技术、代理技术、智能算法、计算机语言学等 多个领域的烟究成果来研究开发新一代的信息检索系统是具有重要理论意 义和广阔应用前景的。g o o g l e 成功的事实说明，搜索引擎技术的有效解决， 必将产生巨大的社会以及经济效益。 1 2 元搜索引擎技术的现状分析 随着互联网规模的急剧膨胀，独立搜索引擎( s i n g l es e a r c he n g i n e ) 无 法适应市场状况，满足用户需求。因此，搜索引擎研究者们寻求分工和协 作，由“分而治之”和“联合使用”的策略分别产生了专业搜索引擎 ( s p e c i a l i z e ds e a r c he n g i n e ) 和元搜索引擎( m e t a s e a r c h e n g m e l 。 元搜索引擎是一种调用其它独立搜索引擎的引擎，亦称“搜索引擎之 母”( t h em o t h e ro f s e a r c he n g i n e s ) 。在这里，“元”( m e t a ) 为“总的”、“超 越”之意i 4 ，元搜索引擎就是对多个独立搜索引擎的整合、调用、控制和优 化利用。相对元搜索引擎，可被利用的独立搜索引擎常称为“源搜索引擎” ( s o u r c ee n g i n e ) ，或“搜索资源”( s e a r c h i n gr e s o u r c e s ) ，整合、调用、控制 2 第1 章绪论 和优化利用源搜索引擎的技术，称为“元搜索技术”( m e t a - s e a r c h i n g t e c h n i q u e ) ，元搜索技术是元搜索引擎的核心。 元搜索引擎是用户只需提交一次搜索请求，由元搜索引擎负责转换处理 后提交给多个预先选定的不同的独立搜索引擎，并将从各独立搜索引擎返 回的所有查询结果，集中起来处理后再以整体统一的格式返回给用户。 1 2 1 元搜索引擎的应用现状 自从19 9 5 年w a s h i n g t o n 大学硕士生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 口】以来，这一新型的网络检索工具异军突 起，发展迅速，目前可用的元搜索引擎己近百种。元搜索引擎其以含盖较 多的搜索资源，能够在尽可能短的时间内提供相对全面、准确的检索结果 等诸多优异功能受到用户的青睐，已渐成为一种不可或缺的极具潜力的网 络检索工具。目前国内外主要的元搜索引擎有： ( 1 ) d o g p i l ed o g p i l e l 6 j 它是一个并、串行相结合的元搜索引擎，共收集 了8 个最流行的搜索引擎，提供w e b 检索、新闻组检索、音频检索、多媒 体检索，图案检索、f t p 检索、新闻检索、股市检索、黄页检索、白页检 索、地图检索、天气检索等。它的定制检索可以让使用者设置成人信息过 滤、多语言、拼写纠正等功能。有自己的网站目录和其它资源。返回结果 可以按所调用搜索引擎归类排序或按相关度排序。免费提供用户在自己的 主页上加入d o g p i l e 查询工具。 ( 2 ) m a m m am a m m a l 7 可以调用1 4 个独立的w w w 搜索引擎，它会分 析你所用的搜索关键词和句法结构，把它转化为符合各种搜索引擎的格式 分别进行搜索。由a s k j e e v e s 提供相关搜索的支持。可查询网上商店、新闻、 股票指数、图像和声音文件等资源。其特点是检索界面友好，检索选项丰 富，检索选项包括：可控制调用的独立搜索引擎、选择使用短语检索功能、 设定检索时间、设定每页可显示记录数等。m a m m a 支持常用检索语法在不 同搜索引擎中的转换，还提供了专门检索页面文件标题的特殊的检索服务， 以及通过电子邮件返回用户所需的检索结果的特色功能。检索结果以相关 性排序，内容包括网页名称、u r l 、文摘、源搜索引擎，有m a m m a 推荐网 3 燕山大学工学硕士学位论文 站。不仅仅可以对查询结果进行纠错整理，同时支持布尔和词组查询，而 且还提供用户在自己的主页上加入其图标。 ( 3 ) m e t a c r a w l e r 它是一个并行式元搜索引擎，是g 0 2 n e t 的一个组成 部分，除支持调用1 2 个独立搜索引擎，还提供涵盖将近2 0 个主题的目录 检索服务。其检索特性非常丰富，包括了常规检索、高级检索、定制检索、 国家或地区的资源检索等检索服务模式。其中，高级检索模式可实现：搜 索引擎的选择调用，基于域名、地区或国家的检索结果过滤，最长检索时 间设置，每页可显示和允许每个搜索引擎返回的检索结果数量的设定，设 定检索结果排序依据( 包括相关度、域名、源搜索引擎) 等。以上内容均可作 为定制检索的个性化选项并予以保存。另外，检索结果中包括一个以1 0 0 0 为最大值的相关度指标。 ( 4 ) i x q u i c ki x q u i c k i s 】可同时调用1 4 个主流的搜索引擎，对网站、m p 3 、 新闻、图像等多种网络资源进行搜索。在检索性能的完善程度上，i x q u i c k 突破了传统元搜索引擎在这方面的局限性，自称是“世界上功能最强大的 元搜索引擎”：支持各种基本的和高级的检索功能，包括关键词检索、短 语检索、截词检索、布尔检索、概念检索、自然语言检索、指定字段检索、 包含( + ) 或排除( 一) 检索等；尤其难能可贵的是，i x q u i c k 知道哪些搜索引擎 能够处理短语、布尔逻辑、截词等等，i x q u i c k 将负责把“翻译”后的查询 请求直接递交到那些能够处理这些复杂请求的搜索引擎中，实现更加有针 对性的搜索服务，瞄准更加高精专的检索结果。 ( 5 ) 万纬搜索引擎万纬搜索引擎【9 】是上海信息技术有限公司开发的一 个并行元搜索引擎，能并行搜索国内及国外的多个著名搜索引擎。由文献 【1 0 ，1 1 】可知万纬支持简单查询和高级查询。简单查询模式下，还提供结果 数量选择菜单；还提供“精确查找”功能，引擎将使用网页智能分析和精 确网络环境模拟技术，在最短的时间内，为用户提供最符合关键字的l o 条 结果，为节省用户时间。在高级搜索模式下提供独立搜索引擎列表，用户 可以根据自己的需要选择中、英文搜索引擎中的任何一个或数个引擎。同 时，用户可以根据需要设置搜索返回结果的排列方式可根据相关度、时间、 域名分类、引擎等项。此外，还可以设置最大等待检索时间、最大检索结 4 第1 章绪论 果限制。显示结果统计、网页标题、源搜索引擎标志、内容摘要等。 ( 6 ) m e t a f i s h e rm e t a f i s h e r i l 到中文元搜索引擎能够调用g o o g l e 、y a h o o 、 a 1 l t h e w e b 、百度、o p e n f i n d 等搜索引擎。其特色有：c o o r a n k 网页评级 系统，更好的优化结果的排序，向您提供网站的准确性参考；c o o w o r d ( b e t a ) 关键字自动分析归纳算法，协助增加搜索的深度与广度；相关搜索提示则 增加搜索灵感；使用多线程技术进行查询；提示修正可能错误的搜索关键 字；提供在结果页面直接预览网站功能。 1 2 2 元搜索引擎的研究现状 目前，人们对于搜索引擎存在的问题认识基本一致，主要集中在如下 多个方面：网络信息质量控制欠缺；大量占用昂贵的网络带宽和c p u 资源： 搜索引擎覆盖面有限；索引数据库更新困难，提供的信息滞后；搜索引擎 之间各行其是，缺乏合作；搜索速度不理想；误检率、漏检率高；搜索引 擎的功能尚待完善：检索结果重现性差；缺乏检索专业信息的能力：检索 过程的重复性；搜索引擎的知识产权问题等。 很多文献针对上述几个问题分别提出了自己的看法与意见，提出需要 重点研究的几方面：应该能充分表达用户查询要求的查询语言、索引数据 库的组织机制和管理、对信息进行准确的自动分类和标引、提高检索的查 准率与相关度、w e b 信息的发掘、支持多媒体检索、增强检索界面的友好 程度及提供个性化检索服务i l 引。 对于搜索引擎的索引数据库的组织机制与规模，人们认识到单个独立 搜索引擎的信息量是有限的，必须将各处的信息组织能力都集中起来，通 过协同工作来完成查询任务。 元搜索引擎集成多个独立搜索引擎，大大提高了检索覆盖面，对于专 业性不太强，甚至比较含糊的查询往往能够返回非常全面的结果，其本身 因为扩大了检索面，所以从一定程度讲，检索的准确性也会得到提高。 但是元搜索引擎有它固有的缺陷： 首先是查全率提高了，查准率却不容易控制，因为其检索结果主要来 自独立检索查询结果中排列靠前的记录。 e 燕山大学工学硕士学位论文 其次是检索功能简单，因为各个目标源搜索引擎的搜索机制、算法等 不尽相同，使它不能支持复杂检索功能。 因此，要提高这种集成的高效性，突显元搜索引擎的优势，非常困难。 很多研究人员为了攻克这个难关，给出了不同的算法和数据模型方案。 特别是随着x m l 的出现，有些系统正在用它建立数据源模型。但该数 据模型的方案不能广泛处理词条( t e r m ) j 顿序、逻辑操作符( l o g i c a lo p e r a t o r s ) 等的限制。虽然有人建议采用后续处理，但是后续处理往往花费大量的c p u 时间。而且，大多数情况下，元搜索引擎不能直接获得检索结果同查询相 关与否的信息，因而不太可行。 独立搜索引擎和元搜索引擎都属于集中式搜索引擎，有人提出集中式 搜索引擎有不可避免的缺科“】。它们很少能够与其它搜索引擎进行共享数 据，使得各搜索引擎的“机器人”重复访问同一w e b 站点，这将造成以下 后果：增加信息源网站的负载；网络重复传输页面，浪费带宽：因用户使 用多个搜索引擎查询同一内容时，往往需要花费很大精力区分返回的重复 信息，给用户查询带来额外的负担。这都难以适应网络规模的日益扩大。 分布式搜索引擎主要是分布式搜索引擎按区域，主题或其它标准创建 分布式索引服务器【l5 。索引服务器之间可以交换中间信息，且查询可以被 重新定向。如果一个检索服务器没有满足查询请求的信息，他可以将查询 请求发送到具有相应信息的检索服务器。由于分布式搜索引擎将索引数据 库划分到几个分布的数据库中，每个数据库相应变小。但所有搜索引擎覆 盖的范围变大，且很少有信息重复。而作为分布式系统特性之一的可扩充 性也是分布式搜索引擎的优点之一。 分布系统研究的一个重点是如何建立好的组织机制。但是，分布式搜 索引擎实现的关键是要求各搜索引擎拥有统一的索引数据库访问接口，或 者提供其它搜索引擎访问自己索引数据库的接口协议。有人建议采用1 9 9 5 年最新修订的z 3 9 5 协议( 这是在客户服务器环境下计算机与计算机之间进 行数据库检索和查询的通信协议) ，但是这又需要在用户服务器端提供 h t t p z 3 9 5 的转换等，实现依然非常困难【l6 1 。实际上，我们可以将该协议 应用在基于数字图书馆的元搜索引擎。 6 第1 章绪论 1 3 本文的研究内容和组织结构 1 3 1 本文的研究内容 如何有效地利用网络信息资源，提高搜索引擎的查准率和查全率，满 足用户的要求，元搜索i 引擎作为新一代的信息检索系统是具有重要理论意 义和广阔应用前景的。本文首先概述了元搜索引擎的原理与现状，分析其 存在的不足，并提出一个改进型的并行元搜索引擎框架，重点探讨其实现 的关键技术及策略，同时编写相关的关键实现代码。本文试图从下面几个 方面来进行研究： ( 1 ) 搜索引擎的选择策略； ( 2 ) 返回信息相关性排序算法； ( 3 ) 查询参数转换规范； ( 4 1 无效链接检查算法。 本课题的总体目标是在现有搜索引擎技术的基础上，结合传统的信息 检索技术，综合利用计算机网络技术、数据库新技术、代理技术、智能算 法、计算机语言学等多个领域的研究成果来研究开发新一代的信息检索系 统模型，并解决这一模型中所涉及到的信息预处理、结果分类等个性化关 键技术问题，最终建立以信息检索为应用背景的试验模型。 1 3 2 本文组织结构 全文共分五章，具体的章节内容安排如下： 第1 章为绪论，介绍了论文研究的背景和意义，概述了当前元搜索引 擎方面商业与研究方面上的情况。最后介绍了本文的主要研究内容和论文 的组织。 第2 章分别介绍了独立搜索引擎和元搜索引擎的原理与工作机制，并 对两者进行了一些性能比较。这章主要侧重在元搜索引擎方面的介绍。 第3 章提出一个并行元搜索引擎的框架，并对各个模块进行设计，探 讨所涉及到的关键技术。 7 燕山大学t 学硕士学位论文 第4 章详细探讨了并行元搜索引擎系统中的任务分配模块。提出了一 个基于成员搜索引擎评价的选择搜索引擎策略。并且介绍了本系统的查询 参数转换。 第5 章具体介绍了并行元搜索引擎的返回结果处理模块的设计。并且 提出了一个基于文摘位置的加权排序算法。同时提出了一个简单的对无效 链接检查的算法。 第2 章搜索引擎概述 2 1 引言 第2 章搜索引擎概述 搜索引擎一词在国内外i n t e m e t 领域被广泛应用，但是其含义却不尽相 同。在国外，搜索引擎通常指基于i n t e m e t 的搜索引擎，他们收集i n t e m e t 上的网页，并且每个网页上每个词都被搜索引擎所收录，这通常是大家所 说的全文检索【1 7 】。典型的i n t e m e t 搜索引擎包括g o o g l e 、h o t b o t 、y a h o o 。 在国内，搜索引擎通常指的是基于网站目录的搜索服务或特定网站的搜索 服务。前者如搜狐( h t t p ：w w w s o h u c o r n ) 、新浪( h t t p ：w w w s i n a c o m ) 等公司 开发的垂直网站搜索服务，后者如百度( h t t p ：w w w b a i d u c o m ) 网站提供的全 文检索服务。本文所指的搜索引擎均为基于i n t e m e t 的搜索引擎。 最早现代意义上的搜索引擎始于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 。同年4 月，斯坦福( s t a n f o r d ) 大学的两名博士生，d a v i df i l o 和美籍 华人杨致远( g e r r yy a n g ) 共同创办了超级目录索引y a h o o ，并成功地使搜索 引擎的概念深入人心。从此搜索引擎进入了高速发展时期。目前，互联网 上有名有姓的搜索引擎已达数百家，其检索的信息量也与从前不可同日而 语。比如，最近几年颇得人心的g o o g l e 搜索引擎，其数据库中存放的网页 已达8 1 亿之巨1 2 2 搜索引擎的分类 搜索引擎的分类有许多不同的方式伸】： ( 1 ) 按照检索方式划分为全文检索引擎及目录式分类搜索引擎。 ( 2 ) 按照不同的检索范围如地域、语言、专业、时间、网站进行分类。 ( 3 ) 按照搜索引擎检索信息的方式进行分类。有以下几种类别：布尔逻 辑型、模糊逻辑型、向量空间型、概率型等。 9 燕山大学工学硕士学位论文 ( 4 ) 按照搜索引擎的位置划分为基于客户的搜索引擎、基于单个服务器 的搜索引擎、基于多个服务器的搜索引擎、分布式的搜索引擎。 ( 5 ) 按照搜索引擎所在网站分为门户网站搜索引擎、专业网站搜索引擎、 公司网站搜索引擎等。 ( 6 ) 按照索引技术分为目录式、蜘蛛式及元搜索引擎。目录式与蜘蛛式 的统称为独立搜索引擎。i 以上仅简单列举了几种搜索引擎分类的方式，为了讨论方便，在以下 的章节里将以独立搜索引擎和元搜索引擎的方式划分搜索引擎。 2 3 独立搜索引擎 启示搜索引擎并不真正地、实时地搜索互联网，它搜索的实际上是预 先整理好的网页索引数据库。它也不能真正理解网页上的内容，它只能机 械的匹配网页上的文字 1 9 】。 2 3 1 独立搜索引擎的组成与原理 真正意义上的搜索引擎，通常指的是收集了互联网上几千万到几十亿 个网页并对网页中的每一个文字( 即关键词) 进行索引，建立索引数据库的全 文搜索引擎。当用户查找某个关键词的时候，所有在页面内容中包含了该 关键词的网页都将作为搜索结果被搜出来。在经过复杂的算法进行排序后， 这些结果将按照与搜索关键词的相关度高低，依次排列。 现在的搜索引擎已普遍使用超链分析技术，除了分析索引网页本身的 文字，还分析索引所有指向该网页的链接的u r l 、a n c h o r t e x t 、甚至链接 周围的文字。 一般独立搜索引擎的主要框架大致包括以下的四个功能模块：网页采 集模块、索引组织模块、检索模块、用户接口模块1 2 ，如图2 1 所示。用 户接口负责接收用户查询要求和返回相应的结果信息，采集器负责从互联 网上收集到原始网页或网页信息的描述，检索器则负责找出符合用户要求 的信息。它们以索引数据库为联接，高效的索引组织方式有利于高效的查 1 0 笙：至堡墨! ! 兰堑鎏 询匹配的实现，从而有助于系统检索性能的提高。从这个意义上讲，检索 器和索引器是整个搜索引擎系统的核心。 lr o b 。t 索引 嚣b 组织 麓b 模块t模块 r o b o t 广广一 ll 小h l r o b o t i 文档库索引库 ll 图2 - 1搜索引擎的框架结构图【2 。1 f i g 2 - 1t h ef r a m e t a b l eo f g e n e r a ls e a r c h e n g i n e 【2 0 】 由文献 2 0 2 2 可知，独立搜索引擎的原理，可以看作三步：从互联网 上抓取网页一建立索引数据库一在索引数据库中搜索排序。 ( 1 ) 从互联网上抓取网页利用能够从互联网上自动收集网页的 r o b o t ( 也叫s p i d e r 、c r a w l e r 或w a n d e r e r ) 系统程序，自动访问互联网，并沿 着任何网页中的所有u r l 爬到其它网页，重复这过程，并把爬过的所有网 页收集回来。 ( 2 ) 建立索引数据库是由分析索引系统程序对收集回来的网页进行分 析，提取相关网页信息( 包括网页所在u r l 、编码类型、页面内容包含的所 有关键词、关键词的位置、生成的时间、大小、与其它网页的链接关系等1 ， 根据一定的相关度算法进行大量复杂计算，得到每一个网页针对页面文字 中及超链中每一个关键词的相关度( 或重要性) ，然后用这些相关信息建立网 页索引数据库。 ( 3 ) 在索引数据库中搜索排序当用户输入关键词搜索后，由搜索系统 程序从网页索引数据库中找到符合该关键词的所有相关网页。因为所有相 关网页针对该关键词的相关度先前已经计算好，所以只需按照现成的相关 度数值排序，相关度越高，排名越靠前。最后，由页面生成系统将搜索结 果的链接地址和页面内容摘要等内容组织起来返回给用户。 搜索引擎的r o b o t 一般要定期重新访问所有网页( 各搜索引擎的周期不 1 i 燕山大学工学硕十学位论文 同，可能是几天、几周或几个月，也可能对不同重要性的网页有不同的更 新频率) ，更新网页索引数据库，以反映出网页文字的更新情况，增加新的 网页信息，去除死链接，并且根据网页文字和链接关系的变化来重新排序。 这样，网页的具体文字变化情况就会反映到用户查询的结果中。 2 3 2 独立搜索引擎的主要评价指标 对搜索引擎进行评价就是根据给定的指标体系，采用一定的方法和程 序，对搜索引擎及其各部分的功能、特性和运营状况进行评测，以确定其 达到的水平和现存的主要问题。 对搜索引擎进行评价具有重要意义。通过评价可以找出其存在的缺陷 及其主要原因，为进一步改善提供依据；通过评价可以丰富搜索引擎的理 论研究和实践经验，从而有助于新的搜索引擎的设计与完成；通过评价可 以确定某一单个搜索引擎的质量和特点，既有助于宣传搜索引擎，又利于 根据需要的类型确定正确选择搜索引擎的原则和方法。 评价搜索引擎检索性能的主要有两个指标：查全率和查准率。 假设检索变化如下表2 1 变化表所示。 表2 - 1 文档变化表 t a b l e2 - 1t h et a b l eo f d o c u m e n t a lv a r i e t y 相关的文档无关的文档 己检索的文档 in - - - r + | 没有检索的文档bdm = b + d c - - r + bl = l + d n o 一- - r + 1 + b + d 那么，查全率( r e c a l l ) 和查准率( p r e c i s i o n ) 定义如下i ”j ： r = 圭= 二 (21)cr + 6 、。 p ：= i r ( 2 2 ) ，+ z 、7 除了查全率和查准率外，另外还有几个指标也是比较常用的：布尔函 数支持，响应时间，死链接比率等评价指标口4 1 。对用户来说的，则主要的 第2 章搜索引擎概述 评价标准是界面是否友好，是否接收自然语言，是否能进行模糊检索等。 2 4 元搜索引擎 元搜索引擎是搜索引擎中非常特殊的一类，它是集成了多个独立搜索 引擎而建立起来的。它涉及到的很多机制和技术与独立搜索引擎类似。本 节主要是针对元搜索引擎同独立搜索引擎不同的地方进行分析与阐述。 2 4 1元搜索引擎的组成与原理 元搜索引擎，通过一个统一的界面、调度模块帮助用户在多个搜索引 擎中选择和利用合适的( 甚至是同时利用若干个) 来实现检索操作，是基于对 分布于网络中的多种检索工具的全局控制机制建立起来的。它克服了独立 搜索引擎的弊端，使用户一下子就能得到多个搜索引擎针对某一查询结果 返回的结果，而不是一个个地去查询。 元搜索引擎可看成具有双层客户机服务器结构的系统，用户向元搜索 引擎发出检索请求。元搜索引擎再根据该请求向多个搜索引擎发出实际检 索请求；搜索引擎执行元搜索引擎检索请求后将检索结果以应答形式传送 给元搜索引擎，元搜索引擎将从多个搜索引擎获得的检索结果经过整理再 以应答形式传送给实际用户【2 5 。如图2 ，2 所示。当然，某些元搜索引擎具 有略微不同的机制。 f 检索请求代理li 结果显示代理i l 检索垂代理l t ；裹主i 厂f l l独立搜索引擎i ，2 ，3 n 图2 - 2 元搜索引擎原理图 f i g 2 - 2t h ep r i n c i p l ef i g o f m e t a - s e a r c he n g i n e 1 3 燕山大学工学硕士学位论文 由文献 2 6 一v 3 0 1 可知，一个真正的元搜索引擎基本是由三部分组成，即： 检索请求提交机制、检索接口代理机制、检索结果显示机制。请求提交机 制负责实现用户“个性化”的检索设置要求，包括调用哪些搜索引擎、检 索时间限制、结果数量限制等。接口代理机制负责将用户的检索请求“翻 译”成满足不同搜索引擎“本地化”要求的格式。结果显示机制负责将所 有源搜索引擎检索结果进行汇集、筛选、去重、合并等优化处理后，以统 一的格式在同一界面集中显示。 元搜索引擎虽没有网页搜寻机制，亦无独立的索引数据库，但在检索 请求提交、检索接口代理和检索结果显示等方面，均有自己研发的、独特 的元搜索技术支持。如提交检索请求时，根据源搜索引擎的特点和相关技 术参数，指定优先顺序，并对检索时间、检索结果数量进行控制；作为若 干个源搜索引擎的检索接口代理，元搜索引擎必须具有较强的字符和语法 转换功能，使用户的检索请求为各具语法特点的不同的源搜索引擎所接受； 而对检索结果的显示，不同的元搜索引擎有不同的处理技术，由于元搜索 引擎设定的检索结果排序依据、最大返回结果数量、相关度参数及优化机 制等不同，调用相同的源搜索引擎的不同元搜索引擎显示检索结果的数量 多少、排序先后、结果信息描述选择亦有较大差异 2 9 】。 2 4 2 元搜索引擎的分类 元搜索引擎有多种分类方式，如根据用户应用模式、调用独立搜索引 擎的方式进行分类【3 0 】。按功能划分，元搜索引擎包括集成搜索引擎和多线 索式搜索引擎；按运行方式的差异可分为桌面型元搜索引擎和基于w e b 的 元搜索引擎。按照工作方式，元搜索引擎可分为并行处理式和串行处理式 两大类。并行处理式元搜索引擎将用户的查询请求同时转送给它调用链接 的多个独立型搜索引擎进行查询处理，串行处理式元搜索引擎将用户的查 询请求依次转送给它调用链接的每一个独立型搜索引擎进行查询处理。 ( 1 ) 集成搜索引擎集成搜索引擎( a u i n - o n es e a r c h p a g e ) 亦称为“多引 擎同步检索系统”( 如生命家园网) 是指搜索引擎界面以任意顺序或分类罗列 多个搜索引擎，搜索引擎本身主要提供各类搜索引擎的介绍信息和物理连 1 4 第2 苹搜索引擎概述 接机制1 3 ”。这类元搜索引擎没有统一的全局外部模式，而是以各搜索引擎 的检索模式和数据格式直接面对用户，即直接把来自多个搜索引擎的搜索 结果列在一个页面上，不作重新计算或更改。其实质是利用网站链接技术 形成的搜索引擎集合，严格来说这类元搜索引擎只是独立搜索引擎的简单 罗列，不能算真正意义上的元搜索引擎。集成搜索引擎无自建数据库，不 需研发支持技术，当然也不能控制和优化检索结果。但集成搜索引擎制作 与维护技术简单，可随时对所链接的独立搜索引擎进行增删调整和及时更 新，尤其大规模专业( 如f l a s h 、m p 3 等) 搜索引擎集成链接，深受特定用 户群欢迎。 典型的集成搜索引擎：搜星搜索引擎 3 2 】、生命家园网口卦、搜索之家 3 4 j 、 p r o t e u s t 3 “、q u e r y s t e r 圳等。 ( 2 ) 多线索式元搜索引擎多线索式元搜索引擎是指利用统一的检索界 面，实现对多个独立搜索引擎索引数据库进行检索，并将检索结果以统一 格式显示的网络检索工具。这类元搜索引擎一般具有以下特征f 3 7 】： 统一检索界面：元搜索引擎提供统一界面，提供对各搜索引擎特点介 绍和选择机制，但所有目标搜索引擎构成一个逻辑整体，元搜索引擎检索 界面构成唯一的全局外部检索模式，用户通过这个全局界面实现对多个或 任意一个搜索引擎的检索。检索指令转换：在具有唯一全局外部检索模式 情况下，系统可提供统一的全局指令语言，并自动地实现元搜索引擎指令 与其目标搜索引擎指令的转换，用户使用同一指令语言检索不同的搜索引 擎的索引数据库。统一结果集的组织与显示：元搜索引擎提供全局组织机 制，对各目标搜索引擎返回的结果进行处理，形成全局结果集，并以统一 格式显示，主要涉及数据格式转换、去重、统一排序等。 典型的多线索式元搜索引擎比较多，主要的有：万纬搜索、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 ) 桌面型元搜索引擎桌面型元搜索引擎是以程序的方式提供给用 户，相当于用户自己拥有一个元搜索引擎。它运行在用户的机器上，用户 的查询请求直接由用户端分发给它所调用的搜索引擎，然后对返回的搜索 结果进行集成后以一定的方式显示。桌面型元搜索引擎是一个包括多个成 ，5 燕山大学工学硕士学位论文 员搜索引擎的完整系统，它们往往允许用户自定义检索式运行的搜索引擎 集合( 例如一个或全部目标搜索引擎) ，甚至可由用户添加新的搜索引擎。这 些桌面型元搜索引擎不仅可以实现对多个搜索引擎的并行检索，而且能提 供重要的后期处理功能。如用户定义结果排序方式、删除重复记录等功能。 典型桌面型元搜索引擎：飓风搜索通 3 8 】、s e a r c h w o l f f 3 9 1 、b e e l i n e 4 0 1 等。 ( 4 ) 基于w e b 的元搜索引擎基于w e b 的元搜索引擎是以w e b 方式为 用户提供元搜索引擎。请求代理、检索接口代理和结果显示代理都存放在 元搜索引擎所在的服务器端。在这种方式中，用户的元查询请求经过服务 器端的请求提交代理和检索接口代理将查询请求分发给它所调用的独立搜 索引擎，这些独立搜索引擎返回的搜索结果由服务器端的结果显示代理处 理后再返回给用户。 基本上多线索式元搜索引擎都属于基于w e b 的元搜索引擎。比如国内 的万纬搜索，国外的m e t a c r a w l e r 、d o g p i l e 等。 2 4 3 元搜索引擎的主要指标及其分析 作为一种搜索引擎，元搜索引擎也有普通的搜索引擎的一些基本指标， 例如响应时间、准确率等。但元搜索引擎个体差异很大，很难进行精确的 比较。根据文献f 2 9 - 3 0 ，下面给出元搜索引擎的几个主要指标，而涉及到 目标源搜索引擎的，则采用2 3 2 所述的指标来进行简单评估。 ( 1 ) 选择独立搜索引擎的策略是否允许用户浏览并且选择需要调用的 独立搜索引擎，是否采用自动选择还是采用手动选择等。 ( 2 ) 覆盖网络资源的广度是否能覆盖多种网络资源类型，是否可提供 主题范畴的目录服务等。 ( 3 ) 是否提供足够的检索选项和功能设置是否支持平行检索，是否提 供逻辑匹配检索、短语检索、自然语言检索等高级检索服务，是否能够实 现检索请求的本地化转换，是否可设置每个搜索引擎返回的检索结果数量， 是否能够自动检测链接的有效性等。 ( 4 ) 对搜索结果的处理能力是否注重检索结果的输出格式，检索结果 的信息描述是否全面等。最常见的形式是，将各个独立的搜索引擎所返回 1 6 第2 章搜索引擎概述 的结果进行集中的去重处理后，以统一的输出格式和相关