（计算机应用技术专业论文）web超链分析及其在搜索引擎中的应用研究.pdf

摘要 随着i n t e m e t 的高速发展和快速普及，w e b 上可以获取的信息也在急剧增加。由于 无法浏览全部的w e b 文档，所以人们往往求助于搜索引擎来杏找所需的信息。w e b 超 链分析技术町以提高搜索引擎的查准率，因此成为网络应用和信息检索方向的研究热 点。 介绍了搜索引擎的分类、发展历程、原理和评价指标，概括了超链分析技术在搜索 引擎中的重要作用。阐述了目前最著名的超链分析算法p a g e r a n k 和h i t s ，分析了它们 存在的问题，发现主题漂移是影响性能的主要因素。与h i t s 相比，p a g e r a n k 在稳定性 和适用性上更胜一筹，更适合于大规模的搜索引擎。因此p a g e r a n k 算法是本文的重点 研究对象。对p a g e r a n k 算法进行了深入的探讨，在分析了国内外主要的改进算法的基 础上，对p a g e r a n k 缺点和改进方法进行总结归纳，从不同的角度提出了两种改进方法。 从超链的创建动机和实际作用进行分析，发现超链的实际作用差别比较大。同时受 到网页分类的启发，引入了超链分类概念。根据不同的类别分配不i 司加权，提出了基于 超链分类的h c p a g e r a n k 改进算法。为了验证算法，在n u t c h 上开发了基于h c p a g e r a n k 的链接分析工具，实验证明，h c p a g e r a n k 的查准率高于传统的p a g e r a n k 算法。 在对p a g e r a n k 计算过程研究的基础e ，发现p a g e r a n k 值不具备语义性。根据h i t s 在线聚类原理，在查询时根据奄询词的语义进行p a g e r a n k 调整，提出了基于超链内容 p a g e r a n k 调整算法。为了验证算法，在n u t c h 上开发了基于超链内容p a g e r a n k 调整算 法的聚类插件。实验证明，基于超链内容的p a g e r a n k 调整算法可以提高搜索引擎的查 准率。 关键词：搜索引擎，超链分析，p a g e r a n k ，超链分类，超链内容 r e s e a r c ho nw e bh y p e r l i n ka n a l y s i s a n di t sa p p l i c a t i o ni ns e a r c he n g i n e l vk e q i a n g ( c o m p u t e r a p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f l ic u n h e a b s t r a c t w i t ht h eg r e a t l yr a p i dg r o w t ha n df l e e tp o p u l a r i z a t i o no fi n t e m e t ，t h ei n f o r m a t i o nw e c o u l dg e tf r o mt h ew e bi sa l s oe x p l o s i v e l ye x p a n d i n g s i n c ep e o p l ec a nn o tb r o w s et h ee n t i r e w e b ，t h e yr e f e rt h e m s e l v e st ow e bs e a r c he n g i n et of i n dw h a tt h e yn e e d a sw e bh y p e r l i n k a n a l y s i st e c h n o l o g yc o u l de n h a n c et h ep r e c i s i o no ft h es e a r c he n g i n e ，i ts o o nb e c a m eah o t t o p i co f t h er e s e a r c h i n gf i e l do fn e ta p p l i c a t i o na n di n f o r m a t i o nr e t r i e v a l f i r s to fa l lw ei n t r o d u c et h ec l a s s i f i c a t i o no ft h es e a r c he n g i n e ，i t sh i s t o r yo fd e v e l o p m e n t ， w o r k i n gt h e o r ya n de v a l u a t i o no ft h ep e r f o r m a n c e t h e nw es u m m a r i z et h ei m p o r t a n t f u n c t i o no ft h eh y p e r l i n ka n a l y s i si nt h eh i s t o r yo fs e a r c he n g i n e a f t e re x p o u n d i n gt h em o s t f a m o u sh y p e r l i n ka n a l y s i s a l g o r i t h mp a g e r a n ka n dh i t s ，w ed i s c u s st h ep r i n c i p l ea n d p r o b l e m so ft h e m ，f i n d i n gt h a tt o p i cd r i f tp h e n o m e n o ni st h em o s ts e r i o u sp r o b l e m c o m p a r e d w i t hh i t s ，p a g e r a n ki sm o r es t a b l ea n da p p l i c a b l ef o rl a r g es c a l es e a r c he n g i n e w et r yt o i m p r o v ep a g e r a n k a f t e rs t u d y i n ga n ds u mu pa l lt h ei m p r o v i n gm e t h o d so ft h ed o m e s t i ca n d o v e r s e a s ，w ep r o p o s et w on e wm e t h o d st oi m p r o v ep a g e r a n kf r o md i f f e r e n ta s p e c t a n a l y z i n gt h ef u n c t i o n sa n dc r e a t i n gm o t i v a t i o n so fh y p e r l i n k sw ef i n dt h a th y p e r l i n k s a r et o t a l l yd i f f e r e n t e n l i g h t e n e db yt h ei d e ao ft e x tc l a s s i f i c a t i o n ，w eb r i n gi nt h ec o n c e p to f h y p e r l i n kc l a s s i f i c a t i o n b a s e do nt h ep r i n c i p l et h a td i f f e r e n tc l a s si sg i v e nd i f f e r e n tw e i g h t ， w ep r o p o s ean e ww a yt oi m p r o v ep a g e r a n kb a s e do nt h eh y p e r l i n kc l a s s i f i c a t i o n t o v a l i d a t et h eh c - p a g e r a n k ，w ew r i t eap r o g r a mo nt h en u t c ha n dd e v e l o pan e wl i n ka n a l y s i s t 0 0 1 t h ee x p e r i m e n tr e s u l ts h o w st h a tt h ep r e c i s i o no fh c p a g e r a n ki s h i g h e rt h a nt h e t r a d i t i o n a lo n e s t u d y i n gt h ec o m p u t i n gp r o c e s so fp a g e r a n k ，w ef i n dt h ep a g e r a n kv a l u eh a sn o s e m a n t i cm e a n i n g a c c o r d i n gt ot h eh i t so n l i n ec l u s t e r i n gw a y , w em o d i f yt h ev a l u eo f p a g e r a n ka c c o r d i n gw i t hh y p e r l i n ka n c h o rt e x t t h e nw ep r o p o s eo n l i n ec l u s t e r i n gw a yt o i m p r o v ep a g e r a n k a tl a s tw ed e v e l o po n l i n ec l u s t e r i n gp l u g i ns o f t w a r et oo nn u t c h t h e e x p e r i m e n tr e s u l ts h o w st h a tt h ep r e c i s i o no fo n l i n ec l u s t e r i n gw a yi sh i g h e rt h a nt h e t r a d i t i o n a lo n e k e yw o r d s ：s e a r c he n g i n e ，h y p e r l i n ka n a l y s i s ，p a g e r a n k ，h y p e r l i n kc l a s s i f i c a t i o n ，h y p e r l i n kc o n t e n t 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 火学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：吕茧墨量门期：2 0 0 9 年了月z 舌日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部f - i ( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：墨查堡 指导教师签名：三奎丛 日期：2 0 0 c 年5 月巧日 f 1 期：? pf i - f 月“日 中1 日钉汕大学( f # 东) 硕上学位论史 1 1 课题的背景与意义 第一章前言 随着互联网的高速发展和快速普及，从w e b 上可以获取的信息也在急剧增加。截 1 至2 0 0 7 年6 月，中困网站的数量已经达到了1 3 1 万个，半年内增加4 7 万个，比2 0 0 6 年同期多增加5 2 万个，年增长率达到6 6 4 i 。1 。专业调研机构n e t c r a f t2 0 0 7 年1 1 月份 数据显示，全球的网站数量达到j - 1 4 4 0 0 万个【2 j 。随着站点的增加，网页的数黾也达到 了天文数字级别。2 0 0 7 年初，中文搜索引擎搜狗称其索引的中文页面达到了l0 0 亿个1 3 1 。 为处理爆炸式增长的w e b 页面，全球搜索巨头g o o g l e 已经研究出了1 0 0 0 亿级别的页面 索引技术。w e b 信息变的如此浩瀚，越来越多的人求助于搜索引擎来查询所需要的信息。 w e b 上的文档和传统的“数字图书馆”收集整理的文档相比，具有以下几个新的特 点：数据呈现分布式且不稳定；数据异构存在大量冗余；数据质量良莠不齐；数据呈现出 动态性并且在不断的增加。传统信息检索技术在w e b 文档中的应用效果很不理想4 l 。然 而，w e b 文档包含了传统文档没有的信息，即w e b 的超链结构( h y p e r l i n ks t r u c t u r e 也称 为链接结构，超链分析也称为链接分析) 。w e b 的超链结构起着导航和推荐的作用，如果 网页a 存在一条超链指向网页b ，那页a 的作者可能认为网页b 包含了有价值的信息【 。 许多国内外学者已经注意到了这点，通过对这些超链结构进行研究，他们取得了一系列 的研究成果。s e r g e yb r i n 币e i l a w r e n c ep a g e 提出了p a g e r a n k 算法【5 】k l e i n b e r g 提出 h i t s 算法1 6 1 等等。这些算法在实际中得到了应用并且取得了良好的效果。但是p a g e r a n k 币1 1 h i t s 也存在一些缺陷，在很多方面仍然不能令人满意【7 ，引。 本课题旨在对w e b 超链分析技术进行研究，试图克服目前超链分析算法中普遍存在 的主题漂移等缺点，并将改进后的算法应用到搜索引擎中，从而提高搜索引擎的查全率 和查准率，使人们能更好的从w e b 中查询所需的信息。 1 2 国内外研究现状 搜索引擎足随着w e b 的迅猛发展而发展起来的互联网应用技术，目前已经成为仅 次于e m a i l 的第二大互联刚应用。从技术发展角度来讲搜索引擎经历以下几个时期： ( 1 ) 第一代搜索引擎出现于上个世纪9 0 年代初。第一代搜索引擎采用了传统的信息 第一幸前言 检索技术，检索速度比较慢，准确率不高。但是它们勾勒出了现代搜索引擎的轮廓，奠 定了搜索引擎的基础。主要代表有：w e b c r a w l e r 、a l t a v i s t a 、l y c o s 、i n f o s e e k 等。 ( 2 ) 第二代搜索引擎的标志就是重视超链分析技术在w e b 榆索中的作用。典型的代 表是g o o g l e 、百度。g o o g l e 提供一系列革命性的新技术，最主要的是先进的p a g e r a n k 、排序技术，还包括完善的文本对应技术、“网页快照”功能等。百度的创办人李彦宏在 美国拥有超链分析的专利，百度在中文搜索方面拥有着最高的市场占有率。 ( 3 ) 第三代搜索引擎是未来的搜索引擎，目前普遍认为将是智能搜索引擎和垂直搜索 引擎( 也称为专业搜索引擎) 。智能搜索引擎就是知道用户要找什么样的信息，懂得用户 要问的问题，并立即给出用户想要的答案。目前虽然有些搜索引擎宣称是智能搜索，但 真正的智能搜索还远远没有达到。垂直搜索是针对某一个行业的专业搜索引擎，是搜索 引擎的细分和延伸，是对网页库中的某类专门的信息进行一次整合，定向分字段抽取出 需要的数据进行处理后再以某种形式返回给用户1 9 l 。基于特定领域的垂直搜索建树颇多， 如g o o g l e 的学术搜索，百度的学术搜索。它的应用效果良好，深受用户好评和推崇【1 0 1 。 总体上来说，目前大规模的w e b 检索技术还处在第二代搜索引擎的水平上。超链分 析技术是搜索引擎提高准确率的关键技术，超链分析技术从提出到今天也不足1 0 年时 间，也足f j 前研究的热点。下面将对超链分析技术的研究现状进行综述。 超链分析技术起源于1 9 9 8 的p a g e r a n k 算法和h i t s 算法，这两种算法应用于搜索 引擎的排序，大幅度提高了搜索引擎的查全率和杏准率，使搜索引擎成为人们在网上冲 浪的得力1 二具。目前超链分析算法主要的有以下几种： ( 1 ) p a g e r a n k 算法及其改进算法 p a g e r a n k 是一种和查询词无关的算法，它可以在用户查询之前进行离线计算，尽 管运算量比较大，但是在用户查询之前就已经计算完毕，不占用查询时的计算时间，所 以又称之为事前分析算法【。p a g e r a n k 算法广泛应用于搜索引擎的排序算法中，著名 的g o o g l e 搜索引擎就采用了此算法。 p a g e r a n k 算法也存在一些不足和缺陷，如：主题漂移、旧页面p a g e r a n k 值偏高等。 许多学者对其进行研究并提出了改进。2 0 0 2 年7 月斯坦福大学计算机科学系的t a h e r h a v e l i w a l a 提出了一种主题敏感( t o p i c s e n s i t i v e ) i 拘p a g e r a n k 算法来改进主题漂移问题， 该算法在个性化方面效果也很好1 2 1 ；2 0 0 5 年北京理工大学的陈伟柱、陈英等人提出了类 2 中图f 订山人学( f 仁东) 硕上学位论义 似的c a t e g o r y r a n k 【l3 1 ，李绍华等后来也提出过类似的算法1 4 1 ：2 0 0 2 年华盛顿大学计算机 科学系的m a t t h e wr i c h a r d s o n 和p e d r od o m i n g g o s 结合超链分析和文本内容的提出了 q d p a g e r a n k 算法【1 5 】；2 0 0 4 年上海交通人学的张玲博士提出了一个加速评估的p a g e r a n k 算法，该算法使得网络上有价值的内容以更快的速度传播f m l ；2 0 0 4 年加拿大n e w b r u n s w i c k 大学的w e n p ux i n g 和a l ig h o r b a n i 提出了一种结构权重p a g e r a n k 算法，这种 算法根据超链接的层次结构计算权重来改进p a g e r a n k 【1 7 】。2 0 0 5 年微软北京研究院的 l i u t i e y a n ，m a w e i y i n g 利用站点的层次结构和p a g e r a n k 来确定w e b 的重要性【1 引。2 0 0 6 年浙江工业大学的黄德才等学者还根据页面相似度提出了基于页面相似度的p a g e r a n k 算法来解决主题漂移问题f7 1 ，2 0 0 7 他们还提出了主题相似的t s p a g e r a n k 算法来解决主 题漂移问题【1 9 1 等等。 目前对主题漂移问题还没有公认比较完好的解决方案。p a g e r a n k 计算效率问题也是 值得探讨的问题【2 0 2 ，p a g e r a n k 算法的一唑市h 关研究还在进行中。目前p a g e r a n k 算法是 w e b 检索的一个主要研究方向。 ( 2 ) h i t s 算法及其改进算法 h i t s 算法是1 9 9 8 年由康奈尔大学的k l e i n b e r g 博士提出的，k l e i n b e r g 提出了权威性网 页( a u t h o r i t y ) 和中心网页( h u b ) 的概念，并且认为这两种页面是相互加强的【6 1 。与p a g e r a n k 算法不同，h i t s 算法是和查询密切相关的。用户输入查询词后，h i t s 算法先利用一个 传统的文本搜索引擎( 侈j o l j a l t a v i s t a ) 获取一个与主题相关的网页根集合( r o o ts e t ) ，再根据 扩展规则向根集中增加页面，最后计算出每个页面的h u b g l a u t h o r i t y 值。h i t s 算法在i b m 的c l e v e r 系统中得到了应用，并且取得了良好的效果【2 2 】。 h i t s 算法出现后也得到了普遍的认可。针对不同的应用，许多学者对h i t s 算法提 出了改进。在实现a r c 系统时，i b ma l m a d e n 研究中心的c l e v e r 项目组结合超链内容提 出t a r c h i t s 算法1 2 2 】；a l l a nb o r o d i n 等在指出了一种不利于h i t s 算法计算的现象后， 提出了h u b 平均( h u b - - a v e r a g i n g - - k l e i n b e r g ) 算法和阂值( t h r e s h o l d k l e i n b e r g ) 算法；d c o h na n dh c h a n g 提出了计算h u b 和a u t h o r i t y 的统计算法p h i t s ( p r o b a b i l i s t i ca n a l o g u eo f t h eh i t s ) 2 引。西安交通大学的傅向华等在主题提取时使用- h i t s 算法并取得了可喜的 成果【2 4 2 5 1 。中国科学技术大学的肖明军等人提出了一种结合页面内容和相似性的 s h i t s ( s i m i l a r i t y h i t s ) 算法，证明其性能好于平均( h u b a v e m g i n g k l e i n b e r g ) 算法【2 6 i 。 第一章前言 南京大学的仲婷等人对w e b 超链结构进行深入分析的基础上，针对h i t s 算法的缺陷，通 过引入权值和调整因子对其进行改进【2 7 】。 这些算法从不同的角度来改进了h i t s 算法，在搜索中取得了比较好的结果，目前 h i t s 仍然是超链分析的主要研究方向。h i t s 算法在主题提取、社区发现、文本聚类分 类等方面有着很大的潜力【2 8 i 。但是由于h i t s 占用了用户的查淘时间，稳定性不如 p a g e r a n k ，凶此在搜索引擎中不如p a g e r a n k 应用广泛。 ( 3 ) 其他的超链分析算法 h i l l t o p 算法的指导思想和p a g e r a n k 的是一致的，都是通过网页被链接的数量和质 量来确定搜索结果的排序权重【2 9 】。但h i l l t o p 认为只计算来自具有相同主题的相关文档 对于搜索者的价值会更大：即主题相关网页之间的超链对于权重计算的贡献比主题不相 关的超链价值要更高。h i l l t o p 算法在2 0 0 1 年申请成为了美圈的专利，g o o g l e 成为专利 受让方。这种新算法与其页面等级系统的整合将为g o o g l e 的排名系统带来良好的效果。 目前由于专利的问题对其探讨的文章比较少。 p a g e r a n k 算法是基于用户随机冲浪模型的，h i t s 算法是基于a u t h o r i t i v e 网页和h u b 网页之间的加强关系。综合t p a g e r a n k 和h i t s 算法的优点，同时考虑到用户浏览页面时 的回退现象，2 0 0 0 年r l e m p e l 和s m o r a n 提出了s a l s a ( s t o c h a s t i ca p p r o a c hf o rl i n k s t r u c t u r ea n a l y s i s ) 算法1 3 0 】。s a l s a 算法基于两条马尔可夫过程链分别构成h u b 矩阵和 a u t h o r i t y 矩阵，这两条马尔可夫链分别为h u b 链和a u t h o r i t y 链。该算法在汁算上没有h i t s 的相互加强的迭代过程，计算量远小于h i t s ，实际的应用效果却等同于h i t s 。 2 0 0 1 年a l l a nb o r o d i n 等提出了完全的贝叶斯统计方法来确定h u b 和a u t h o r i t i v e 网页 【2 3 1 。这种方法的简化版相当于s a l s a 算法。贝叶斯算法是一种新颖的算法，国内外对其 研究和改进比较少。 总之，超链分析从提出到现在也仅仅只有1 0 年的时间，它能提高搜索引擎的查准率， 改善用户的浏览感受，已经成为网络信息检索领域的研究热点。目前，国内外尚未出现 比p a g r a n k 和h l t s 效果更好更有影响力的全新的超链分析算法，研究方向主要集中在对 p a g r a n k 平 h i t s 的改进上，虽然有很多学者提出了自己的方法，但仍有很大的改进空间， 因此对p a g r a n k 币n h i t s 的研究有着重要的现实意义。 4 中国白油大学( 7 f 尔) 硕l 学位论义 1 3 论文研究内容 论文的主要工作内容如下： ( 1 ) 搜索引擎和超链分析的相关理论 首先给出了搜索引擎的定义和研究范围，然后介绍了搜索引擎的分类、发展历程、 工作原理、评价指标，最后重点介绍了开源搜索引擎n u t c h ；介绍目前主流的超链分析 算法p a g e r a n k 和h i t s 及其衍生算法，最后给出了超链分析技术的发展方向。 ( 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 算法产 生主题漂移的原因，针对其存在的问题，根据超链的创建动机和实际作用，引入了超链 分类的概念，提出了基于超链分类的p a g e r a n k 改进算法。 ( 3 ) 基于超链内容的p a g e r a n k 调整算法 在对p a g e r a n k 计算过程研究的基础 二，发现p a g e r a n k 值不具备语义性。根据h i t s 在线聚类原理，在查询时根据查询词的语义进行p a g e r a n k 调整，提出了基于超链内容 p a g e r a n k 调整算法。 ( 4 ) 超链分析算法在搜索引擎中的应用研究 介绍了开源搜索引擎n u t c h 的排序公式和p a g e r a n k 在n u t c h 中的应用原理。在n u t c h 基础上设计了实验系统。对本文提出的超链接基于链接分类的的p a g e r a n k 改进算法进 行了编程实现，并应用到了n u t c h 上；在n u t c h 架构下开发了基于超链内容的p a g e r a n k 调整算法n u t c h 插件。实验结果证明改进的方法可以改善搜索结果的排名规则，使搜索 引擎的查准率得到有效提高，最后对这西种改进方法进行了比较和总结。 1 4 论文组织结构 论文共分六章，具体结构如下： 第一章“前言”，阐述了论文的研究背景和意义以及国内外研究现状，介绍了论文 的主要研究内容，最后给出论文的组织结构。 第二章“搜索引擎与超链分析”，首先给出了搜索引擎的定义和研究范围，介绍了 搜索引擎的分类、发展历程、工作原理和评价指标，重点介绍了开源搜索引擎n u t c h 。 然后介绍目前主流的超链分析算法p a g e r a n k 和h i t s ，最后总结指出了超链分析的发展 第章前占 方向。 第三章“基于超链分类的p a g e r a n k 改进算法9 99 对p a g e r a n k 算法的特点进行了分 析，找到了传统p a g e r a n k 算法产生主题漂移的原因，针对其存在的问题，根据超链创 建动机和实际作用引入了超链分类的概念，提出了基于超链分类的p a g e r a n k 的改进算 法。为了验证该算法，提出并实现了一种简单的超链分类方法。 第四章“基丁二超链内容的p a g e r a n k 调整算法9 9 9 在对p a g e r a n k 计算过程研究的基 础上，发现p a g e r a n k 值不具备语义性。根据h i t s 在线聚类原理，在查询时根据查询词 的语义进行p a g e r a n k 调整，提出了基于超链内容p a g e r a n k 调整算法。 第五章“基于n u t c h 平台的实验设计”，在开源搜索引擎n u t c h 基础上设计了实验 系统。将第三章和第四章的p a g e r a n k 改进算法应用到开源搜索引擎n u t c h 中，通过实 验证明了改进的算法可以改善搜索引擎检索性能，最后对两种改进方法进行了比较。 “总结”，对全文进行了总结，说明了论文的主要工作、主要创新点、存在的不足 以及未来发展的方向。 6 中国石油大学( f 仁东) 硕j j 工他论文 2 1 搜索引擎技术 第二章搜索引擎与超链分析 2 1 1 搜索引擎的定义及分类 广义上讲，搜索引擎是一种对w w w 站点资源和其他资源进行索引和检索的一类特 殊的计算机信息检索系统。因此，凡是可以查询互联网信息的检索系统都可以归为搜索 引擎。按照搜索引擎的工作方式，搜索 - 3 i 擎可以分为：全文搜索引擎、目录索引类搜索 引擎和元搜索引擎等；按照其发展的历史又可以分为第一代搜索引擎，第二代搜索引擎 和未来的搜索引擎；按照其应用范围不同，可以分为垂直搜索引擎( 也称专业搜索引擎) 和综合搜索引擎。 狭义上讲搜索引擎特指全文搜索引擎，因为目前它最成功并且代表了搜索引擎的发 展方向。它的定义如下：全文搜索引擎( s e a r c he n g i n e ) 足一种在互联网上查找信息的工 具，它通过网络机器人等前端程序收集互联网信息，对其进行索引，形成供查询用的数 据库。用户在搜索引擎的客户端程序中键入要查找的关键词，搜索引擎就会在所形成的 数据库中找出与该词相匹配的u r l ，并将结果显示给用户，用户可根据输出的结果选择 并访问相关站点【3 1 1 。 本文将遵从狭义定义来讨论搜索引擎，我们讨论的搜索引擎必具备三个典型的特 征：( 1 ) 有专门的蜘蛛程序( 也叫网络机器人) 来遍历互联网抓取信息；( 2 ) 能够对抓取后 的信息进行索引，并形成可以支持高速查询的数据库；( 3 ) 用户输入查询词后可以获取一 组相关的u r l 返回给用户。我们仅研究符合e 述定义的典型搜索引擎，目录查询搜索 引擎、元搜索引擎等不在本文的讨论范围内。 2 1 2 搜索引擎的发展历程 搜索引擎技术是伴随着互联网的发展而成长起来的。它经历了一下几个时期的发 展：蕴育阶段，第一代搜索引擎发展阶段，第二代搜索引擎发展阶段，未来发展阶段。 ( 1 ) 蕴育阶段 1 9 8 9 年，w w w 技术的出现使得浏览器和w e b 模式成为网络的主要的信息交流方 式。1 9 9 0 年m c g i l lu n i v e r s i t y 学生a l a ne m t a g e 等开发了a r c h i e 系统。a r c h i e 系统是第 一个可以自动索引互联网上匿名f t p 网站文件的程序，用户可以在a r c h i e 系统上搜索 f t p 文件，虽然用户必须输入精确的文件名搜索，但是它基本上已经具备了搜索3 - 3 i 擎的 第一：章搜索引擎b 超链分析 雏形。a r c h i ef t p 搜索币n t l 大天网的早期f t p 搜索颇有相似之处。但它还不是真正意义 的搜索引擎。虽然a r c h i e 并没有像搜索引擎一样拥有广泛用户，但是他们的思想肩发， 搜索引擎的出现。 ( 2 ) 第一代搜索引擎阶段 1 9 9 3 年8 月，斯坦福大学的学生在a r c h i t e x t 的基础上扩展成了一个搜索引擎e x c i t e ， 他们还利用分析字词关系对互联网上的大量信息作了更有效的检索。开源搜索引擎 n u t c h 的作者d o u g hc u t t i n g 先生曾在这个公司做过技术结构师。 1 9 9 4 可以说是搜索引擎的诞生年，这一年出现了一大批搜索引擎，包括： w e b c r a w l e r 、l y c o s 、i n f o s e e k 等，这些搜索引擎有的后来倒闭或者被收购，但是他们都 对搜索引擎技术的发展起到了里程e l 碑- 式的推动作用。 1 9 9 4 年初，华盛顿大学的学生b r i a np i n k e r t o n 创建了w e b c r a w l e r 搜索引擎，它足 第一个支持搜索文件全部文字的全文搜索引擎，之前的搜索引擎仅仅使用自人工评论或 程序自动取正文的前1 0 0 个字。w e b c r a w l e r 是第一个真正意义的搜索引擎。同年的创建 了l y c o s 提供了前缀匹配和字符相近限制，l y c o s 还是第一个在搜索结果中使用了网页 自动摘要的搜索引擎；i n f o s e e k 的用户界面比较友善、并且还有大量附加服务。中文搜 索引擎百度的创始人李彦宏曾在这个公司做过技术工作。1 9 9 5 年出现的a l t a v i s t a 大量 的创新功能使它迅速成为当时搜索引擎的代表，a l t a v i s t a 是第一个实现高级搜索语法的 搜索引擎。 这些搜索引擎就是现在第一代搜索引擎。他们基本上奠定了搜索引擎的技术基础， 以后的搜索引擎都是在他们的技术上发展起来的。他们的典型特征就是将传统的信息检 索技术应用到了搜索引擎上，比如说：空间向晕模型表示文档，自动摘要技术，全文索 引技术，高级检索语法。但是w e b 信息不同于传统的文档，所以导致第一代搜索引擎 准确率不高，不能满足用户的需要。 ( 3 ) 第二代搜索引擎阶段 w e b 的超链接是w e b 文档区别于传统文档的典型特征，学多专家学者利用这点并提 出了一些超链分析的算法，最成功最著名的就是p a g e r a n k 算法，它成功的应用到了 g o o g l e 中，使得g o o g l e 迅速脱颖而出，四次荣获s e a r c h e n g i n e w a t c h 【o 】读者选举出的最 杰出搜索引擎”成为全球用户最受欢迎的搜索引擎，并且市场份额也达到了第一。 另外值得一提的是中文搜索引擎百度，它在中文搜索中占据了第一的位置。它的创 始人李彦宏在美国拥有超链分析的专利。 8 中因臼油大学( o 仁东) 硕j ：学位沦文 采用超链分析技术是第二代搜索引擎搜索引擎的典型特征。北京大学的天网搜索引 擎的排序方法也考虑，超链接结构的影响【3 2 1 。超链接技术使得这些后起之秀迅速的超过 了前辈，目前超链接技术是研究的热点和搜索引擎界最高的商业机密。 ( 4 ) 未来搜索引擎阶段 虽然基。j 二超链分析的第二代搜索引擎的查询率已经比较高，但足人们总是想直接检 索到最需要的信息。因此，搜索引擎面临的问题就是使得搜索引擎通过某种渠道能够“理 解”人们需求，智能搜索引擎是最理想的搜索引擎。但是，人的思想时刻都在变化，按 照目前的技术条件做到完全智能是不大现实的。目前，一些自我宣称实现了智能检索的 搜索引擎效果未必能比的上百度、g o o g l e 。因此，第二个方法就是人为地去选择专业搜 索引擎，各个专业的搜索引擎仅仅是本行业的“专家”。( 专业搜索引擎也叫垂直搜索引 擎或者主题搜索引擎，也可以反映出专业搜索引擎的特点) 。目前g o o g l e 的学术检索、 百度的m p 3 搜索就属于这类。目前专业搜索引擎受欢迎的程度远远高于智能搜索引擎。 2 1 3 搜索引擎的工作原理 搜索引擎一般是由搜集器( 也称为网络爬虫、机器人程序) 、管理器( 索引器) 、榆索 器( 用户接f ) 三个部分组成，如图2 1 所示。搜集器负责从网络上搜集网页，其主要表 现形式足网络机器人，它可自动在互联网上进行搜索。检索器提供刚络用户检索界面， 并根据用户的杏询要求，从信息数据库中检索出与之相关的信息资料并反馈给用户。管 理器负责搜索策略的制定及管理、索引的增删改、存储组织等【3 l 】。 搜索引擎的l ：作整体上来说可以分为前台工作和后台： 作。前台工作主要是指用户 可以看到的界面，由检索器负责完成。目前搜索引擎检索界面一般足以w e b 形式展现 的。 搜索引擎的后台工作比较复杂，由搜集器和管理器分米两个步骤完成。第一步是抓 取页面。如图2 1 所示，爬虫程序( s p i d e r ) 先从种子u r l 列表开始抓取页面，抓取到的 页面存到数据库中，然后解析这些页面，从页面中提取出其包含的超链接，将这屿超链 接加入到u r l 列表中。依次循环，直到满足停止条件为止。目前爬虫程序的抓取策略 可以采取深度抓取、广度抓取、站点抓取、主题抓取等。第二步足索引负面。索引页面 一般采取倒排文档的方式。采用倒排文档的主要的原因足它的检索速度很快，一般1 秒 内就町以完成。 9 第：亭搜索弓i 擎1 j 走c i 链分析 起始u r l 图2 1 搜索引擎工作原理图 f i 9 2 1p r i n c i p l eo fs e a r c he n g i n e 2 1 4 搜索引擎的评价指标 目前，各个主要的搜索引擎采用技术和服务范围不尽相同，因此综合各项性能指标 差异很大。评价一个搜索引擎应该从多个方面来评价。搜索引擎的定量评价引擎评价指 标定义为五类：索引构成、检索功能、检索效果、检索结果和用户交互【3 3 j ，见图2 2 。本 文旨在研究w e b 信息检索的效果，目前搜索引擎的响应时间差别不大。因此详细介绍一 下检索效果指标中的查准率和查全率。 l o 中国l i 油人学( 。f ；东) 硕上学位论义 重复牢 死链接牢 响应时问 结果显示格式的种类 每种显示的内容 检索结果排序依据 图2 - 2 搜索引擘评价指标 f i 9 2 2e v a l u a t i o nm e a s u r eo fs e a r c he n g i n e ( 1 ) 查全率与相对查全率 查全率是指检索出相关文献的数量和文献空间中所有相关文献数量之比【3 引。由于因 特网上信息的海量性和动态性，我们无法确定所有相关文献的数量。凤元杰等人根据多 目标优化的原理给出一种相对查全率指标的计算方澍3 5 1 。 假设彳，( f _ l ，2 ，朋) 为第f 个搜索引擎，剐= l ，2 ，聆) 为彳i 同的查询词。在一个给定 时间内，搜索引擎的返叫结果足稳定的。可以得 m 玎的矩阵p = 口1 月 口2 月 “i口m 2 口m t ，口。为查询词码在4 ，搜索引擎e 查询时返回的 一一一一一一；|i 第：章搜索引犟j 超链分析 记录数。 a 。, = m a x a u ，a 2 j ，a m j q = l ，2 ，胛) ，b ：= m i n a l j ，a 2 j ，a m j ) q = l ，2 ，肝) 虚拟构造两个极端情况的搜索引擎。用a b e ，= ( “i 。a ：，a ：) 表示对不同查询词在查 询时返回记录数均为最多的搜索引擎，a h 。，为最好搜索引擎。a w , o r s t = ( 6 1 ，b 2 ，玩) 表示查 询时返回记录数均为最少的搜索引擎，彳。为最差搜索引擎【3 5 1 。 口尸( 口：- a ，) ( i = l ，2 ，m ) ( 2 1 ) 6 f - ( 日。一6 j ) ( f = l ，2 ，脚) ( 2 2 ) 其中a ，表示搜索引擎a ，在查全上与a 胁接近的程度。a ，越小彳，搜索引擎查全性能相 对越好。而b ，表示搜索引擎a ，在查全方面优于爿、，的程度。可以定义搜索引擎a ，的相 对查全率，如式2 3 ： 、 r ( a _ f ) = 毫( 卢l ，2 ，卅) ( 2 - 3 ) a l + b l 可得，o = r 似f ) = l ，当彳f 为彳6 p 盯时，r ( a ，) = 1 ；当彳，为a w 口肘，时，r ( a ，) = 0 。 ( 2 ) 查准率与相对查准率 查准率是指检索出相关文献的数最和检索出的文献总镀之比。对搜索引擎来说，检 索结果的返回数都比较大，相关性判断的工作量非常之大，这降低了可操作性。但是风 元杰等人提出了一种可行的相对查准率的计算方法。 相对查准率的基本思想是一种分类加权思想。对不f 司查询词，尼，确定一个 相关性范畴的等级，对不同的等级给出权数，根据加权公式计算出p ) ，然后再对所 有查询词的尸) 求平均值，即为搜索引擎a 的相对查询率p ( a ) t 35 1 。具体的计算方法如 下： 计算尸) 将前3 0 条记录分为4 组，记为j = 1 , 2 ，3 ，j z = 4 ，5 ，l o ) ，以= 1 1 ，1 2 ，2 0 ， j t = 2