（计算机应用技术专业论文）基于lucene的web搜索引擎的研究.pdf

硕士学位论文 摘要 随着网络信息量正不断地以指数规模增长，人类已步入信息爆炸时 代。面对浩如烟海的网络信息，如何才能迅速、方便地获取有效信息， 日益成为人们关心的问题。搜索引擎的出现极大地缓解了这一矛盾。搜 索引擎是一种应用在w e b 上的软件系统，它以一定的策略在互联网中进 行搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供 检索服务，从而起到信息导航的目的。 在当前网络信息的大环境里，网络上出现了很多商业性的w e b 搜索引 擎，如g o o g le 、b a id u 、s o u g o 等，他们极大地方便了网络用户。但由于 他们的商业性质，其关键技术对于外界是保密的。为推进搜索引擎技术 的发展，a p a c h e 基金会推出了一个开源的全文搜索引擎工具包l u c e n e 。 l u c e n e 可以方便地嵌入到各种应用中，实现针对具体应用的全文检索功 能，近些年来在世界各地被广泛应用。本文在现有搜索引擎理论的基础 上，以l u c e n e 为基础，并结合x m l 数据存储的思想，从不同层次研究了以 l u c e n e 为核心的搜索引擎的构建。 本文的主要工作体现在以下三个方面： 1 分析了当前搜索引擎的工作机制和关键技术，特别深刻地剖析了 l u c e n e 的索引引擎机制和搜索引擎机制，并在此基础上设计了基于 l u c e n e 的w e b 搜索引擎架构。 2 对于编写要求不严谨的h t m l 实现的网页要真正做到高效准确的挖 掘数据非常困难。相对于h t m l ，x m l 可以更好地实现w e b 中的信息共享与 交换。本文提出了x m l 数据抽取模块的设计思想，采用x m l 文件存储准备 被索引的文件，可以有效地提高建立索引的速度和减小存储索引的空间， 并能有效地提高数据挖掘的准确性。 3 针对l u c e n e 原基础排序算法查询精确度较低并且只考虑关键词和 文档的相关度，忽略了网页本身的重要性的缺点，本文对l u c e n e 排序算 法进行了改进，改进后算法的最大特点是通过调整权重系数提高网页排 名的合理性和查询的精确度。 关键词：l u c e n e ；x m l 数据抽取模块；排序算法优化；搜索引擎 基于l u c e n e 的w e b 搜索引擎的研究 a b s t r a c t w i t ht h ea m o u n to fw e bi n f o r m a t i o ni si n c r e a s i n gi ne x p o n e n t i a lr a t e ， m a n k i n dh a se n t e r e dt h ee r ao fi n f o r m a t i o ne x p l o s i o n f a c e dw i t hab r o a d a r r a yo fn e t w o r ki n f o r m a t i o n ，t h ep e o p l eh a v ei n c r e a s i n g l yc o n c e r n sh o w t o q u i c k l ya n de a s i l yo b t a i nt h ev a l i di n f o r m a t i o n t h ee m e r g e n c eo fs e a r c h e n g i n eg r e a t l y a l l e v i a t e st h i sc o n t r a d i c t i o n s e a r c h e n g i n e i s aw e b a p p l i c a t i o ns o f t w a r es y s t e m w i t h ac e r t a i nd e g r e eo f s t r a t e g y i nt h e i n t e r n e t ，s e a r c he n g i n ec a nc o l l e c t ，f i n di n f o r m a t i o na n du n d e r s t a n d ，e x t r a c t ， o r g a n i z e ，d e a lw i t hi n f o r m a t i o n ，a n dp r o v i d er e t r i e v a ls e r v i c e ，s oi tp l a ya n i m p o r t a n tr o l eo fi n f o r m a t i o nn a v i g a t i o n i nt h i sn e t w o r ke n v i r o n m e n t ，t h e r ea r em a n yc o m m e r c i a lw e bs e a r c h e n g i n e i nt h en e t w o r k ，s u c ha sg o o g l e ，b a i d u ，s o u g oe t e ，w h i c ha r e c o n v e n i e n tf o rw e bu s e r s h o w e v e r ，d u et ot h en a t u r eo ft h e i rb u s i n e s s ，t h e k e yt e c h n o l o g yf o rt h eo u t s i d ew o r l di sk e p tc o n f i d e n t i a l t oa d v a n c i n gt h e d e v e l o p m e n tf o rs e a r c he n g i n et e c h n o l o g y ，a p a c h ef o u n d a t i o ni n t r o d u c e da f u l l t e x to p e ns o u r c es e a r c he n g i n et o o l k i tl u c e n e i nr e c e n ty e a r s ，l u c e n e i sw i d e l yu s e da r o u n dt h ew o r l d ，w h i c hc a ne a s i l ye m b e di nav a r i e t yo f a p p l i c a t i o n s a n da c h i e v et h ef u l lt e x ts e a r c hf u n c t i o nf o r s p e c i f i c a p p l i c a t i o n t h i sp a p e ri n t e g r a t e st h ee x i s t i n gt h e o r yo fs e a r c he n g i n e ，l u e e n e ， x m ld a t as t o r a g ei d e a sa n da td i f f e r e n tl e v e l s ，s t u d i e ss e a r c he n g i n eb a s e do n l u c e n e t h em a j o rw o r k so ft h i sp a p e rc a nb eg e n e r a l i z e dw i t ht h r e ea s p e c t s ： 1 t h ep a p e rd e m o n s t r a t e st h ec u r r e n ts e a r c he n g i n ew o r km e c h a n i s m a n ds o m ek e yt e c h n o l o g i e s ，p r o f o u n d l ya n a l y z e sl u c e n ei n d e xa n dr e t r i e v a l e n g i n e ，a n do nt h i sb a s i s ，p r o p o s e sw e bs e a r c he n g i n ef r a m e w o r kb a s e do n l u c e n e 2 r e q u i r e m e n t sf o rl o o s eh t m lp a g e st or e a l l ya c h i e v ea c c u r a t ea n d e f f i c i e n td a t am i n i n ga r ev e r yd i f f i c u l t c o m p a r e dt oh t m l ，x m lc a n b e t t e ra c h i e v et h ew e bi n f o r m a t i o ns h a r i n ga n de x c h a n g e t h ep a p e r p r o p o s e st h ed e s i g ni d e ao fx m l d a t ae x t r a c t i o nm o d u l e ，a n di tu s e sx m l f i l e st os t o r ed o c u m e n t st ob ei n d e x e d ，w h i c hi m p r o v e st h e s p e e do f i n d e x i n g a n dr e d u c e st h es t o r a g es p a c eo fi n d e x i n ga n di m p r o v e st h e a c c u r a c yo fd a t am i n i n g i i 硕士学位论文 3 a g a i n s tl u c e n es o r t i n ga l g o r i t h mo n l yc o n s i d e r i n gt h er e l e v a n c eo f k e y w o r d sa n dd o c u m e n t s ，i g n o r i n gt h ei m p o r t a n c eo ft h ep a g ei t s e l f ，t h i s p a p e ri m p r o v e sl u c e n es o r t i n ga l g o r i t h m ，w h i c hi m p r o v e st h er a t i o n a l i t yo f p a g er a n ka n dt h ep r e c i s i o no fq u e r yb ya d j u s t i n gt h ew e i g h tc o e f f i c i e n t k e yw o r d s ：l u c e n e ；x m ld a t a e x t r a c t i o nm o d u l e ；o p t i m i z a t i o no fs o r t i n g a l g o r i t h m ；s e a r c he n g i n e 基于l u c e n e 的w e b 搜索引擎的研究 插图索引 图2 1 搜索引擎的一般模型 6 图2 2 简单p a g e r a n k 值的计算1 1 图3 1l u c e n e 系统结构图1 7 图3 2l u c e n e 数据流图1 8 图3 3l u c e n e 索引机制架构图1 9 图3 4l u c e n e 索引文件结构图2 1 图3 5 基于内存d o c u m e n t 缓存有助于改善l u c e n e 索引性能2 1 图3 6l u c e n e 检索机制架构图2 3 图4 1 基于l u c e n e 的w e b 搜索引擎系统总体架构图2 5 图4 2 信息采集模块的体系结构图2 6 图4 3 信息处理模块的体系结构图2 7 图4 4l u c e n e 模块的体系结构图2 8 图4 5x m l 数据抽取模块流程图2 9 i v 硕士学位论文 附表索引 表3 1l u e e n e 各包功能表一1 7 表3 2l u c e n e 调整索引性能的参数2 2 表4 15 次对比实验的单个用户对系统评价的查准率3 5 表4 25 次对比实验的查准率3 6 v 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 李屯林一 日期洳年乡月7 e t 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据 库，并通过网络向社会公众提供信息服务。 作者签名： 导师签名： 春扯咕 1 俚永 日期如勿年多月夕日 日期舢l o 年占其7 e l 硕士学位论文 1 1 课题背景 第1 章绪论 近些年来，互联网上的网络信息量以指数的规模增长，人类已步入 信息爆炸时代，在这种环境下搜索引擎已经成为人们在海量信息中快速、 准确地定位到所需的信息的必要工具。搜索引擎技术是互联网发展的第 二次技术革命n 】。从通俗意义上讲，搜索引擎是指一种互联网应用软件 系统，该系统以一定的爬取策略在互联网上搜集信息，在对信息进行处 理后，为用户提供互联网信息查询服务。从用户的角度上看，搜索引擎 软件系统提供一个网页交互界面，用户可以通过网页交互界面提交一个 或多个关键词或者短语，该系统返回一个以某种排序策略进行排序后的 结果信息列表妇】【 。 根据2 0 0 9 年1 月，中国互联网络中心( c n n i c ) 发布的第2 3 次中国 互联网络发展状况统计报告，有6 8 0 的网民使用搜索引擎服务，2 0 0 8 年全年搜索引擎用户增长了510 0 万人，年增长率达到3 3 6 。中国互 联网络中心( c n n i c ) 发布的这份报告充分说明了搜索引擎技术拥有巨大 的科研价值和商业价值。在当前这种网络信息的大环境里，网络上出现 了很多商业性的w e b 搜索引擎，如g o 0 9 1e 、b a id u 、s o u g o 等，他们极大 地方便了网络用户。但由于他们的商业性质，其关键技术对于外界是保 密的。为推进搜索引擎技术的发展，a p a c h e 基金会推出了一个开源的全 文搜索引擎工具包l u c e n e 。自从l u c e n e 诞生之日起，它就风靡全球。如 何以l u c e n e 为基础开发搜索引擎已成为搜索引擎领域的一个热点问题。 1 2 搜索引擎的研究现状 1 2 1 国外研究现状 ( 1 ) a r c hie 搜索引擎 a r c h ie ( h r c h ie f a q ) 被认为是搜索引擎的鼻祖，它是第一个自动索引 w w w 上匿名f t p 文件的搜索引擎，由m cg i l1u n iv e r sity 的三个学生a 1a n e m t a g e 、p e t e rd e u ts c h 、bil lw h e e1a n 开发1 。早在互联网还没有出现 的时候，使用f t p ( f “et r a n s f e rp r o to c 0 1 ) 协议进行网络文件传输就 已经很普及了邙1 。a r c h ie 并不是一个真正的搜索引擎系统，可将它看做 一个可搜索的f t p 文件名的结果列表。当用户准确地输入自己想要的文件 基于l u c e n t 的w e b 搜索引擎的研究 名时，a r c h ie 会告诉用户一个下载自己想要的文件的f t p 地址列表。1 9 93 年10 月，m a r tijnk o ste r 创建了h t t p 版的a r c h ie a 1 i w e b 。 ( 2 ) r b s e ( r e p o s it o r y - b a s e ds o f t w a r ee n g in e e rin g ) 搜索引擎 19 9 3 年底，n a s a ( 美国国家航空和宇宙航行局) 开发了r b s e - ( r e p osit o r ) - b a seds o f t w a r ee n g in e e rin g ) 搜索引擎。r b s e 是第一个 全文索引搜索引擎，也是第一个将关键字匹配度应用到结果列表排序中 的搜索引擎 3 。 ( 3 ) y a h 0 01 目录搜索 19 9 4 年4 月，y a h o o ! 诞生。它由美籍华人j e r r y y a n g ( 杨致远) 和 d a yid fi10 共同创立。y a h o o ! 实际上只是一个可搜索的目录，并不是一 个真正意义上的搜索引擎，这是因为y a h o o ! 的数据都是由人工录入的， 但其搜索效率相当高。 ( 4 ) a 1t a v ista 搜索引擎 19 95 年l2 月，a lta v ista 问世，迅速风靡全球，成为搜索引擎领域的 第一座里程碑。a 1ta v is t a 创新了搜索引擎领域很多功能，改变了之前搜 索引擎的定义，拥有搜索引擎界多个第一，如：第一个实现自然语言检 索的搜索引擎，第一个支持高级搜索语法( 如a n d 、o r 、n o t 等) 的搜索 引擎，第一个支持用户自己向w e b 页索引库提交或删除u r l 的搜索引擎， 并能在2 4 小时内上线。a 1t a vis ta 最突出的特点是速度，并且在面向用户 的界面上也作了大量更新。 ( 5 ) i n f o s e e k 19 9 8 年4 月，in f os e e k 诞生，它是第一个实现以“超链接分析原理” 为基础的主流搜索引擎。 ( 6 ) g o o gle 搜索引擎 19 9 8 年底，g o o g le 创立，它将19 9 8 年9 月27 日作为自己的生日。l9 9 9 年2 月，g o o g le 完成了从a 1p h a 版到b e t a 版的蜕变。g o o g le 不拘泥原有的 搜索引擎技术，改革搜索引擎技术的多个方面，如p a g e r a n k 、用户界面、 地图搜索、网页等级、网页快照、更新频率、动态摘要、多语言支持、 多文档格式支持等。在搜索引擎技术上的革新使以搜索准确性高著称的 g o o g le 改变了之前搜索引擎的定义，成为继a 1t a v i s ta 2 _ 后搜索引擎领域 的又一座里程碑。 1 2 2 国内研究现状 ( 1 ) o p e n f in d 搜索引擎 19 9 8 年1 月，台湾中正大学吴升教授所领导的g a is 实验室创立了 2 硕士学位论文 o p e n f in d 。o p e n f in d 早期只做中文搜索，曾被认为是最好的中文搜索引 擎，但在2 0 0 0 后被b a id u 取代，随后进军英文检索领域。 ( 2 ) 天网搜索引擎 北大天网具有强大的f t p 检索功能，目前存储w e b 约6 0 0 0 万，是国家 “九五 重点科技攻关项目“中文编码和分布式中英文信息发现”的研 究成果，由北大计算机网络与分布式系统研究室开发。19 9 7 年10 月2 9 日 天网搜索引擎正式为c e r n e t 提供服务。 ( 3 ) 百度( b a id u ) 搜索引擎 2 0 01 年1 月，百度公司在北京中关村成立。2 0 01 年8 月，百度公司发 布b a id u 搜索引擎的b e t a 版。2 0 01 年10 月2 2 日，百度公司正式发布b a id u 搜索引擎。b a id u 只提供中文搜索，拥有目前国内最大的中文w e b 数据库， 据统计目前存储中文网页超过2 亿。其它特色服务包括：m p 3 搜索、错别 字纠正提示、网页预览预览全部网页、相关搜索词、f l a s h 搜索、网页 快照、新闻搜索等。 1 3 本文的主要研究内容 首先，本文研究了当前搜索引擎系统和l u c e n e 的基本理论，以此为 基础设计了基于l u c e n e 的w e b 搜索引擎的构架，并对系统的每个功能模块 的作用和体系结构进行了详细的说明；其次，深刻地剖析了x m l 数据抽取 模块和x m l 文档解析是如何实现的，为l u c en e 的良好运行奠定了坚实的基 础；最后，本文详细阐述了l u c e n e 排序算法的思想和原理，并对排序算 法进行了改进。 1 4 论文组织 第1 章介绍了搜索引擎技术的研究背景、国内外研究现状。 第2 2 阐述了搜索引擎系统的工作机制，详细介绍了搜索引擎领域的 基础理论：文本分词技术、网页排序技术、系统的各种测试指标。 第3 2 首先对l u ce n e 进行了扼要的简介；阐述了l u c e n e 的系统结构， 特别对l u ce n e 的七个包和四个数据流进行了详细的分析；然后，引入了 l u ce n e 的索引机制，从工作原理、文件结构、调整索引性能三个方面进 行了详细的阐述；最后详细地分析了l u ce n e 的检索机制。 第4 2 介绍了基于l u c e n e 的w e b 搜索引擎的设计思想，对该系统的整 体架构和每个功能模块进行了说明和分析。对该系统所涉及的关键技术 ( x m l 数据抽取、x m l 文档解析、l u ce n e 排序算法及算法改进) 的理论基 3 基于l u c e n e 的w e b 搜索引擎的研究 础和工作原理进行了详细阐明，并以l u ce n e 和自行设计的爬虫构建实验 平台，对改进算法进行了验证，对实验数据进行了科学的分析。 最后对本文的当前工作进行了总结，对未来的研究工作进行了展望。 4 硕士学位论文 第2 章搜索引擎技术研究 2 1 搜索引擎的工作机制 一个搜索引擎系统由搜索器( s p id e r ) 、分析器( a n a ly ze r ) 、索引器 ( i n d e x e r ) 、检索器( s e a r c h e r ) 和用户接口( u i ) 五个部分组成。 ( 1 ) s p i d e r ( 也称为r o b o t 或c r a w l e r ) 在系统中维护一个包含一些起始u r l 的超链接队列，从该超链接队列 的起始u r l 出发，采用广度( 或深度) 优先的策略对w e b 进行遍历后下载文 档，并从中解析出新的u r l 后抽取出新的u r l 力h 入到上述队列中。上述过 程周而复始直到队列为空后停止抓取。 ( 2 ) a n a l y z e r 对搜索器下载的文档进行分析以用于索引。文档分析技术一般包括： 分词、过滤和转换等，其中最主要的是分词技术。在分词时，大部分系 统从全文中抽取词条。分词后通常进行去除常用词条、去除标点符号、 单复数转换、同义词转换等工作。 ( 3 ) i n d e x e r 将文档以倒排索引的形式存储在索引数据库中。索引的质量决定整 个搜索引擎系统的成败与否。一个好的搜索引擎的索引系统要求索引操 作易于实现和维护，索引存储空间小，搜索速度快。 ( 4 ) s e a r c h e r 从索引中找出用户查询与索引数据库中文档的相关度大于系统所设 定的阀值的所有文档，并返回给用户一个按照相关度递减的顺序排列的 结果文档列表。 ( 5 ) u i 为用户提供可视化的查询输人和结果输出界面。在查询输人界面中， 用户输入待检索条件。在输出界面中，搜索引擎将检索结果展现为一个 按照相关度递减的顺序排好序的结果文档列表，其中包含了文档的超链 接、摘要、标题等信息。 整个系统示意图如下： 5 基于l u c e n e 的w e b 搜索引擎的研究 二副骝 2 2 分词技术 图2 1 搜索引擎的一般模型 用户 对于英文来说，分词技术并不显得十分关键，因为英文单词之间有 空格作为天然的分隔符。但是对于汉语来讲就有相当大的困难，如何分 词有如下几种做法1o 1 1 1 1 。 ( 1 ) 词典切分算法 即建立一个丰富的词库，按照词库里存在的词对关键字进行切分。 词典切分算法的优点是关键字非常清晰，当然缺点也很明显，需要雇请 专门人员进行词库设计与维护。不同的语种需要不同词库，成本巨大。 ( 2 ) n 元切分算法 其可分为单字切分、2 元切分、3 元切分、多元切分。一般采用2 元切 分，比如“浙江杭州西湖 ，切分之后就是 浙江、江杭、杭州、州西、 西湖”。为什么采用2 元切分? 如果采用单个字符，那么“上海 被分成 “上、海”，结果很可能将“海上 一起查了出来。可见，此方法虽然能 够保证有很高的查全率，但由于中文中存在歧义的地方很多，基于单字的 检索可能会返回很多跟用户输入无关的结果。如果采用3 元甚至多元，那 么精细度又不如2 元。可见2 元是最小的查询单位。2 元切分相对于词典切 分的最大优点是实现简单，而且免去了词典维护的工作，但其冗余量大， 搜索效率低。 2 3 网页排序技术 影响一个搜索引擎系统性能的因素有很多，但对用户而言，感受最 深的当属查询列表的好坏，接下来将详细介绍几种主流网页排序技术。 2 3 1 布尔模型( b o o ie anm o d ei ) 在搜索引擎早期，由于网络和电脑硬件的限制，搜索引擎并不存储 抓取下来的网页的所有内容而只是存储一部分主要的内容，存储的信息 量很少，这时采用布尔模型成为最佳的选择。 6 硕士学位论文 布尔模型的定义：设t 。为某一关键词，d ，为某一文档的向量表示， w ( t 。，d ，) 表示t 。与d ，的相关性，令用户查询q = t 。，t ：，t 。 ，q 的析取范 式为q ，则q 与d j 的相关性s i m ( q ，d ，) 为 s i m ( q ，d 小f ：磐小叫w ( “咖”) ) ( 2 1 ) l 当si i l l ( q ，d j ) = 1 时表示d j 与q 相关，当sim ( q ，d j ) = 0 时表示不相关。 从公式( 2 1 ) 中可以看到：布尔模型是以集合论和布尔代数为基础 来构建的。它最大的特点是理论简单便于理解、使用方便、运行速度快。 当然，任何事物都具有两面性。布尔模型最大的缺点是只有相关性的概 念而没有相关度的概念。换句话说，布尔模型不支持按相关度匹配的查 询服务也不能将结果文档列表进行排序后显示，当然，在结果文档列表 中也不可能会出现与查询内容意思相近的文档。在搜索引擎系统中使用 布尔模型经常会出现下列情况：第一，当用查询关键字很普通或流行时， 返回的结果很多；当查询关键字很专业或生僻时，返回结果很少，或者 返回结果为零；第二，为了较高的查询精度，布尔模型要求用户准确地 输入查询语句，这对于用户来说要求太高，并且在很多情况下用户根本 无法用布尔表达式表述很复杂的查询请求n 引；第三，某些网站经营商为 了提高自己网站的点击率，利用当时的搜索引擎系统一般只收录w e b 的前 一百个词语或 标签中的内容这个技术特点，人为地在搜索引擎收 录的内容中添加大量与自己网站内容无关但流行度很高的词语来欺骗搜 索引擎，而布尔模型对这种欺骗手段没有任何对抗能力n ( 注：此时布尔 模型对目录式搜索引擎并未失效，因为目录型搜索引擎中用于与用户查 询匹配的评价信息需经专业技术人员查看网页内容后进行人工或半自动 编写n 5 3 ) 。随着网络技术和计算机硬件水平的提高，搜索引擎开始索引全 文，布尔模型告别了属于它的时代，搜索引擎进入了一个全新的时代一 向量空间模型。 2 3 2 向量空间模型( v s mv e c tors p a c em o d ei ) 布尔模型的缺点是由于关键字的权值太简单，造成相关算法结果也 过于简单。要克服布尔模型的二元权值不能度量相关度的缺陷，可使关 键词t 。在文档d ，中的权值用一个介于o 和1 之间的实数来表示。 如何计算关键词在文档中的权值? 主要使用传统的词频反向文档词 频方法。何谓词频反向文档词频方法呢? 即定义w b ( d j ，t 1 ) 为t 。在d j 中出现 频率tf 。( d ，) 的函数n 7 基于l u c e n e 的w e b 搜索引擎的研究 肋( d ，) 一妒( 坑( d 川 ( 2 2 ) 公式( 2 2 ) 中的函数妒可用t f , id f 来表示，则 w b ，) 一t f ，) 奉i d f ( q ) ( 2 3 ) t f ( t e r mf r e q ue n c y ) 是词频函数，它表示关键词在文档中出现的 次数，某个关键词的t f 值越大，证明该关键词对文档越重要。 id f ( in v e r sed o c u m e n tf r e q u e n c y ) 是反向文档频率函数，它用来 衡量关键词对文档的重要程度。在信息论中，一个关键词所在的文档数 越多，证明该关键词的主题性就越弱，就越不具有区别性，它的id f 值就 越小；相反，一个关键词所在的文档数越少，证明该关键词的主题性就 越强，就越具有区别性，它的i d f 值就越大n 小引。id f 的表达式为 i d f l o g n n ( 2 4 ) 其中n 表示数据库中文档集合的总数，n 表示出现关键词的文档数。 词频反向文档词频方法来源于本世纪4 0 年代美国学者g k zip f 提出 的齐普夫定律。齐普夫定律可以表述为：如果把一篇较长文章中每个词出 现的频次统计起来，按照高频词在前、低频词在后的递减顺序排列，并 用自然数为这些词编上等级序号，即频次最高的词等级为1 ，频次次之的 等级为2 ，频次最小的词等级为d 。若用f 表示频次，r 表示序号， 则有1 厂事r c ( c 为常数) ( 2 5 ) 很明显，除去那些常出现在文档中但没有实际含义的词，例如得、 地、的等，如果t 。，tb 是文档d ，中的两个词，而且t 。的频次高于t - ，则有 w b ( d ，t 。) w b ( dj ，tb ) 。然后，再应用聚类技术实现部分匹配和扩展查询。 总的来说，v s m 方法归纳起来可分为以下三个步骤： ( 1 ) 将给定用户查询q 、网页p 表示为关键词的集合，记为 p = tl ，t2 ，t 。) ，q = q i ，q 2 ，”，q ) 其中t j ( j = l ton ) 、q k ( k = 1t om ) 均表示一个词项。 ( 2 ) 采用词频反向文档频率法计算词项的权值 嬲0 ， ) 一t f ( r ，) 木i o f ( t , ) ( 2 6 ) w b 0 ，呸) 一t f p ，呸) i d f ) ( 2 7 ) p 、缃应的权值向量为 p ， w b ( p ， ) ，w b ( p ，乞) ) q = t w b ( p ，级) ”，w b ( p ，) ) ( 3 ) 采用余弦法计算网页p 与查询q 的相似值 8 ( 2 8 ) ( 2 9 ) 硕士学位论文 s i m ( q ，p ) 一 ( 2 1o ) v s m 模型有四个主要优点。首先，在v s m 模型中关键词权值可以在0 到 1 之间变化，这使得采用了v s m 模型的搜索引擎具有了按相关度排序搜索 结果列表的能力，再者，采用了v s m 模型的搜索引擎的部分匹配策略使那 些与查询意义相关但不包含查询关键词的网页可以出现在结果列表中； 还有，文档与查询的相似度问题是一个很难用计算机模拟的问题，而v s m 模型将这个问题转换成为计算两个向量的余弦值问题；最后，v s m 模型在 公式上很难计算，但在计算机中很容易实现。 同时v s m 模型也有很多缺点。首先，v s m 模型过于将相关度测算量化， 强调计算，更依赖于用户对结果列表的直觉与感知，余弦函数不一定是 最好的测算方法；其次，在v s m 模型中认为词与词之间的关系是相互独立 的，但实际上，词与词之间很难相互独立，他们之间存在很多关系如相 似关系、等级关系、相关关系等，其中以相关关系最为复杂；再次，一 词多义现象的存在严重破坏相关性的测算。还有，基于v s m 模型的相关性 测算的准确度取决于向量维数的取值，维数越高，相关性测算的准确度 就越高，但相关性测算的计算量却越大。最后，含有更多词的大文档天 生就比小文档容易被搜索引擎命中。 虽然v s m 模型具有上面很多缺点，但是和布尔模型相比，v s m 模型的 缺点瑕不掩瑜。在当代搜索引擎的排序算法的设计中，v s m 模型仍然有用 武之地。 在搜索引擎领域，网站经营者为了使自己网站在搜索引擎的搜索结 果列表中排名靠前，往往利用v s m 的弱点采取各种欺骗手段：例如在网页 源码注释中加入大量的关键词、在图片的 标签中加入很多关键词、 在网页正文中加入大量与网页背景色相同的关键词、还有臭名昭著的 c l o a k in g 技术，其中c 1o a k in g 技术是v s m 模型无法战胜的。欺骗技术的猖 獗迫使搜索引擎的相关性测算方法进入了超链分析阶段。 2 3 3 超链分析原理 超链接分析原理来源于情报学经典方法中的引文分析法。何为引文 分析法呢? 它是一种独特的情报计量学方法。一般来说，引文分析法认 为某期刊或论文被引用的次数越多，证明该期刊或论文的质量就越高。 那么，把这个思想移植到网页上，如果指向这个网页的链接越多，就认 9 基于l u c e n e 的w e b 搜索引擎的研究 为被指向的该网页越重要。需要指出的是：超链接分析原理在计算一个 网页的重要性时，不是单纯的将被指向该网页的链接数加一，而是将指 向该网页的链接数作为权，同时将指向该网页的网页重要性也考虑进来， 将计算扩展后的网页评分作为网页重要性的依据他。具有代表性的基于 链接分析原理的算法有如下三种： 1 h i t s 算法 h i t s ( h y p e r lin k - in d e x edt o p ics e a r c h ) 算法由康奈尔大学的i o n k 1ein be r g 博士于19 9 8 年首先提出的一种网页排序算法，后来，ib m 研究 院在c 1e v e r 系统中采用该算法。h it s 的中文全称是超文本引入主题搜索， 它所依赖的是对w e b 环境下的超链接结构的分析心。h it s 算法认为在每篇 网页中均存在权威性( a u th o r ity ) 和目录( h u b ) 这两种类型的权值，相应 地在c 1e v e r 系统中存在着两种类型的网页： ( 1 ) 权威( a u th o rity ) 网页：与给定查询主题的上下文最为相关的网 页。 ( 2 ) 目录( h u b ) 网页：拥有很多指向权威性( a u th o rit y ) 网页的超链 接。 对于每篇网页的权威性( a u th o rit y ) 权值和目录( h u b ) 权值，c le v e r 系统采用目录网页和权威网页相互评价的办法进行在线迭代计算的方 法。例如对于一个网页p ，用x p 来表示网页p 的权威性( a u th o r ity ) 权值， 用y p 来表示它的目录( h u b ) 权值，则计算网页p 的权威性( a u th o r ity ) 权 值和目录( h u b ) 权值的公式如下： z p 一罗匕 ( 2 1 1 ) 而 = x ， ( 2 1 2 ) 口p 其中q p 表示网页q 有链接指向网页p 。 基于权威值迭代计算的h i t s 算法常常会发生“主题漂移现象 乜2 2 3 “1 。所谓h i t s 算法产生的“主题漂移一现象是指权威网页向一组链 接稠密但与用户查询无关的网页集合集中的现象，更确切地讲，当一组 链接稠密但与用户查询无关的网页与根集合中的某w e b 相链接时，这组链 接稠密网页的权威性( a u t h o r it y ) 权值会快速增加，从而造成查询结果向 该组链接稠密的网页集中的现象。 h i t s 算法需要在线地迭代计算每一篇网页的权威性( a u th o r it y ) 权 值和目录( h u b ) 权值，这使得查询的响应时间非常大，远远超过用户所能 忍受的时间上线( 商用搜索引擎系统一般认为用户最多能忍受2 秒) 。 1 0 硕士学位论文 2 p a g e r a n k 算法 19 9 8 年，l a w r e n c ep a g e 和s e r g e yb rin 以描述网络用户访问网页的 一般行为的随机冲浪模型为基础提出了p a g e r a n k 算法。随机冲浪模型假 设如下2 5 1 2 6 1 2 ： ( 1 ) 用户任意地打开一个网页作为其上网的起点。 ( 2 ) 用户浏览完这个网页后，从该网页中随机地点击一个超链接进入 另一个网页进行浏览。 ( 3 ) 用户沿着超链接浏览了一些网页后，对这个主题感到厌倦，重新 任意地打开一个网页进行浏览，并重复( 1 ) 和( 2 ) 。 p a g e r a n k 算法依据随机冲浪模型的思想和引文分析法的原理，其基本 思想是：如果一个页面可能被许多其他页面访问，则认为这个页面很可 能是重要页面；如果一个页面即使没有可能被许多其他页面访问，但被 一个权威性的页面访问，则认为这个页面很可能是重要页面；一个页面 的重要性被平均分配给它所指向的每个网页的页面。将一个网页“可能 被其他网页访问的次数”以及“访问该网页的其他网页的权威性”作为 衡量一个网页重要性的标准，就是p a g e r a n k 值。 p a g e r a n k 技术基于整个w e b 的链接结构来计算各网页的重要性，它认 为用户能够通过网页之间的超链接能访问到整个网络，也就是说它认为 用户可通过网页间的超链接最终到达所需的特定网页心盯心 。更确切地说 整个w e b 的超链接构成一个有向图，如图2 2 。 图2 2 简单p a g e r a n k 值的计算 网页p a g e r a n k 值计算公式如下： p r s c o r p 似) 一( 1 一d ) n + d 宰咫( z ) c ( z ) ( 2 1 3 ) 其中，p r s c o r e ( a ) 表示网页a 的p a g e r a n k 值；p r ( t 。) 表示a 的源网页t 。 1 1 基于l u c e n e 的w e b 搜索引翠的珂f 究 的p a g e r a n k 值；c ( t 。) 代表网页t 。的出度；n 表示搜索引擎系统中网页库的 网页总数；d 代表阻尼系数，取值范围为区间 0 ，1 ，g o 0 9 1e 的经验值为 0 85 。当访问一个特定的网页时有且仅有两种情况会发生，一种情况是 用户随机打开一个网页，刚刚好正是自己想要访问的网页；另一种情况 是任意打开一个网页不是所需要的网页，但经过连续点击已打开网页中 的超链接后访问到所需要的特定网页。公式( 2 13 ) 的前半部分( 1 一d ) n 是 第一种情况的概率，而后半部分d 宰p r ( 霉) c ( 互) 是第二种情况的概率。 丁 公式中的衰减因子d 表示用户持续点击已打开网页中的超链接的概率， ( 1 - d ) 表示网页本身所具有的网页级别。通过上面详细的分析可以知道， w w w 上所有网页的p a g e r a n k 值形成一个概率分布。因此，每个网页的 p a g e r a n k 值的初始值一般设为1 n ，然后按上式进行递归运算，显然，公 式( 2 13 ) 的计算过程是一个递归收敛的过程0 1 。 由于p a n g r a n k 算法通过指向某网页的超链接的数量来计算该网页的 重要性，使p a g e r a n k 算法具有了一些不太客观的排序因素： ( 1 ) 新站点不如旧站点。 ( 2 ) 小站点不如大站点。 ( 3 ) 专业站点不如通俗站点。 ( 4 ) 用户通过搜索找到的仅仅是当前最热门的网页，却没有找到自己 最需要的网页。p a g e r a n k 算法将用户检索信息的主动过程，转变为接受 安排特定信息的被动过程。 3 h i1 1 t o p 算法 h i l1t o p 算法是g o 0 9 1e 的工程师k ris h n ab h a r a t 于2 0 0 0 年提出的一个 基于超链分析原理的新算法，并在2 0 0 1 年申请了该算法的专利权，g o o g le 成为受让方。 h il1 t o p 算法和p a g e r a n k 算法在指导思想上基本是一致的，但并不完 全相同。p a g er a n k 算法通过计算指向某一网页的超链接的数量和质量来 确定该网页的重要性，而h i 11 t o p 算法通过计算指向某一网页且必须和该 网页具有相同主题的相关网页的超链接的数量和质量来确定该网页的重 要性，也就是说