（计算机软件与理论专业论文）元搜索引擎缓冲及排序的相关研究.pdf

摘要 摘要 在社会信息化不断进步的过程中，互联网已经成为人们日常生活以及工作中 不可或缺的工具。搜索引擎在互联网中是重要的一部分，而且随着网络中信息量 的不断增加和信息更新速度的不断加快，最快地从网上得到最重要的信息已经成 为网络用户的重要需求，这就更凸显了搜索引擎的重要作用。随着搜索引擎的发 展，元搜索引擎作为新生事物，也正在起着越来越重要的作用。 本文从提高元搜索引擎搜索结果的排序质量以及加快响应速度出发，对元搜 索的排序和缓冲调度进行了研究，从有效性和实用性等方面改进了现有的算法， 并通过在w i n d o w s 环境下利用v i s u a l1 2 # 2 0 0 5 开发的一个小型系统s e a r c h e r - a ， 对这些改进的算法进行了实现，通过与改进前的排序情况和响应时间进行比较， 改善元搜索的性能。 s e a r c h e r - a 中主要包括搜索结果提取模块、排序模块、缓冲模块、用户管理 模块。涉及到的相关技术有搜索结果提取模块中的网页源码分析及标签树的构 建，搜索结果提取，摘要分析；排序模块中的f d c 算法的改进及相关分析，缓 冲模块中的缓冲调度算法分析及改进，以上内容均通过程序进行了试验，通过试 验已经得到相关数据和结果，而实验过程中的一些具体算法，如搜索结果提取中 的队列实现方式，f d c 算法，缓冲调度算法等，文中也将进行详细阐述。 关键词元搜索；结果提取；摘要分析；缓冲调度；结果排序 a b s t r a c t a b s t r a c t a st h ei n f o r m a t i o n - b a s e ds o c i e t yi m p r o v i n gf a s t t h ei n t e m e th a sb e e 心m et h e i n d i s p e n s a b l et o o lo fp e o p l e sd a i l yl i f ea n dw o r k s e a r c he n g i n ei s8 1 1i m p o r t a n tp a r t o ft h ei n t e m e t w i t ht h ei n c r e a s i n gc a p a c i t ya n du p d a t i n gs p e e do fi n f o r m a t i o ni nt h e n e t w o r k , t og e tt h em o s ti m p o r t a n tm e s s a g ei m m e d i a t e l yh a sb e c o m et h eu s e r s p r i m a r yd e m a n d , w h i c hf u r t h e rh i g h l i g h tt h es e a r c he n g i n e si m p o r t a n tr o l e w i t ht h e d e v e l o p m e n to fs e a r c he n g i n e s ，m e t as e a r c he n g i n ea san o v e l t y , i sa l s op l a y i n ga m o r ea n dm o l - ei m p o r t a n tr o l e t h i sd i s s e r t a t i o nr i m sa ti m p r o v i n gt h eq u a l i t yo fm e t as e a r c he n g i n e sr e s u l t r a n k i n ga n dt h er e s p o n s es p e e d w i t ht h es t u d yo ft h ee x i s t i n gr a n k i n ga l g o r i t h m sa n d c a c h ea l g o r i t h m s ，ih a v em a d es o m ei m p r o v e m e n t sf i o mt h ee f f e c t i v e n e s sa n d p r a c t i c a l i t yo fs u c hi m p r o v e m e n t st ot h ee x i s t i n ga l g o r i t h m s w i t hv i s u a lc # 2 0 0 5 d e v e l o p m e n tt o o l ，ih a v em a d eas m a l ls e a r c h i n gs y s t e mw h i c h i sn a m e ds e a r c h e r - a t oa c h i e v et h e s ea l g o r i t h m so nt h ew i n d o w s c o m p a r e dw i t ht h ef o r m e rr a n k i n ga n d r e s p o n s et i m e ，t h i ss e a r c h i n gs y s t e mi sb e t t e ri n e f f e c t s e a r c h e r - am a i n l yi n c l u d e ss e a r c hr e s u l t se x t r a c t i o nm o d u l e ，s o r t i n gm o d u l e ， c a c h em o d u l e ，u s e rm a n a g e m e mm o d u l e i n v o l v e di nt e c h n o l o g i e sr e l a t e dt ow e b s i t e $ o u r c ec o d ea n a l y s i sa n dc o n s t r u c t i o no fl a b e lt r e ea n ds t a t i s t i c sa n a l y s i si ns e a r c h r e s u l t se x t r a c t i o nm o d u l e ，f d cr a n k i n ga l g o r i t h mi m p r o v e m e n t sa n dc o r r e l a t i o n a n a l y s i si ns o r t i n gm o d u l e ，c a c h ea l g o r i t h ma n a l y s i sa n di m p r o v e m e n ti nc a c h e m o d u l e t h ea b o v ee l e m e n t sh a v ea l lp a s s e dt h et e s tp r o c e d u r e s ，a n dih a v eg o t8 0 m e r e s u l t s s o m es p e c i f i ca l g o r i t h m ss u c ha su s i n gq u e u et og e tt h es e a r c hr e s u l t s ，f d c a l g o r i t l l l n ，c a c h ea l g o r i t l u nw i l lb cd e t a i l e d l ye l a b o r a t e d k e y w o r d sm e t as e a r c h ；e x t r a c ts e a r c hr e s u l t ；s u m m a r ya n a l y s i s ；c a c h es c h e d u l e ；r e s u l tr a n k m - 独创性声明 本人声明所里交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：盂边日期：三盟：望! 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 0 ， 签名；盔逆导师签名- 五五么! l 日期：二班， 第1 章绪论 1 1 研究背景 第1 章绪论 i n t e r n e t 和其他形式信息服务的迅速发展，使人们能够比以往更容易、更直 接地获取各种形式的信息。但是由于i n t e r n e t 是一个开放、分布的信息空间， 它本身所固有的3 个特点己经极大地阻碍了人们充分地使用i n t e r n e t 上的信息 资源： i n t e r n e t 上可利用的信息是缺乏良好组织的、多种结构形式的，并且分 布在全世界的各个站点上； 数据和服务的类型以及数量每天都在大量增加，因而信息可利用性和可 靠性也在不断地变化： 由于数据源的动态性以及潜在的有用信息的更新和保存问题，信息常常 是模糊的，有时甚至是错误的。 基于上述原因，在i n t e r n e t 上查找有用的信息具有一定的困难，出现了“富 数据穷信息”的问题。如何迅速、有效地从大量数据中找至所需要的信息已经成 为信息服务领域中重要的、亟待解决的问题。当前已经开发了各种搜索服务系统， 帮助人们发现和收集i n t e r n e t 上的信息。其中最常用的是搜索引擎系统。根据 e x c i t e 的统计，平均每天有2 0 ，0 0 0 ，0 0 0 个用户通过该搜索引擎共作了 5 8 0 ，0 0 0 ，0 0 0 次页面浏览。根据y a h o o 的报告，每天有3 5 ，0 0 0 ，0 0 0 个用户通过 该搜索引擎作了1 6 7 ，0 0 0 ，0 0 0 次页面浏览。这些数据显然说明了当前的搜索引擎 系统为千千万万网络用户提供了大量服务【l 捌。 虽然搜索引擎系统确实能够帮助人们发现有用信息，但是，人们发现这些搜 索引擎系统存在一些不足之处。首先，对网络用户来说，他们希望能够在整个 w e b 的范围中发现和收集有用信息。然而，大量的研究表明，没有一个单个的搜 索引擎能够索引到w e b 上的全部文档。也就是说，没有任何一个当前的搜索引擎 能够在整个w e b 范围中为网络用户提供文档查找服务。事实上，根据1 9 9 9 年5 月s e a r c h e n g i n e w a t c h 网站上的统计报告，现在索引w e b 文档最多的搜索引擎系 a l t a y i s t a 也只索引了3 1 3 的w e b 文档。所以，对于一个特定的查询请求，当 前没有一个搜索引擎系统能够提供大规模的w e b 信息搜索。研究表明，虽然没有 一个单个的搜索引擎能够提供大规模的信息搜索，联合使用多个搜索引擎能够提 供较大规模的信息搜索。在这种情况下，元搜索引擎系统应运而生。 元搜索查询是一种以现有的w e b 搜索引擎系统为基础的查询方法，以这种方 法构造的w e b 页面查询工具被称为元搜索引擎。元搜索引擎本身不通过蜘蛛程序 为w w w 建立索引，因此既不需要维护庞大的索引数据库，也不需要构造复杂的搜 北京工业大学工学硕士学位论文 索引擎。一般地，它为用户提供了简单、统的集成查询界面：用户的查询请求 被转换成各个搜索引擎所能识别的格式，然后发送给这些搜索引擎，真正的查询 过程由它们来完成。因此，各个搜索引擎服务系统中的索引系统是元搜索引擎的 资源库及基础工具。元搜索引擎收集到各个索引系统返回的结果后，经过处理以 一定的格式返回给用户。由元搜索引擎的研究思想可以看出，以这种方法构造的 w e b 文档查询工具具备了以下优点0 , 3 川： 由于元搜索方式可以依次让多个索引信息系统并行查询，即同时利用了 多个索引数据库，查询的覆盖面得到了有效的扩大。 由于各个搜索引擎对文档相关性的评估存在较大的差异，用户可以从不 同的“观点”的结果中进行选择，增大了命中其原意的概率。 由于不需要考虑索引数据库的建立和维护工作，元搜索引擎的开发者可 以把重点放在结果的处理上，以帮助用户尽可能快的找到其所需要的文 档。 给用户在使用上带来很大的方便，免除了用户在各个索引系统问不断的 转换，不断地适应各种不同的界面、结构、格式的麻烦。尽管元搜索引 擎一般不提供各种复杂的i n t e r n e t 服务，但是它的简单明了对只需要输 入关键字查询的用户来说是非常受欢迎的。 根据调查，一方面，对于某个用户而言，他提交的搜索请求大约有1 6 - - - 2 2 是已经在以前被提交过的，另一方面，对于所有用户而言，大约有3 0 9 6 4 0 的 搜索请求是类似或者完全一样的。大部分的搜索请求都是在很短的时间间隔内被 重复提交的，但是也有一些搜索请求是经过相对较长的时间间隔而被重复的，当 然后者大部分是在不同用户之间的重复。因此，随着网络搜索引擎的规模越来越 大，为了给用户一个比较满意的响应时间，比较专业的搜索引擎都采用了缓冲技 未。 1 2 研究目的和意义 现有的元搜索系统一般只是将从各个独立搜索引擎搜集到的结果进行简单 的罗列，因此往往在前几页的结果显示上很难满足用户的需求，而且对于每次重 复检索都要向各个独立的搜索接口发送请求，必然会耗费大量的时间。为了更好 地对元搜索结果进行排序，减少重复搜索的时间，构建了搜索系统s e a r c h e r a 。 s e a r c h e r - a 主要包括搜索模块、排序模块和缓冲模块，其中搜索模块可以将各 大搜索引擎的结果集提取并显示，缓冲模块通过将各种不同的调度算法应用在缓 冲区上，来对响应时间、命中率进行对比和比较，从而选择出最合适的调度算法， 排序模块设计了一个优化的排序算法，以改进排序的质量，这些对于提高目前元 搜索引擎的使用效率和改进元搜索的排序都会有一定的研究和参考价值。 第1 章绪论 1 3 国内外知名的元搜索引擎 ( 1 ) i n f o g r i d ( h t t p ：向w i n f o g r i d c o r n ) 3 3 , 3 4 1 提供与主要搜索网站的直接连结和目录检索，具有强大的元搜索和新闻搜索 功能。 ( 2 ) i n f o n e t w a r er e a l t e r ms e a r c h ( h t t p ：w w w i n f o n e t w a r e c o i i i ) 原为检验网络分类技术而设计。它以元搜索引擎知名，但具有强大的对搜索 结果进行主题分类的功能。与众不同的是，用户可选择不同的主题，并得到 来自所有主题搜索结果，而不是仅仅把搜索结果限制在一个主题范围之内。 ( 3 ) i t h a k i ( h t t p ：w w w i t h a k i n e t d i r h t m l ) 支持包括中文在内的1 4 种语言检索。 ( 4 ) i x q u i c k ( h t t p ：w w w i x q u i c k c o m l ) 可搜索网站、m p 3 、新闻、图象等多种网络资源。 ( 5 ) p r o f u s i o n ( h t t p ：w w w p r o f u s i o n c o m ) 拥有智能化的搜索方案，提供诸如搜索引擎选择、检索类型、结果显示、摘 要选项、链接检查等较多的检索选项，支持个性化设置，可以选择三个最好 的搜索引擎、或三个最快的搜索引擎、或全部搜索引擎、或手工选择任意几 个搜索引擎来进行搜索。自动实现符合特殊检索语法要求的转换，如在调用 e x c i t e 、i n f o s e e k 、w e b c r a w l e r 时将“n e a r ”转换成“a n d ”，在调用g o t o 、 y a h o o 时 铲n o t ，删除等。原为堪萨斯州大学所有，2 0 0 0 年四月被i n t e l l i s e e k 搜索公司购买。 ( 6 ) m a m m a ( h t t p ：w w w m 删n c o m ) 1 9 9 6 年面世，自称为“搜索引擎之母”的并行元搜索引擎，可同时调用7 个 最常用的独立搜索引擎，并且可查询网上商店、新闻、股票指数、图像和声 音文件等资源。其特点是检索界面友好，检索选项丰富，主要包括：可控制 调用的独立搜索引擎、选择使用短语检索功能、设定检索时间、设定每页可 显示记录数等。另外，m a m a 支持常用检索语法在不同搜索引擎中的转换， 还提供了专门检索页面文件标题的特殊检索服务，以及通过e 一腮i l 传输检 索结果的特色功能。检索结果以相关性排序，内容包括网页名称、u r l 、文 摘、源搜索引擎。 ( 7 ) m e t a c r a w l e r ( h t t p ：w w w m e t a c r a w l e r c o m ) 1 9 9 5 年由华盛顿大学推出，1 9 9 7 年被i n f o s p a c e 购买。支持调用1 2 个独立 搜索引擎，提供涵盖近2 0 个主题的目录检索服务。其检索特性非常丰富， 包括常规检索、高级检索、定制检索、国家或地区的资源检索等检索服务模 式。其中，高级检索模式可实现：搜索引擎的选择调用，基于域名、地区或 北京工业大学工学硕士学位论文 国家的检索结果过滤，最长检索时间设置，每页可显示的和允许每个搜索引 擎返回的检索结果数量的设定，设定检索结果排序依据( 包括相关度、域名、 源搜索引擎) 等。以上内容均可作为定制检索的个性化选项并予以保存。另 外，检索结果中包括一个以1 0 0 0 为最大值的相关度指标。 ( 8 ) b y t e s e a r c h ( h t t p ：w w w b y t e s e a r c h c o m ) 搜索速度快，可检索资源丰富，搜索范围包括w e b 、城市信息、公司名录、 域名、f t p 网站、多媒体、新闻组、包裹跟踪等，并提供新闻浏览、u r l 提 交、最新的2 0 个检索浏览、联机商店等内容方面的服务。支持完全匹配( a 1 1 ) 、 部分匹配( a n y ) 、短语检索( p h r a s e ) 等特性检索功能，没有搜索引擎列表， 不能控制源搜索引擎的选择。 ( 9 ) s a v v y s e a r c h ( h t t p ：s a v v y c s c o l o s t a t e e d u ：2 0 0 0 ) 支持二十种语言( 不包括中文) ，可调用全部或任意几个搜索引擎，可选择每 个搜索引擎返回结果的数日，可进行目录检索。 1 4 论文架构 本文的其余部分主要内容是： 第二章，介绍了信息检索、搜索引擎和元搜索引擎的基本知识，包括信息检 索的基本理论模型、搜索引擎的基本模型及现状、搜索引擎的优势和缺陷、元搜 索引擎的体系结构、搜索引擎常用排序算法、元搜索引擎缓冲区的常用调度算法、 国内外知名的元搜索引擎等。 第三章，详细讲述s e a r c h e r - a 中搜索结果提取模块的设计，这也是用户和 s e a r c h e r - a 系统交互的模块，将详细阐述搜索结果提取过程中的几个主要步骤， 网页源码分析、提取结果的两种方法：构造标签树进行提取、构造队列进行提取， 与排序模块相关联的摘要分析、词频统计、距离计算等，在本章都将进行详细的 分析。 第四章，分析基本的f d c 算法及其改进算法，其中f d c 算法主要是利用普通 词和关键词之间的共现词频、共文档率以及相互之间的距离关系，来获得关系最 为密切的词，作为关键词的共现词集，再利用共现词集来调整排序效果的一种算 法，本章抓住普通词和关键词之间的距离这一关键因素，提出平均距离和随机距 离两种不同度量方式，进而对算法和排序都有不同的调整效果。 第五章，详细分析各种缓冲调度算法及本系统的相关改进方案，其中l r u 算 法基本没什么变化，但是f b r 和s l r u 算法都进行了相应的改进。使用缓冲区包 括将搜索结果添加到缓冲区和从缓冲区中提取搜索结果。本系统的设计思路是： 将搜索结果添加到缓冲区时，先对搜索出的结果文本进行解析，根据采用的缓冲 第l 章绪论 调度算法，先将搜索结果一个个地添加到缓冲队列中，再将缓冲队列中的结果添 加到本地缓冲文件中；而从缓冲区中提取结果时，也是先从本地缓存文件中读取 结果到缓冲队列中，再从缓冲队列中提取合适的结果显示。缓冲区的管理主要是 定期将缓存文件中的结果集进行更新以及对各个缓冲队列进行整理。 第六章，介绍本系统的整体架构及其他各模块的测试情况。在s e a r c h e r - a 系统中，除了前面三章中的搜索结果提取模块、排序模块、缓冲模块外，还有一 些辅助的模块，如用户登录模块、用户管理模块、缓存管理模块、用户日志管理 模块等。本章将对这些其它模块的测试情况进行分析。 第七章，总结与展望。 1 5 本章小结 本章是绪论部分，从现在搜索引擎和元搜索引擎存在的问题出发，阐述了构 造s e 盯c h e r - a 系统的目的和意义，另外介绍了一下现在国内外比较知名的元搜索 引擎，最后是整篇论文的架构分析。 苎：兰里墨兰耋皇丝窒! ! 兰 第2 章信息检索与搜索引擎 2 1 信息检索的基本理论模型 信息检索主要研究对整个文档信息的表示、存储、组织和访问。一个好的信 息检索系统不仅要求将输出信息进行相关性排列，还应该根据用户的意图、兴趣 和特点通过自适应和智能化的调查匹配机制，使用户获得满意的检索结果。 最常用的信息检索性能度量是检索的查全率和查准率。一般认为，检索的查 准率为检索结果中有用的相关文档数与检索到的查询结果总数之比，而检索的查 全率为满足用户查询要求或相关于查询要求的信息与被检索出的结果集之间的 比率 5 1 。 本节将详细讨论信息检索领域的基本的模型、技术和方法。 2 1 1 概念 信息检索( i n f o r m a t i o n r e t r i e v a l ，d 泛指用户从包含各种信息的文档集中查找 所需要的信息或知识的过程。随着当今社会各个领域知识的迅猛发展，信息以爆 炸式的方式增长，致使信息的种类繁多，格式复杂，除了纯粹的文本、数字内容 以外，还包括图形图像、声音、视频等多媒体格式的文档。由于信息的范围扩展， 在这里我们把信息检索的任务看作是用户给定信息需求后，从文档集中识别并返 回最为匹配的文档。 2 1 2 过程及组成 信息检索的过程模型示意图如图2 1 所示1 6 , 7 s l 。 北京工业大学工学硕士学位论文 文本信息源用户 i r li 文档资源或文档 i 用户需求l j 1r 文档的表示d f 索引) i- l 匹配过程| i 查询表示q 。 检出文档 工 修改文档表示 h 评价或利用检索结果卜一查询优化( 相关反馈) 图2 - 1i r 的一般模型及检索过程 f i g u r e2 - 1s t a n d a r dm o d e la n dp r o c e s s i n go f i r 在图中可看到，信息检索的系统主要包括： - 文档模型：即文档的索引，也就是文档内容的识别和表示，包括语义内 容和上下文属性( 如作者、编辑者等) ； 一查询模型：即用户需求信息的获取与表示； _ 匹配函数：即在文档表示和查询的基础上，定义查询和文档的相关度函 数； _ 性能评价：一般采用查准率( p r e c i s i o n ) 和查全率( r e c a l l ) 对检出的结果进 行评价，处理速度有时也用于评价系统的效率； -反馈修正过程：根据检出的结果对查询表示( 少数情况下也对文档表示) 进行扩充与参数优化，以提高系统性能。 由于任何系统都存在一定的非线性，要确切描述是不现实的，因此，一般 来讲，任何个信息模型都有其理论基础和假设。在信息检索系统中的一些普遍 性的假设如下： _ 被检索对象主要为文档对象。 一检索是根据文档内容的表示及所需信息的表示进行的。 兰：兰堡垦竺墨兰垫耋! ! 兰 2 1 3 数学模型 基于模型的文本检索技术的核心是检索模型。6 0 年代中期以来，人们提出 了大量检索模型。从最初的一些较小的和较为结构化的文档所设计的特殊模型 ( 如文献记录，包括题目、作者和主题词等) ，发展到现在具有较强理论基础和能 处理多种文档格式的模型。当前的模型能够处理具有复杂内部结构的文档，并且 一般都具有学习和利用相关反馈进行查询优化等功能，使得系统性能大大提高。 检索模型主要包括三方面的内容：文档与用户查询的表示：查询匹配策略：匹配结 果的相关度表示。几种常用的信息检索模型是布尔模型、概率模型和向量空间模 型 g a o a i 。 ( 1 ) 布尔模型 严格匹配模型( e x a c tm a t c hm o d e l ) 是根据用户提交的检索条件，利用匹配 函数，将文档集分为匹配集合和不匹配集合。在匹配的文档子集中，文档一般不 在匹配程度上进行排序。当然可以根据文档日期、字母顺序或其他属性来排序。 严格匹配模型中最简单并且最常用的一种是布尔模型。 布尔模型是一种简单的严格匹配模型( e x a c tm a t c hm o d e l ) ，也是其他检索 模型的基础，它定义了一个二值变量集合来表示文档，这些变量对应于文档中的 特征项，一般是由训练文档集中的词条或短语组成i 砼j 鲥。如果词条对文档内容有 贡献，则赋予t r u e ，否则置为f a l s e 。在查询与文档匹配的过程中，主要看该文 档中的词条是否满足查询的条件。 一个查询是由一些通过逻辑操作符号( 如a n d ，o r 和n o 下) 连接起来的关键 词所组成，例如“( 软件0 r 说明书) a n d 计算机a n d 网络”，该查询可以形式化 为。aa n dba n dc 。，它将比aa n db ，选中更少的文档。一般说来，在布尔模 型中，用a n d 连接的关键词越多，获取的文档就越少，而且文档数量的减少将非 常明显。而用0 r 连接的关键词越多，获取文档的数量也就越多。因此为了提高 用户查询的精度，用户在查询过程中应该尽量将查询的需求描述清楚，以减少获 取文档的数量。但是因为匹配结果的二值性，是无法在匹配结果集中进行查询结 果的相关性排序的。 布尔模型在六、七十年代得到了较大发展，也出现了许多可以应用的商业 系统和某些的网站，但现在己经不是十分常用。 北京工业大学工学硕士学位论文 p 范数模型是对布尔模型的扩展，它克服了简单布尔模型匹配函数过于严格 而导致漏检率高的致命缺陷。在p 范数模型中，假设文档d 可表示为 d ：( d l ，d 一d 。) ，用户查询可表示为q = ( q 。，q 一，q 。) ，其中d ，和q j 分别表示第 i 个特征词条对文档内容和查询内容的贡献程度，d 。，q 。在 o ，1 的区间取值。 定义文档与查询间的相似度如下公式( 2 - 1 ) 所示。 s i m ( d ，o ) = 1 一 q f o - d ，y q 。9 j - l ( 2 一1 ) 其中1 p 一。根据具体应用改变d 。，q 。和p 的取值即可达到不同的检 索效果。当p 一一，且d 。的取值为0 或l ，q ，= q 产= = l 时，p 范数模型则退 化为简单布尔模型。在实际使用中p 的取值由实验得出，取值范围一般为 2 ，5 。 ( 2 ) 概率模型 在信息检索中存在不确定性问题，对查询本身来说，它不能唯一地表示信息 需求，对于结果来说，不能判定查询结果的正确与否。对于布尔检索也是如此， 因为查询的提交本身就是一种不确定性方式。为了解决布尔检索模型中的不确定 性问题，引入了概率检索模型。概率模型则考虑到了词条、文档间的内在联系， 利用词条间和词条与文档阃的概率相依性进行信息检索。 信息检索的概率论模型的基础是概率排序规则：如果文档按照与查询的概率 相关性的大小排序，那么排在前面的文档是最有可能被检索的文档。 信息检索的主要任务就是计算文档与查询之间的相关性。一个查询由来自一 个固定的关键词空间的关键词组成，一个文档由来自同一关键词空间的关键词集 合组成，即d o e = 。如果文档满足如下公式( 2 - 2 ) 则该文档将被检出 3 6 , 3 1 1o 叫r c 4 历c ) p ( n o t r e 4 d o c ) ( 2 2 ) 其中p ( r e lid o e ) 表示文档d o c 与查询有关的条件概率，p ( n o t r e lld o e ) 表 示文档d o e 与查询不相关的条件概率。 根据贝叶斯规则( b a r e s ) ，式2 - 2 可以改写成式2 3 ： p ( d o c l r e i ) p ( r o i ) p ( d o 二。c l n 。o t r e 。1 ) p ( n 2 o t r 。e 1 ) 1 ( 2 - 3 ) 所获取的文档可以利用上式的左端进行排序。利用概率计算的主要问题是怎 样计算这些概率，这可以通过计算相关性己知的文档样本来得到。如果查询串由 一个关键词组成，或者组成查询串的关键词之间相互独立，那么每个与文档中的 第2 章信息检索与搜索引犟 词条匹配的查询词条的相关性通过如下公式( 2 - 4 ) 表示： w 2 f 砚r 万( r 厕- r ) ( 2 川 其中，n 是样本集合中文档的数量，n 是样本集合中包含该词条的文档的数 量，r 是与查询相关的文档数目，r 是与查询相关而几包含该词条的文档数日。 这样查询q 可以表示为 ，其中w - 由以上公式计算得到。文 档d 表示为 ，其中如果关键词存在于文档中，则对应的x l = l 反之则 x i = 0 。这样可以定义查询串q 与文档d 之间的相似度函数，如公式( 2 - 5 ) 所示。 i s i m ( q ，d ) = 以坼 k = l ( 3 ) 向量模型 向量空间模型( v s m ：v e c t o rs p a c em o d e l ) 是近年来使用较多且效果较好的 一种信息检索模型。v s m 自从g s a l t o n 等人成功地用于著名的s m a r t ( s y s t e mf o r t h em a n i p u l a t i o na n dr e t r i e v a lo ft h et e x t ) 系统之后，该模型及其相关的 技术，包括项的选择，加权策略，以及采用相关的反馈进行查询优化等，在文本 分类、自动索引、信息检索等许多领域得到了广泛的应用 1 4 , 1 5 】。 在v s m 中，将文档看作是由相互独立的词条组( t 。，t 。l ) 构成，对于每 一词条t i ，都根据其在文档中的重要程度赋以一定的权值w 。权重越大，则相应 关键词对于该文档来讲越重要。文档向量中的词条的权重般基于词条在文档中 出现的频率，在知道文档向量和查询串向量后，就可以计算文档向量与查询串之 间的相似度。有多种计算向量之间相似度的方法，用的比较多的是两个向量的标 准化点积。并将t i ，t 2 l 看成一个n 维坐标系中的坐标轴，w 。w z ，碥为对应 的坐标值。这样由( t j ，t 2 ，t 。) 分解而得的正交词条矢量组就构成了一个文 档向量空间，文档则映射成为空间中的一个点。对于所有文档和用户查询都可映 射到此文本向量空间，用词条矢量( t 。wt , w 。t n w 。) 表示，从而将文档信息 的匹配问题转化为向量空间中的矢量匹配问题。假设用户查询为q ，被检索文档 为d ，两者的相似程度可用向量之问的夹角来度量，夹角越小，说明相似度越高。 相似度计算公式如下公式( 2 6 ) 所示。 w 耻 在实际操作中。n 个关键词向量空间并不意味着每个文档都需要用n 个权重 表示，由于每篇文档往往都只是跟某个主题有关，这样大多数的权重都为0 。因 北京工业大学工学硕士学位论文 此，在实际存储文档向量时，只是将那些权重不为0 的关键词与对应的权重放在 一起。这样在计算过程中不需要使用很多内存空间。 ( 4 ) 其它模型 在此三种模型的基础上还有更多的扩展模型。可供选择的集合理论模型有： 模糊集合模型、扩展布尔模型等：语义标引模型、神经网络模型等：可供选择的代 数模型：广义向量空间模型、潜可供选择的概率模型：贝叶斯网络模型、信任度网 络模型等。另外对于不同结构的文档也有不同的模型：推理网络结构化文本检索 模型：基于非重叠链表的模型、基于邻近结点的模型等。浏览模型：扁平浏览模型、 结构导向模型、超文本模型等。 2 2 搜索引擎基本模型 目前网络上有大量的搜索引擎向用户提供服务，它们的功能各异，所提供的 服务也相对多样，部分搜索引擎拥有庞大的数据源资源和强劲的硬件设施做后 盾，有的小巧玲珑而个性鲜明，有的搜索引擎从互联网上收集各类信息资料，有 的则获取、加工其它搜索引擎的反馈结果，既有向所有用户提供统一信息服务的 通用搜索引擎，也有针对某一领域的专业搜索引擎，虽然如此，但它们的基本工 作原理是相同的i l 。 一个典型搜索引擎有三个不同的部分组成：一是收集数据的网络蜘蛛 ( s p i d e r ，又称为网络机器人) ，二是数据维护系统，它负责对所得到的资源信 息进行整理、分类、检索和更新，三是搜索引擎的用户查询系统，这三部分各有 分工，在搜索引擎中完成不同的工作，它们所处理的对象、工作的原理有较大的 差异，图卜2 是一个搜索引擎的工作原理图： 图2 - 2搜索引擎工作原理图 f i g u r e2 - 2 t h ep r i n c i p l eo f s e a r c he n g i n e 1 2 釜：苎笪墨兰霎主堡至：! 兰 图中的三个虚线框所分割开的部分分别是网络机器人、数据维护系统和用 户查询系统。它们之间的关系和分工可以从图中很清晰地看出：网络机器人根据 u r l 地址在网络中漫游、并把收集到的资源信息传送回搜索引擎的数据源：数据 维护系统的工作就是对这些取回的数据进行加工处理，对数据的分类、索引，同 时也要完成数据的存储、更新等工作，这些工作由图卜2 中间的虚框所包含的模 块完成：图1 - 2 右侧的虚框完成用户查询，被称为用户查询系统，该系统对用户 提出的查询要求进行分析并向数据源提交，再将检索结果返回给用户。一般用户 直接接触的只是用户查询系统的界面部分。比如输入所要查询的词句，然后按下 搜索键，再就等待返回的查询结果。看上去很简单，实际上为了向用户提供丰富 而有效的服务，搜索引擎有许多的内部工作需要完成，下面将讨论这三个部分的 工作原理 1 6 1 7 , 1 s 。 2 2 1 网络机器人 网络机器人实质是一种特殊的客户端程序，对于网站来讲，和我们所用的浏 览器并没有什么不同。我们通过浏览器访问特定u r l 地址的互联网资源，控制浏 览器的u r l 定向、链接的跳转，而浏览器负责获取被访问资源并以适当的形式( 文 本、图像、音频、视频或文件等) 返回。在浏览过程中，浏览器的访问行为是被 动的、由用户驱动的，访问模式是交互的【”捌。 网络机器人也是通过u r l 地址定向地访问网络资源，获取相应的数据，它们 的行为是由某些算法程序控制，不需要人为的干预，它们的访问行为和模式是主 动的、自主的，它可以分析得到的数据资源，提取出自己所需要的新的u r l 地址 信息( 超级链接) ，这样它根据新的u r l 地址有访问新的资源。 通过超级链接可以访问到互联网上的所有资源，这样在理论上，网络蜘蛛就 可以自动地访问到所有的互联网资源，搜索引擎的数据源可以得到整个互联网的 数据【2 1 矧。但实际上互联网的资源数量实在太多，而且更新速度很快，将整个互 联网的数据都收录入搜索引擎数据源是根本就不可能的。这样就需要一些控制策 略来调整、引导网络蜘蛛的搜索行为，譬如搜索域的划分、搜索深度的控制、数 据更新时间的调解等，图1 - 3 即一个网络蜘蛛的工作原理图： 北京工业大学工学硕士学位论文 图2 3网络蜘蛛工作原理图 f i g u r e2 - 3t h ep r i n c i p l eo fn e ts p i d e r 图中虚线所分割出的是网络蜘蛛部分，可以看出它是由一个数据获取传送模 块和一个策略控制模块构成：数据获取传送模块负责直接从网络上获取所需要的 互联网资源，并传送至搜索引擎的数据源之中，策略控制模块执行前述的各种控 制策略：具体引导模块获取数据的行为。因为实际应用中网络蜘蛛的搜索过程是 多线程井发进行的，所以在这张原理图中标出了多个搜索过程。 2 2 2 数据维护系统 网络蜘蛛将所得到的互联网资源传回搜索引擎的数据源，接下来的工作就 由数据维护系统负责了。 数据维护系统的工作主要分为三个部分：一是对数据源中的信息资源进行 分析、整理归类的数据索引系统，第二部分是数据源的维护工作，包括数据的存 储、访闯，第三部分是数据源资源的更新。下图卜4 是数据维护部分的工作原理 图： 器k 竺 图2 _ 4数据维护工作原理图 f i g u r e2 4 t h ep r i n c i p l eo f d a t am a i n t e n a n c e 1 4 - 第2 章信息检索与搜索引擎 从图中可以得出三个部分之阆的关系。其中数据的更新部分实际上由数据更 新控制模块与网络蜘蛛共同完成。它们在数据更新过程中需要交换各种控制信 息 数据维护系统的工作中有很大一部分是基于数据源的操作，前面讲到过互联 网数据与传统数据源所处理的对象有很大的不同，比如数据索引部分，传统数据 源的索引功能是针对某些字段进行的简单排序工作，而搜索引擎的数据索引部分 要复杂得多，它是基于文档内容的提取技术，即文档向量模型，在搜索引擎的索 引工作中，重点是分析出页面内容的含义，然后根据分析的结果将页面整理分类。 同传统的数据源系统相比，在数据更新方面搜索引擎也存在较大的差异。传 统数据源的更新一般是局部的，要更新的数据可事先规划，是可预测的行为，而 搜索引擎的数据源更新问题就要考虑更多的问题，因为互联网上的数据更新量 大、更新速度快，对数据的实时性要求高，而且更新数量、时间无法准确预测， 再加上互联网的持续高速发展更加剧了这种不确定性，采用什么样的更新控制策 略保证数据的实时有效性和全面性就成了一个关键问题，在这方面有许多启发性 和智能的算法( 主要是利用统计规律) 。 在大型数据源中，由于数据量庞大，因而在数据传送过程中的缓冲策略选择 很重要，而对搜索引擎而言，由于它的数据量是一般数据源无法匹敌的，而且又 受到网络传输的速率、实时性等条件的制约，缓冲策略的正确与否会极大地影响 搜索引擎的服务质量。 2 2 3 用户查询系统 用户查询系统是搜索引擎直接同用户接触到的部分，它负责接受用户的查 询，经过分析处理后把查询要求向数据源提交，它把返回的结果显示给用户，由 用户进一步分析，选择需要浏览的内容。对每一条查询结果相对应的提供一个 u r l 地址，用户就可以通过这个u r l 地址定向访问所要的具体内容。下图卜5 是 用户查询系统的工作原理图【2 3 埘矧： 北京工业大学工学硕士学位论文 图2 - 5用户查询示意图 f i g u r e2 - 5t h es k e t c hm a po f u s e rq u e r y 由图中可以看到，用户查询系统中牵涉到多种技术，包括动态网页生成技术、 语义分析技术、数据检索技术等。通过分析用户的查询、访问行为可以学习、确 定和预测用户的浏览模式，向用户提供有效的浏览导航，帮助用户快速寻找到所 需要的信息。 2 3 搜索引擎的优势和缺陷 独立的搜索引擎，因为其内容涉及范围不一样，在不同领域、针对不同用户 起着不同的作用。由于网络语言不像传统检索语言那样严谨、规范，并且处在不 断的变化当中，综合性的独立搜索引擎，能分离出更多贴近用户需求的类别，以 满足用户查询的多样性。 专业独立搜索引擎则更具优势，因为它主要收集、索引某一学科的内容，在 该领域内涉及更细致、更广泛。同时，按照严格的学科划分，可克服综合网站之 间存在的信息重复问题，有效利用网络资源。由于它们的索引数据源相对轻巧， 因此运行速度很快，倍受用户青睐。 当然，其缺陷也很明显： 信息覆盖面不够广泛。使用搜索引擎的用户都希望“一个”搜索引擎就 能够索引全部的w w w 可公开访问页面，尽量避免为得到全面的检索结果 在不同的搜索引擎之间切换。但是，对独立搜索引擎而言，相对于其能 力，w e b 页面数量增长速度太快，以至于覆盖率方面一直都相对低下。 表卜1 是清华大学i t 可用性实验室2 0 0 5 年的中文搜索引擎网页覆盖率 结果数据【”】。可以看到，覆盖率最高的百度也只有3 2 5 2 ，最低的搜狗 甚至不到1 0 。可以说，这个结果和用户的期望相差甚远，即众多的页 面在单一搜索引擎中是难以找到的。 第2 章信息检索与搜索引擎 钿蚰k拽酉度畸l 擅麓问援狩 静态弼瑟t 条)2 31 5 1 1嬲- 三l l 裾弧3 动卷网鬣条)1 2 5 45 3 1l 26 5 1n墙3 全韶网页( 条) 3 2 5 72 l a 23 拿7 3渊 1 5 2 3i o 诌 垒都罔页覆_ ；斑率幅 2 氛6 2 1 7 5 l 托5 2 2 乱 1 2 秘8 执 图2 - 6中文搜索引擎网页覆盖率统计 f i g u r e2 - 6s t a t i s t i c so fc o v e r a g ep e r c e n ta b o u tc h i n e s es e a r c he n g i n e 检索效率不高。独立搜索引擎除了覆盖面有限以外，在信息检索