（计算机系统结构专业论文）nutch搜索引擎中网页排序技术的研究.pdf

iiti t l l1 1iil 9 0 3 1 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和 相关知识产权属广西大学所有，本人保证不以其它单位为第一署名单位发表或使用本 论文的研究内容。除已注明部分外，论文中不包含其他人已经发表过的研究成果，也 不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮助的个 人和集体，均已在论文中明确说明并致谢。 论文作者签名：纠口年占月2b 日 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： d 即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：、彳勿沙例导师签名辍纠留年占月三汨 n u t c h 搜索引擎中网页排序技术的研究 摘要 随着互联网技术的不断发展，搜索引擎已经成为人们获取网络信息的 主要工具。研究搜索引擎网页排序的目的是从众多搜索结果中将内容相关 和权威的网页排在前面，帮助用户迅速定位需要的网络资源。网页排序算 法直接影响到搜索引擎信息检索的准确率和用户使用满意度。n u t c h 是基于 j a v a 实现的开源搜索引擎。通过对n u t c h 进行深入研究，指出其目前存在 的两大问题，其一是没有实现p a g e r a n k 算法，影响了最终排序效果；其二 是对中文进行单字切分，影响了查询结果准确率。 首先，针对目前n u t c h 搜索引擎中没有实现网页p a g e r a n k 计算的问题， 利用m a p r e d u c e 并行计算模型处理大数据集的优势，在n u t c h 机群系统上 设计和实现了基于m a p r e d u c e 的p a g e r a n k 分布式并行算法。实验结果表 明：处理的数据量越大，机群中的节点越多，计算p a g e r a n k 的效率越高； 另外，该分布式并行算法具有较好的可扩展性。然后，针对目前n u t c h 对 中文进行单字切分的问题，加入了j e 中文分词器对n u t c h 的中文分词进行 改进。在分析和研究经典p a g e r a n k 算法原理的基础上，通过设置控制站外 与站内链接的比重因子对该算法进行了改进。为了改善n u t c h 基于l u c e n e 的网页综合排序模型，将改进后的p a g e r a n k 算法因子融入到n u t c h 网页评 分计算公式当中。实验表明，改进后n u t c h 明显提高了查询结果的准确率， 改善了中文网页的排序效果。 关键词：n u t c h 搜索引擎网页排序p a g e r a n k 算法 中文分词 m a p r e d u c e 并行模型 r e s e a r c ho fw e bp a g e sr a n k i n g i nn u t c hs e a r c he n g i n e a b s t r a c t w i t ht h ec o n t i n u o u sd e v e l o p m e n to fi n t e r n e tt e c h n i q u e ，s e a r c he n g i n eh a s b e c o m et h em a i nt o o lf o rp e o p l et oo b t a i nn e t w o r ki n f o r m a t i o n t h er e s e a r c h g o a lo fw e bp a g e sr a n k i n gi n s e a r c he n g i n ei sp u t t i n gt h er e l a t e da n d a u t h o r i t a t i v ew e bp a g e si nt h ef r o n to fm a n ys e a r c hr e s u l t sa n dh e l p i n gu s e rt o l o c a t et h en e t w o r kr e s o u r c er a p i d l y t h ei n f o r m a t i o nr e t r i e v a la c c u r a c yo f s e a r c h a n du s e r ；a t i s f a c t i o n f f e c t e db yt h ew e brankingsearch e n g i n ea n du s e rs a t l s t a c t l o n i sa t t e c t e at h ew e dp a g e s y a l g o r i t h md i r e c t l y n u t c hi sa no p e ns o u r c es e a r c he n g i n eb a s e do n j a v a n u t c h h a sb e e nr e s e a r c h e di nd e t a i l p r e s e n t l y ，t h e r ea r et w od e f e c t si nn u t c h f i r s t l y ， t h ep a g e r a n ka l g o r i t h mi sn o ti m p l e m e n t e d ，s ot h eq u a l i t yo fw e bp a g e s r a n k i n gi si n f l u e n c e d s e c o n d l y ，t h ec h i n e s ei n d i v i d u a lc h a r a c t e rs e g m e n t a t i o n i su s e d ，s ot h ea c c u r a c yo fs e a r c hr e s u l t si sa f f e c t e d f i r s t ，i nv i e wo ft h ed e f e c ti nn u t c hw h i c hh a sn o tr e a l i z e dt h ep a g e r a n k c o m p u t a t i o n ，t h es u p e r i o r i t yo fp r o c e s s i n gl a r g ed a t a s e t sb a s e d o nm a p r e d u c e i su t i l i z e d ，a n dt h em a p r e d u c e b a s e dp a g e r a n kd i s t r i b u t i o n a lp a r a l l e l a l g o r i t h m i s d e s i g n e d a n di m p l e m e n t e do nn u t c h c o m p u t e c l u s t e r s e x p e r i m e n t ss h o wt h a t t h em o r ep r o c e s s i n gd a t aa n dc l u s t e rn o d e sa r e ，t h e i h i g h e re f f i c i e n c yo fc o m p u t i n gp a g e r a n ki s ；m o r e o v e r , t h i s d i s t r i b u t i o n a l p a r a l l e la l g o r i t h mi s o fg o o ds c a l a b i l i t y n e x t ，i nv i e wo ft h ed e f e c ti nn u t c h w h i c hu s e sc h i n e s ei n d i v i d u a lc h a r a c t e rs e g m e n t a t i o n ，j ec h i n e s es e g m e n t a t i o n i sa d d e dt o i m p r o v ec h i n e s es e g m e n t a t i o n i nn u t c h a i t e rt h ec l a s s i c a l p a g e r a n ka l g o r i t h mi sa n a l y z e da n ds t u d i e d ，t h i sa l g o r i t h mi si m p r o v e db y s e t t i n gf a c t o rw h i c hc o n t r o l st h ep r o p o r t i o no fo u t s i d el i n k sa n di n s i d el i n k s i n o r d e rt oi m p r o v et h ew e bp a g e sr a n k i n gs y n t h e t i c a lm o d e lb a s eo nl u c e n ei n n u t c h ，t h ei m p r o v e dp a g e r a n kf a c t o ri s a d d e di n t ot h en u t c hw e bp a g e s s c o r i n gf o r m u l a e x p e r i m e n t ss h o w t h a tt h ea c c u r a c yo fs e a r c hr e s u l t si sr a i s e d a n dt h er a n k i n gq u a l i t yo fc h i n e s ew e bp a g e si si m p r o v e do b v i o u s l ya f t e rt h e i m p r o v e m e n t i nn u t c h k e yw o r d s ：n u t c hs e a r c he n g i n e ；w e bp a g e sr a n k i n g ；p a g e r a n ka l g o r i t h m ； c h i n e s es e g m e n t a t i o n ；m a p r e d u c ep a r a l l e lm o d e l 目录 摘要i a 】i i s t r a c t i i i 第一章绪论1 1 1 论文研究背景1 1 2 搜索引擎简述2 1 3 搜索引擎网页排序算法的研究现状。3 1 3 1 搜索引擎排序技术的研究发展3 1 3 2 基于链接分析的改进算法5 1 3 3 搜索引擎综合排序模型6 1 4 论文研究的目的和意义7 1 5 论文的主要工作和组织结构7 第二章n u t c h 搜索引擎相关技术介绍9 2 1l u c e n e 与n u t c h 9 2 2m a p r e d u c e 并行计算模型1 1 2 3 分布式文件系统h d f s 1 4 2 4n u t c h 中的并行计算与机群部署1 4 2 4 1n u t c h 中的分布式并行计算：1 4 2 4 2n u t c h 机群的部署与配置1 5 2 5 本章小结1 6 第三章n u t c h 中p a g e r a n k 算法的并行实现- 17 3 1 引言17 3 2p a g e r a n k 算法原理。1 7 3 2 1 随机冲浪模型。1 7 3 2 2p a g e r a n k 算法特性与迭代计算实验18 3 3 基于m a p r e d u c e 的p a g e r a n k 并行算法2 0 3 4 实验与分析2 2 3 4 1 构建机群系统环境2 2 3 4 2 实验结果与分析2 2 3 5 本章小结2 5 第四章n u t c h 中网页排序效果的改进与实现2 6 4 1 引言2 6 4 2 对p a g e r a n k 算法的改进2 7 4 3 对n u t c h 中文分词的改进2 8 4 3 1 中文分词技术2 8 4 3 2 在n u t c h 中加入j e 中文分词器2 9 4 4 对n u t c h 网页综合评分算法的改进3 0 4 4 1n u t c h 中基于l u c e n e 的网页评分算法3 0 4 4 2o p i c 算法31 4 4 3 改进n u t c h 网页评分公式。3 2 4 5 实验与分析3 3 4 5 1t o p n 查准率对比3 3 4 5 2 排序效果对比3 4 4 6 本章小结3 5 第五章总结与展望3 6 5 1 总结3 6 5 2 展望3 6 参考文献3 8 刭c 谢4 l 攻读硕士学位期间参加的科研项目4 2 攻读硕士学位期间发表录用的学术论文4 2 广西大学硕士掌位论文n u t c h 搜索引擎中网页排序技术的研究 1 1 论文研究背景 第一章绪论 随着互联网技术的不断发展，网络中的站点数量飞速增加，包含的各种信息资源丰 富巨大，网络与人们的生活和工作密不可分。无论是进行网络购物还是在线远程教育， 不管是查询资料信息还是朋友聊天交流，相应的网络服务都层出不穷，满足了人们多方 面的生活需求。但是，面对如此巨大的网络信息库，人们如何快速有效地从中获得对自 己的工作和生活有价值的信息呢? 搜索引擎技术的诞生，就很好地解决了人们检索网络 信息的难题。w e b 搜索引擎从1 9 9 4 年开始出现，到现在已经有十几年的历史了，诞生 了不少使用广泛的商业搜索引擎，如g o o s e 、百度和雅虎等，用户可以尽情享受搜索 引擎带来的快捷与便利。因此，搜索引擎已经成为人们获取网络信息的一种最重要的手 段，也成为计算机科学领域研究的热点川。 搜索引擎最初只能检索十几万个w e b 页面，而现在已经可以检索上百亿个页面， 并且检索量还在逐年上升。随着可检索页面量的不断增大，用户将会获得更多的搜索结 果。虽然搜索引擎公司声称其可检索页面范围仍不能覆盖整个因特网，但是从目前现有 的检索页面中返回的结果数据看，页面量已经很多了，而用户是不可能对如此多的检索 页面都逐一浏览的。根据美国搜索引擎营销专业服务商i p r o s p e c t 发布的搜索引擎用户 使用习惯情况调查报告显示【2 】，超过8 0 的用户不会去浏览3 页以后的检索结果，而超 过一半的用户只会浏览搜索引擎检索结果中的第一页。由此可知，用户一般只关注搜索 引擎检索结果中排在前面的页面。因此，提高搜索引擎检索结果页面的准确率是非常重 要的，尤其是排在前面几页的检索结果。 搜索引擎的目标就是帮助用户快速定位所需要的资源，并按一定的形式把搜索结果 呈现给用户。那么，如何从众多的检索结果页面中将最相关和权威的页面排在最前面， 就成了搜索引擎需要解决的问题之一。当用户在搜索引擎查询页面输入查询词进行检索 时，总是希望能及时迅速检索出最想要的结果，并且这些结果能排在搜索结果中的最前 面。因此，搜索引擎检索结果的排序效果好坏直接影响到用户能否方便快捷地获取所需 的信息资源，同时也直接关系到用户使用该搜索引擎的满意程度【3 】。而决定排序效果的 是搜索引擎的网页排序算法，算法设计的好坏直接影响着搜索引擎信息检索的准确率和 用户使用满意度，故排序算法是搜索引擎最核心的部分之一，也是决定搜索引擎成败的 关键，因此成为当前搜索引擎研究领域中的热门话题。 目前，如g o o s e 和百度等这些商业搜索引擎，由于技术和利益方面的保密性，其 中的网页排序算法涉及商业机密，人们无法知晓。但是，开源搜索引擎n u t c h 4 的诞生， 为广大学者研究搜索引擎提供了很好的选择，可对其中基本的网页排序算法技术进行研 p - 西大学硕士学位论文n u t c h 搜索引擎中网页排序技术的研究 究和改进，以达到更好的排序效果。 1 2 搜索引擎简述 现代搜索引擎的祖先，是由加拿大m c g i l l 大学计算机学院的a l a ne m t a g e 等三名 学生在1 9 9 0 年发明的a r c h i e ，它是第一个在互联网中自动索引匿名f t p 网站文件的程 序，但搜集的信息资源不是网页，因此还不是真正意义上的搜索引擎。简单地说，搜索 引擎( s e a r c he n g i n e ) 是指利用某种计算机程序按照特定的策略对互联网信息进行搜集， 然后将组织和处理后的信息按一定的方式显示给用户，为用户提供检索服务的系统【5 】。 搜索引擎的工作原理大致可分为四个阶段，即网页爬取、网页预处理、网页索引和 用户检索【6 1 。 1 、在网页爬取阶段，搜索引擎利用网页爬行程序s p i d e r ( 也称为网络蜘蛛) ，顺着网 页中的超链接连续不断地对网页进行抓取，直到满足一定的条件才停止抓取。从互联网 有关超链接的理论上讲，如果从某个范围的网页集合开始出发进行搜集，就能获取到互 联网中绝大部分的网页。 2 、在网页预处理阶段，主要对爬取到的大量网页进行去重去噪、分词处理、网页 链接分析、网页重要程度的计算等工作，并调用相关的文档解析器将非格式化的网页文 档转化成格式化的文档。 3 、在网页索引阶段，对己格式化的网页文档进行信息提取工作，例如网页的u r l 、 页面中的关键词及其位置信息、网页的生成时间以及网页之间的链接关系等，然后用这 些相关信息来建立网页索引数据库文件。 4 、在用户检索阶段，首先用户在搜索入口页面输入查询词，然后搜索引擎的检索 程序从索引文件库中找到与该查询词匹配的网页，并按照一定的网页排序算法将搜索结 果呈现给用户，搜索结果中除了提供网页标题和u r l 之外，还会显示一些与网页有关 的摘要信息等，方便用户查询到所需的网页。 搜索引擎主要分为三类，即目录索引搜索引擎、全文索引搜索引擎和元搜索引擎【_ 7 1 。 1 、目录索引是以人工或半自动方式进行信息搜集后，由人工对搜集到的信息进行 整理并形成摘要，接着将摘要信息存放到预先确定好的分类当中。从严格意义上来说， 目录索引不能算作真正的搜索引擎，它只是按照一定的目录分类罗列出网站链接而已， 用户可以不用进行关键词查询，而只需在分类目录去寻找所需要的信息即可，其中最具 代表性的是雅虎和新浪分类目录搜索。 2 、全文索引搜索引擎是真正意义上的搜索引擎，它们利用网络蜘蛛程序爬取互联 网的网页信息，然后建立相应的索引数据库，并能根据用户的查询词对索引库中进行检 索，找到与查询词相匹配的记录，接着按一定的排列顺序返回给用户相应结果，g o o g l e 和百度就属于此类的典型代表。 3 、元搜索引擎也叫集合型搜索引擎，它们没有自己的数据库，而是将用户的查询 广西大学硕士学位论文n u t c h 搜索引擎中网页排序技术的研究 请求同时发送给多个搜索引擎，然后对返回的结果进行去重和排序等处理后呈现给用 户。国外著名的元搜索引擎有v i v i s i m o 、d o g p i l e 和i n f o s p a c e 等，国内元搜索引擎的典 型代表是搜星搜索引擎。 1 3 搜索引擎网页排序算法的研究现状 1 3 1 搜索引擎排序技术的研究发展 在当今信息化社会，互联网遍布整个世界，搜索引擎也在高速发展，越来越多的网 民使用搜索引擎提供的检索服务，让搜索引擎成为互联网的热点之一。根据c n n i c 调 查显示【8 】= 在网民使用的网络服务中，搜索引擎所占比例由一年前的5 7 8 上升到6 8 5 ；在网民获得新网站途径中，搜索引擎所占比例由一年前的7 5 6 上升到8 7 5 ； 在网民获取网络信息方法中，搜索引擎所占比例由一年前的6 3 8 增长到7 2 6 。从搜 索引擎的发展变化可以看出，搜索引擎的排序技术成为其决定因素和划分标准。g o o g l e 因为拥有其发明的p a g e r a n k 排序技术，成为全世界使用最广泛的搜索引擎；百度因为 拥有其独创的超链接分析排序技术，成为全球最知名的中文搜索引擎。 因此，如果按照排序技术划分【9 】，搜索引擎可分为如下三类： l 、基于词频统计排序的搜索引擎 这种搜索引擎是由情报检索理论发展过来的，该理论认为网页出现检索词的频率越 高，位置越重要，则网页和检索词的相关性越好。词频加权的方法有以下几种，即绝对 词频或相对词频加权、基于词分辨值加权和反词频加权等。例如，对某个词在网页中出 现的频率来给定权值，其中可对出现频率高的词赋予较低的初始值，而对出现频率低的 词赋予较高的初始值。词位置加权中的权值与检索词在页面中出现的位置和版式有关， 网页和检索词的相关度由权值大小来决定。其中，词的位置可以包括网页的标题、网页 的摘要、正文的标题或内容、锚文本等，版式是指网页的字体类型、字号大小、文字粗 细等等。例如，可对网页标题或摘要中出现的词以及对网页中字号较大或加粗的词赋予 较大的权值等。 词频统计具有简易实用的优点，是目前发展最成熟的技术之一，并成为搜索引擎排 序技术的基础。缺点是没有充分利用网页特性，也许会出现这样一种情况，两个网页的 词频相同，但它们的质量却天差地别。另外，也会出现某些网站故意在网页中堆积大量 关键词来提高网页排名的作弊行为，目前，搜索引擎的设计者已经采取了很多措施来对 这种作弊行为进行治理和处罚。 2 、基于链接分析排序的搜索引擎 这种搜索引擎是由文献引用思想发展而来，该思想中认为一篇好论文的标准是被许 多高质量的论文引用，引用次数越多就说明该论文越好越权威。于是，网页链接分析也 借鉴了文献引用的思想，认为一个好网页的标准是被许多高质量的网页链接，链接次数 越多就说明该网页越好越重要。1 9 9 8 年诞生了两个基于超链接分析的经典网页排序算 n u t c h 拽索引擎中网页排序技术的研究 法，分别由l a r r yp a g e 和s e r g e yb r i n 提出的p a g e r a n k 算法以及由k l e i n b e r g 提出的h i t s 算法，它们又分别被应用到g o o s e 搜索引擎以及i b m 的c l e v e r 智能系统中。 p a g e r a n k 算法【1 0 】体现了“民主选举”的思想。首先，该算法认为网页x 链向网页y 即表示x 给y 投了一票，然后统计出每个网页的得票数，票数越多的网页就被认为是 重要权威的网页。另外，除了统计网页的得票数( 链接数) 外，还要考虑选票的“含金量”， 即为某网页投票的网页是否重要权威，可想而知，权威网页就如权威人物一样，投出的 票自然具有较高的价值，获得这些选票的网页的重要性自然也提高了。因此，某网页要 想取得“选举”的胜利，就必须获得很多的投票数( 链接数) ，并且选票的质量( 投票网页的 权威性1 越高越好。 p a g e r a n k 算法如公式( 1 1 ) 所示【1 1 】，其中p r ( 是网页【，的p a g e r a n k 值，p r ( z i ) 是 链向网页u 的网页v i 的p a g e r a n k 值，c ( 功是网页所的链出数量，d 为阻尼系数( 脉1 ) 。 p r ( u ) = ( 1 一d ) + d ( 尸r ( k ) c ( k ) + p r ( v 2 ) c ( v j ) + + 尸尺( 圪) c ( 圪) )( 1 1 ) 由此可知：( 1 ) p a g e r a n k 计算对象是单个网页，网页u 的p a g e r a n k 值主要由链向 u 的所有网页的p a g e r a n k 递归值确定；( 2 ) 如果网页m 的链出数越多，则网页u 受到 所链接的影响就越小：( 3 ) p r ( 是所有p r ( v i ) x t 力i 而求得，因此网页u 的入链越多，p r ( 的值越大：( 4 ) 阻尼系数d 值设置为0 到1 ，一般取值0 8 5 ，它可以削弱其它网页对网页 u 的链入贡献值。 h i t s 算法【1 2 】将网页分成具有相互加强作用的两类，一类是具有较高价值的权威网 页( a u t h o r i t y ) ，依赖于链向它的网页：另一类是指向较多权威网页的中心网页( h u b ) ，依 赖于它链向的网页。该算法主要包括两个过程：( 1 ) 生成网页链接子图，即根据查询词 从检索结果中取前n 个网页构成根集s ，向s 中添加被s 引用和引用s 的网页扩充成 集合t ，利用t 中的网页以及网页间的链接构成网页链接子图g ：( 2 ) 计算网页的a u t h o r i t y 和h u b 值，首先把g 中各网页的a u t h o r i t y 和h u b 值初始化为1 ，然后进行i o 操作迭代 计算并作规范化处理，直到结果收敛获得各网页的a u t h o r i t y 和h u b 值。总之，针对某个 查询词，h i t s 算法通过迭代计算方法找到价值( a u t h o r i t y ) 高的网页，可以取得较好的 查全率，并输出一组较大权威值和中心值的网页。 链接分析排序算法的优点是在词频统计的基础上更注重排序结果的重要性和权威 性。但是，也出现了某些网页设计者为了提高在搜索引擎的排名，利用对网页进行链接 添加、链接交换或者链接欺骗等手段进行作弊的现象，从而导致用户很难搜索到一些内 容质量高却没有很多链接的网页。另外，链接分析的算法缺点是纯粹地基于链接分析来 发现权威网页，而没有充分考虑网页的具体内容，存在所谓的“主题漂移( t o p i cd r i f t ) ”l i 刊 问题，即算法的结果中往往包含一些相互链接密度较高但在内容上却偏离了查询主题的 网页。 3 、基于智能化排序的搜索引擎 到目前为止，大多数商业搜索引擎都是在基于词频统计和链接分析排序技术的基础 广西大学硕士学位论文 n u t c h 搜索引擎中网页排序技术的研究 上进行不断完善和优化，并在朝着智能化排序的方向发展【1 4 1 。百度提出的竞价排名服务 是收费排名的一种，先由客户为自己的网页向百度购买关键字排名，然后百度对该网页 的点击量进行计费【1 5 , 1 6 。但是，收费排名的结果排序缺乏真实性并有失公正性，不能算 是智能化排序。 真正意义上的智能化排序应包括如下几个方面 i7 】：个性化排序、基于语义排序、基 于主题排序以及智能去重排序等。其中，个性化排序是通过用户反馈来提高排序准确性， 在搜索引擎不断“学习”到用户的行为模式后，使其越来越满足用户的需求。基于语义排 序时通过运用自然语言识别和人工智能等多方面的技术把关键词级别映射到概念级别， 并结合上下文内容分析和近义词、同义词、多义词处理技术，不断增加对检索词和网页 之间的语义相关度的理解和分析。基于主题排序则使排序结果更趋向于某个主题，是垂 直搜索引擎技术中的关键。智能去重排序是自动识别检索结果中重复的网页或网站，然 后进行智能过滤和去重。另外，基于多媒体信息的检索排序技术也是搜索引擎未来要发 展的方向。 1 3 2 基于链接分析的改进算法 为了有效的抑制基于链接分析算法的“主题漂移”现象，出现了一些基于超链接和内 容的网页排序算法，在链接分析的基础上引入网页内容信息的影响因素，它们都是在 p a g e r a n k 算法和h i t s 算法两个经典的算法基础上进行改进的。 1 、h i l l t o p 算法【1 8 】是2 0 0 1 年由g o o g l e 的工程师b h a r a t 对p a g e r a n k 算法进行的改 进。该算法更注重计算来自具有相同主题的网页链接，认为主题相同或相关的网页之间 的链接比主题不相关的链接价值要更高。例如，如果某网页是有关“体育”的，那么对于 那些链入该网页的有关“体育”的网页链接就比有关“军事”的网页链接的贡献价值要大 些。影响主题的网页称为专家网页，这些网页决定被链接网页的权重得分。另外，h i l t o p 算法有效解决了某些试图通过增加大量无效链接来提高网页排名的作弊问题。 2 、c a t e g o r y r a n k 算法f 1 9 】将分类技术融入到排序算法中，在加入类别信息后能获得 更加准确的排序结果，它克服了p a g e r a n k 算法与查询词无关的缺点，具有让相同或者 相似类别的网页更加相关的优点。该算法从三方面把分类技术应用到搜索引擎的排名当 中：( 1 ) 对每一个链接，把所链接网页的类别信息加权到p a g e r a n k 值中，转变成基于链 接的c a t e g o r y r a n k 算法；( 2 ) 在所有网页中，计算每种类别的c a t e g o r y r a r t k 向量；( 3 ) 对用户查询关键词进行分类，结合查询记录以及个人爱好等信息来获取用户的兴趣类 别，并根据离线计算结果来提高网页排名的准确性。总之，该算法同时考虑了链接的类 别相关性和网页的类别差异，最后把每个网页的类别信息都集成进来。 3 、s p a g e r a n k 算澍2 0 ，2 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 值高的现象。另外，把s p a g e r a n k 广西大掌硕士掌位论文 n u t c h 搜索引擎中网页排序技术的研究 算法和h i t s 算法结合起来形成f p a g e r a n k 算法，用于迭代计算网页的h u b 和a u t h o r i t y 值，该算法基本思想是出站链接多的网页具有较高的h u b 值，而入站链接多的网页具有 较高的a u t h o r i t y 值。当上网浏览者对某个网页感到厌倦时，一般会选择出度或入度大的 网页继续浏览，所以这些网页应比随机浏览的网页具有更高的得分。 4 、融入链接相关度p a g e r a n k 算法的【2 2 ，2 3 】认为网页中各个链接不是平等的，而是存 在竞争的。为了实现链接之间的竞争性，该算法对链接标题内容( 锚文本) 和其所指向网 页的内容进行相关度计算。算法基本思想是：( 1 ) 如果网页x 链向网页y ，链接标题内 容与网页y 内容相关度越高，x 对y 的贡献越大；( 2 ) 把所有对网页y 有贡献的网页 p a g e r a n k 值相加求和作为y 的p a g e r a n k 值。该算法在保持p a g e r a n k 算法计算效率基 础上，进一步改善了网页评分，并在智能和语义排序方面做出了新的尝试。 5 、a r c 算法【2 4 】是由i b m 的c l e v e r 研究小组提出，它是在h i t s 算法的基础上考 虑了网页链接锚文本信息对网页排序的影响。h i t s 算法在计算a u t h o r i t y 和h u b 值时， 平等对待网页之间的各个链接，而事实上每个链接的重要性是不相同的。该算法充分利 用了链接锚文本和搜索主题之间的相关度来给予链接不同的重要性，并根据各链接的重 要性权值重新构建一个矩阵，取代原来的网页链接子图邻接矩阵来计算网页的a u t h o r i t y 和h u b 值。 6 、a v e r a g e 算法【2 5 】和s i m 算法f 2 6 】分别由j g e v r e y 和s r u g e r 提出的基于超链接和 内容的网页排序算法。它们与h i t s 算法的不同之处在于：( 1 ) 在向搜索引擎提交查询词 并获取网页根集的过程中，h i t s 算法忽略了每个页面与查询词的相似度s i m i l a r i t y 值， 只是利用网页链接信息来计算网页的a u t h o r i t y 和h u b 值。但是，a v e r a g e 和s i m 算法却 利用了s i m i l a r i t y 值来计算网页的a u t h o r i t y ：( 2 ) 在对网页的a u t h o r i t y 和h u b 值进行迭代 计算时，h i t s 算法需要迭代计算若干次直到结果收敛，而a v e r a g e 算法和s i m 算法只 需考虑相邻网页对结果的影响，它们的迭代计算次数仅为l 。 1 3 3 搜索引擎综合排序模型 搜索引擎综合排序模型是建立在现有的排序算法和技术基础之上，将现有的排序技 术优化并结合起来应用到搜索引擎排序模型中。国外对综合排序模型已有不少研究，在 国内北京大学的天网搜索引擎项目在综合排序模型方面做出了理论和实验的探索，并在 天网中建t w e b g a t h e r t 2 1 7 】的排序模型，该模型包含三个重要因素：网页内容、网页链 接、用户行为，它们共同决定网页的最终权重。 ( 1 ) 网页内容。一个关键词的权重由网页标签权重、网页大小权重和关键词频率权重 构成。在经典的t f * i d f 算法中加入文件长度因子，并赋予频繁出现在规模小的网页集中 的关键词更高的权重。 。 ( 2 ) 网页链接。在网页链接中只考虑异网站链接数目，并赋予新网页一定的权重补偿， 因为新网页刚开始的点击量往往较少。 ( 3 ) 用户行为。当用户输入查询词并获得搜索结果后，先查看网页的摘要信息，当用 n u t c h 搜索引擎中网页排序技术的研究 户找到与查询相关的摘要时，就点击其超链接来访问网页。通常用户只会浏览搜索结果 中的前几页，因此较难被浏览和点击并排在后面的搜索结果，应给这些后面的结果相应 的权重补偿。 在计算最终网页权重时，w e b g a t h e r 采用了综合指数法对网页内容基本权值、链接 权值以及用户评价权值三个指标进行加权求和，即人为指定加权因子的比例，带有一定 的主观因素。总之，w e b g a t h e r 模型考虑到了三种主要的相关性排序技术并加以综合， 在每一种相关性排序技术中，又给出了具体的方法并进行优化，是一个相对完备的综合 模型【2 8 1 。 1 4 论文研究的目的和意义 目前，搜索引擎已经成为人们获取网络信息的主要工具。其中，搜索引擎网页排序 算法决定了搜索引擎的成败，是商业搜索引擎的关键部分与核心机密，因此成为广大学 者研究的热点之一。 研究搜索引擎网页排序的目的就是从很多搜索结果中将内容相关和权威的网页排 在前面呈现给用户，帮助用户迅速地定位所需要的资源。目前的搜索引擎利用词频和词 位置统计排序技术来解决网页内容与查询的相关性问题，利用p a g e r a n k 和h i t s 等链接分 析排序算法来解决判定网页权威性问题。在大量的网页搜索结果中，如果只采用内容相 关性排序算法，则仍会得到大量的结果并无法保障网页的重要性；如果只采用链接分析 排序算法，则会存在主题漂移等问题并无法保证查询结果的相关性【2 9 】。因此，只有通过 设计实现搜索引擎网页综合排序模型，才能满足用户对查询结果的相关性和权威性的综 合需求。 由于商业搜索引擎的网页排序算法是核心机密，无法得知其中的实现细节，而j a v a 开源代码实现的n u t c h 搜索引擎却为学者研究提供了很好的选择。但是，由于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 值时也存在效率低下的问题。因此，为了使n u t c h 更好地满足搜索引擎的实 际应用要求，在n u t c h q b 设计并实现一种高效的p a g e r a n k 并行算法，然后进一步改进它 的综合排序模型，这样做具有一定的研究意义和较高的实用价值。 1 5 论文的主要工作和组织结构 论文的主要工作如下： 1 、分析了国内外搜索引擎网页排序算法的发展现状，研究基于链接分析排序算法， 重点对经典的p a g e r a n k 算法进行深入研究，熟悉其计算原理与实现方法，分析算法的 缺点与不足。 n u t c h 搜索引擎中网页排序技术的研究 2 、熟悉开源搜索引擎n u t c h 的组成结构，研究其基于m a p r e d u c e 的并行计算模型 以及分布式文件系统h d f s ，并对其基于l u c e n e 的网页综合排序模型进行深入研究， 分析模型中存在的不足。 3 、针对目前n u t c h 搜索引擎中没有实现p a g e r a n k 计算的问题，利用m a p r e d u e e 并行计算机制处理大数据集的优势，在n u t c h 机群系统上设计和实现了基于m a p r e d u e e 的p a g e r a n k 分布式并行算法。实验结果表明：处理的数据量越大，机群中的节点越多， 计算p a g e r a n k 的效率越高；另外，该分布式并行算法具有较好的可扩展性。 4 、针对目前n u t c h 对中文进行单字切分的问题，加入了j e 中文分词器对n u t c h 的 中文分词进行改进。在分析和研究经典p a g e r a n k 算法原理的基础上，通过设置控制站 外与站内链接的比重因子对该算法进行了改进。为了改进n u t c h 基于l u c e n e 的网页综 合排序模型，将改进后的p a g e r a n k 算法因子融入到n u t c h 网页评分计算公式当中。实 验表明，改进后n u t c h 明显提高了查询结果的准确率，改善了中文网页的排序效果。 论文共分为5 章，各章节主要内容如下： 第一章绪论。简述了搜索引擎的分类与基本原理，主要介绍了搜索引擎网页排序 算法的研究现状，引出了论文的研究意义和主要工作。 第二章n u t c h 搜索引擎技术介绍。介绍了l u c e n e 与n u t c h 的关系，并对n u t c h 的 组成与工作流程进行了简单说明，并介绍n u t c h 中的m a p r e d u c e 并行算法思想以及分 布式文件系统h d f s ，最后介绍n u t c h 中的的并行计算机制与机群部署。 第三章n u t c h 中p a g e r a n k 算法的并行实现。介绍p a g e r a n k 的迭代计算原理并通 过简单实验进行验证，然后详细介绍了在n u t c h 中基于m a p r e d u e e 的p a g e r a n k 并行算 法实现过程，通过实验说明该算法有效提高了p a g e r a n k 的计算效率。 第四章n u t c h 中