搜索引擎排序算法的分析与研究硕士学位论文 精品.docx

搜索引擎排序算法的分析与研究硕士学位论文 精品.docx

《搜索引擎排序算法的分析与研究硕士学位论文 精品.docx》由会员分享，可在线阅读，更多相关《搜索引擎排序算法的分析与研究硕士学位论文 精品.docx（73页珍藏版）》请在冰点文库上搜索。

搜索引擎排序算法的分析与研究硕士学位论文精品

学校代码：

10254

密级：

论文编号：

上海海事大学

SHANGHAIMARITIMEUNIVERSITY

硕士学位论文

MASTERDISSERTATION

论文题目：

搜索引擎排序算法的分析与研究

学科专业：

计算机应用技术

作者姓名：

指导教师：

完成日期：

毕业设计（论文）原创性声明和使用授权说明

原创性声明

本人郑重承诺：

所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。

尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。

对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。

作者签名：

　　　　　日　期：

指导教师签名：

　　　　　日　　期：

使用授权说明

本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：

按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。

作者签名：

　　　　　日　期：

学位论文原创性声明

本人郑重声明：

所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。

除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。

对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。

本人完全意识到本声明的法律后果由本人承担。

作者签名：

日期：

年月日

学位论文版权使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。

本人授权　　　　大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

涉密论文按学校规定处理。

作者签名：

日期：

年月日

导师签名：

日期：

年月日

指导教师评阅书

指导教师评价：

一、撰写（设计）过程

1、学生在论文（设计）过程中的治学态度、工作精神

□优□良□中□及格□不及格

2、学生掌握专业知识、技能的扎实程度

□优□良□中□及格□不及格

3、学生综合运用所学知识和专业技能分析和解决问题的能力

□优□良□中□及格□不及格

4、研究方法的科学性；技术线路的可行性；设计方案的合理性

□优□良□中□及格□不及格

5、完成毕业论文（设计）期间的出勤情况

□优□良□中□及格□不及格

二、论文（设计）质量

1、论文（设计）的整体结构是否符合撰写规范？

□优□良□中□及格□不及格

2、是否完成指定的论文（设计）任务（包括装订及附件）？

□优□良□中□及格□不及格

三、论文（设计）水平

1、论文（设计）的理论意义或对解决实际问题的指导意义

□优□良□中□及格□不及格

2、论文的观念是否有新意？

设计是否有创意？

□优□良□中□及格□不及格

3、论文（设计说明书）所体现的整体水平

□优□良□中□及格□不及格

建议成绩：

□优□良□中□及格□不及格

（在所选等级前的□内画“√”）

指导教师：

（签名）单位：

（盖章）

年月日

评阅教师评阅书

评阅教师评价：

一、论文（设计）质量

1、论文（设计）的整体结构是否符合撰写规范？

□优□良□中□及格□不及格

2、是否完成指定的论文（设计）任务（包括装订及附件）？

□优□良□中□及格□不及格

二、论文（设计）水平

1、论文（设计）的理论意义或对解决实际问题的指导意义

□优□良□中□及格□不及格

2、论文的观念是否有新意？

设计是否有创意？

□优□良□中□及格□不及格

3、论文（设计说明书）所体现的整体水平

□优□良□中□及格□不及格

建议成绩：

□优□良□中□及格□不及格

（在所选等级前的□内画“√”）

评阅教师：

（签名）单位：

（盖章）

年月日

教研室（或答辩小组）及教学系意见

教研室（或答辩小组）评价：

一、答辩过程

1、毕业论文（设计）的基本要点和见解的叙述情况

□优□良□中□及格□不及格

2、对答辩问题的反应、理解、表达情况

□优□良□中□及格□不及格

3、学生答辩过程中的精神状态

□优□良□中□及格□不及格

二、论文（设计）质量

1、论文（设计）的整体结构是否符合撰写规范？

□优□良□中□及格□不及格

2、是否完成指定的论文（设计）任务（包括装订及附件）？

□优□良□中□及格□不及格

三、论文（设计）水平

1、论文（设计）的理论意义或对解决实际问题的指导意义

□优□良□中□及格□不及格

2、论文的观念是否有新意？

设计是否有创意？

□优□良□中□及格□不及格

3、论文（设计说明书）所体现的整体水平

□优□良□中□及格□不及格

评定成绩：

□优□良□中□及格□不及格

（在所选等级前的□内画“√”）

教研室主任（或答辩小组组长）：

（签名）

年月日

教学系意见：

系主任：

（签名）

年月日

论文独创性声明

本论文是我个人在导师指导下进行的研究工作及取得的研究成果。

论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机构已经发表或撰写过的研究成果。

其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明并表示了谢意。

作者签名：

日期：

论文使用授权声明

本人同意上海海事大学有关保留、使用学位论文的规定，即：

学校有权保留送交论文复印件，允许论文被查阅和借阅；学校可以上网公布论文的全部或部分内容，也可以采用影印、缩印或者其他复印手段保留论文。

保密的论文在解密后遵守此规定。

作者签名：

导师签名：

日期：

摘要

随着现代科技的进步，互联网得到了飞速的发展，逐渐成为人们日常学习、生活、工作中最重要的获取知识和信息的工具。

进入21世纪以来，网络信息成几何级数的增长，快速精确查找需要的信息变得越来越难，这使得发展搜索引擎技术成为一种必要，它能帮助人们快速有效地获取信息。

本文介绍了搜索引擎的概念及其发展历史、搜索引擎的分类、结构与工作原理、搜索引擎的评价标准、常用的中英文搜索引擎，以及搜索引擎排序算法作了简单的介绍。

如何使广大网民快速找到所要的知识和信息资源，成为搜索引擎技术研究的重点。

本文针对一些已有算法：

PageRank算法、HillTop算法、DirectHit算法等存在的不足，即PageRank算法平均分配权威值；Hilltop中利用“专家页面”不合理，容易产生Spam；DirectHit算法处理重复点击、与新页面不理想的问题，提出改进算法的思路。

针对PageRank算法权威值的计算，引入非均衡分配的思想，改进PageRank算法平均分配权威值的问题；引入社区发现技术来改进算法，该算法利用社区作为“专家页面”，不仅可以改善Hilltop算法找“专家页面”不合理的现象，而且对于DirectHit算法处理新页面不理想、用户重复点击等问题也能起到一定的效果。

关键词：

搜索引擎，排序算法，社区发现技术，PageRank，HillTop，DirectHit

ABSTRACT

Withtheprogressoftheinformationtechnology,Internetdevelopsfastandbecomesanimportantmeansofobtainedtheknowledgeandinformationwhichmaybeusedinpeople’sstudy,dailylifeandwork.Sinceweenterinto21thcentury,theinformationofinternetincreasedatageometricprogression.Queryinginformationbecomemoreandmoredifficult,itbecomesaneedofdevelopingthesearchenginetechnologies.Itcanhelppeopleacquireinformationquicklyandeffectively.

Thispaperintroducetheconceptionandthedevelopinghistory,classify,structureandoperatingprinciplesofthesearchengine.Atthesametime,itdescribesthecommonChineseandEnglish,theevaluationstandardofthesearchengineandintroducesthecommonalgorithmstepbystep.

Howtomakethesearchingbequickisthemainpointofthesearchengineresearching.Thispaperaccordingtosomeexistingalgorithmandputsforwardimprovingwaystosolvetheshortcomingsoftheexistingalgorithms.SuchasthePageRankalgorithm’sPRvalueswhichisequaldivision,HillTopalgorithmeasilygeneratethespambecauseofutilizingtheexpertpagesillegitimacyandnon-idealprocessingmethodsforrepeatspotbowlingoftheDirectHitalgorithm.WeinducttheunbalanceideaforPageRankalgorithm’sproblemsofnotequaldivision，andthediscoverytechnologyofcommunitytosettlethestandingproblemsofHillTopalgorithmutilizetheexpertpagesillegitimacyandnon-idealprocessingmethodsforrepeatspotbowlingoftheDirectHitalgorithm.Thisalgorithmcouldbehelpforreducingtheadverseeffectscausedbythesealgorithms.

Atlast,wesummarizetheworkofthispaperandpredictthefuturedevelopmentofthesearchenginealgorithm.

MaozhongFu（ComputerApplication）

DirectedbyProf.MaotingGao

Keyword:

SearchEngine,sortingalgorithm,thetechnologyofthecommunitydiscovery,PageRank,HillTop,DirectHit

第一章绪论

本章首先介绍了本课题的研究背景和意义，其次论述了搜索引擎的发展及其未来，以及搜索引擎排序算法发展过程以及存在的问题，最后对本文的工作安排和论文结构做了详细的说明。

1.1研究背景和意义

随着信息技术的进步，互联网作为信息的载体得到了飞速的发展，成为人们学习、工作、生活中获取知识和信息的主要来源。

根据美国因特网监测公司“网器（Netcraft）”28日宣布[1]，截止2月底，全球互联网网站数量超过1.6亿，较一个月前增加了450万，达162662053。

据国外权威通讯社报道，网站数量在2005年增加了1700万，在2006年增加了2740万。

美国、德国、中国、韩国和日本的网站发展速度最快。

过去两年间，博客及网上购物的兴起和创建网站操作的简单化等因素结合在一起，使得网站数量猛增。

现有搜索引擎给人们带来了很多方便的同时，也逐渐暴露了自身的一些问题，这些弊端主要表现在以下方面：

1）网络信息量过于庞大，网络错综复杂，没有特定的网络模型，描述不便。

2）检索结果信息过多，有用信息不全。

3）检索结果缺乏个性化，不能满足不同用户的需求。

4）不同国家的搜索引擎差别较大，对不同语言的适应性较差。

5）多媒体信息检索还不完善。

6）网页的更新速度远远快于索引数据库的更新。

7）垃圾网页过多，许多虚假广告、不健康信息、错误信息充斥互联网。

8）广告的比例较大，干扰正常的浏览。

如何快速准确的查找用户所需的信息成为互联网急需解决的问题，这就为搜索引擎技术的发展提供了土壤。

现有的排序算法有很多，如PageRank算法[2]、HillTop算法[3]、DirectHit算法[4]等，但是没有一个是完美无缺的。

本文在介绍搜索引擎及其相关技术的基础上，结合已有的排序算法，提出了自己的解决思路，以改善搜索引擎排序算法的质量，使用户能够快速准确的找到所需信息，同时也为以后排序算法的研究提供一个有价值的参考。

本文是在上海市教委科研项目“基于统计学习的数据挖掘技术研究”（项目编号：

06FZ007）的支持下，开展搜索引擎排序算法的分析与研究。

1.2搜索引擎的发展历史

搜索引擎是用于帮助互联网用户查询信息的搜索工具，它以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导航的作用。

下面将介绍搜索引擎的发展历程。

1.2.1搜索引擎的起源

简单地说，搜索引擎起源于传统的信息全文检索理论[5]，即计算机程序通过扫描每一篇文章中的每一个词，建立以词为单位的排序文件，检索程序根据检索词在每一篇文章中出现的频率和每一个检索词在一篇文章中出现的概率，对包含这些检索词的文章进行排序，最后输出排序的结果。

在早期的时候，互联网上面的搜索引擎和今天人们常用的搜索引擎有所不同，早期的搜索引擎更像是如今很多中文的“ICP（InternetContentProvider）”网站，把因特网中的资源服务器的地址收集起来，由其提供的资源类型的不同而分成不同的目录，再一层层地进行分类。

人们要找自己想要的信息可按他们的分类一层层进入，就能最后到达目的地，找到自己想要的信息。

这其实是最原始的方式，只适用于因特网信息并不多的时候，因为如果信息一旦多起来，查找的时候所花费的时间就很长了。

1990年，互联网还没有得到全面的推广，但是，通过网络传输文件已经比较普遍，真正意义上的搜索引擎是1994年创立的Lycos（Mauldin将JohnLeavitt的Spider程序[6]接入其索引程序中产生的。

互联网搜索引擎除了需要有全文检索系统之外，还要有所谓的“蜘蛛”（Spider）系统[7]，即能够从互联网上自动收集网页的数据搜集系统。

“蜘蛛”系统是JohnLeavitt开发的，并且由MichaelMauldin将这个系统融合到了Lycos搜索引擎里面去，它能够将搜集所得的网页内容交给索引和检索系统处理，就形成了现在常见的互联网搜索引擎系统。

当然，一个完整的搜索引擎系统还需要有一个检索结果的页面生成系统，也就是要把检索结果高效地组装成万维网页面。

概括起来说搜索引擎是为查询而生的，用户需求的不断更新、发展是搜索引擎技术不断进步的动力。

1.2.2搜索引擎的现状

经过了多年的发展，现在的搜索引擎功能越来越强大，提供的服务也越来越全面，当你登录某一个网站，在互联网上搜索各个网站的某一类内容，比如，输入“猪流感”，希望得到最新、最全面的信息，你需要等待多长时间？

几年前，人们希望十几秒，最多30秒钟就能得到结果，而现在的期望值是1~2秒，也就是说，伴随点击鼠标的“咔哒”一声，显示屏的页面已经变了，排在最前面的十几、二十条信息的标题已经出现在你的面前。

除了速度的不断提升之外，搜索引擎目前的特点可概括为以下几个方面：

1）目录型和检索型的搜索引擎相互结合[8]

由于目录型和检索型的搜索引擎有各自的优点和缺点，目前它们谁也无法完全取代谁，于是很多搜索站点都同时提供这两种类型的服务。

例如Yahoo是目录型搜索引擎的代表，但同时它也提供基于关键词的检索服务；而Infoseek则主要是一个检索型的搜索引擎，但它同时也建立了一个由人工编辑的小型目录。

2）多样化和个性化的服务

绝大多数搜索引擎现在都提供多样化的服务，以吸引更多的用户，商业搜索引擎尤其注重这一点。

以Sohu为例，用户可以从它的首页上查看新闻、理财信息、公共交通、浏览黄页，可以进行网上购物、交易、交友，或者使用免费E-Mail和网上聊天等服务。

近期许多搜索引擎已开始提供个性化的服务，例如Yahoo的“MyYahoo”、Infoseek[9]的“Personalizedstartpage”、Lycos的“MyLycos”等，它们允许用户为自己定制起始页面，并选择感兴趣的内容和经常使用的服务放在该页面上。

3）强大的查询功能

与最早的搜索引擎相比，现在的搜索引攀在查询功能方面己经有了很大的改进。

除了简单的AND、OR和NOT逻辑外，不少搜索引擎还支持相似查询，例如AltaVista、Northernlight、Lycos等支持短语查询，AltaVista的高级搜索功能支持NEAR逻辑等。

域搜索也是一项很实用的功能，它允许用户把查询范围限制在网页的某个域中，例如标题、URL、图像标记或链接等，AltaVista、Northernlight、Infoseek和XX等搜索引擎都支持对网页的不同域进行搜索。

但是在搜索引擎快速发展的同时，其自身也存在着一些问题：

1）提供的查询方式相当有限，与用户的交互性差，信息检索质量不高。

2）仅支持单个关键词或者一组关键词及其逻辑运算符组成的查询，而并不支持自然语言搜索或语义搜索。

3）不能利用历史信息进行搜索。

用户的每次搜索都是从头开始，而不是从原有的查询结果中作进一步选择。

4）呈现方式单一、呆板。

多数搜索引擎只返回一个长长的搜索结果列表，其中可能有数以万计的包含关键词的网页，但这些网页是否以及在多大程度上与用户的搜索意图相关，则不得而知。

1.2.3搜索引擎的未来

互联网信息的快速发展促进了搜索引擎技术的不断进步，呈现出一个喜人的应用前景，未来的搜索引擎不仅要满足用户简单的查询需求，更要能动态的适应信息和用户不断改变所带来的更高的要求，搜索引擎以后的发展将致力于以下几个方面：

1）十分注意提高信息查询结果的精度，提高检索的有效性

用户在搜索引擎上进行信息查询时，并不十分关注返回结果的多少，而是看结果是否和自己的需求吻合。

对于一个查询，传统的搜索引擎动辄返回几十万、几百万篇文档，用户不得不在结果中筛选。

解决查询结果过多的现象目前出现了几种方法：

一是通过各种方法获得用户没有在查询语句中表达出来的真正用途，包括使用智能代理跟踪用户检索行为，分析用户模型，使用相关度反馈机制，使用户告诉搜索引擎哪些文档和自己的需求相关（及其相关的程度），哪些不相关，通过多次交互逐步求精；二是用正文分类（TextCategorization）技术将结果分类，使用可视化技术显示分类结构，用户可以只浏览自己感兴趣的类别；三是进行站点类聚或内容类聚，减少信息的总量。

2）重视交叉语言检索的研究和开发

交叉语言信息检索是指用户用母语提交查询，搜索引擎在多种语言的数据库中进行信息检索，返回能够回答用户问题的所有语言的文档。

如果再加上机器翻译，返回结果可以用母语显示。

该技术目前还处于初步研究阶段，主要的困难在于语言之间在表达方式和语义对应上的不确定性。

但对于经济全球化、互联网跨越国界的今天，无疑具有很重要的意义。

3）自然语言理解技术　　

自然语言理解是计算机科学中的一个引人入胜的、富有挑战性的课题。

从计算机科学特别是从人工智能的观点看，自然语言理解的任务是建立一种计算机模型，这种计算机模型能够像人那样理解、分析并回答自然语言。

以自然语言理解技术为基础的新一代搜索引擎，人们称之为智能搜索引擎。

由于它将信息检索从目前基于关键词层面提高到基于知识（或概念）层面，对知识有一定的理解与处理能力，能够实现分词技术、同义词技术、概念搜索、短语识别以及机器翻译技术等。

因而这种搜索引擎具有信息服务的智能化、人性化特征，允许网民采用自然语言进行信息的检索，为他们提供更方便、更确切的搜索服务。

4）个性化的搜索[10]

一种搜索引擎是否具有智能，是否能够满足用户的需求，要看它是否可以分析用户的个人特点并制定相应的“对策”，给出最合适的排序。

个性化搜索引擎很强大，对抓取和用户的搜索行为进行分析，通过他们的算法，可以实现不同的人在搜索同样关键词的时候，根据不同人的各种属性（地域、年龄、性别、爱好、职业、历史搜索等等）分别得到最适合他们的结果；可以根据用户各自的差异和特点，提供最适合该用户的网页呈现，划分具有共同爱好、特性的用户群体。

浏览器可以在客户端自动获取分析用户各自感兴趣的信息，实现个性化的搜索。

如现在流行的Google为用户提供个性搜索（IndividualSearch）服务，用户在使用高级搜索的时候可以设置检索词所在的位置，如正文、标题、仅在URL、或者文本等等，还可以通过逻辑关系限制检索，如可以含有、一定含有、一定不含有等等，以及对于检索的时间范围、地域范围做出限制。

Baidu也提供了个性搜索功能，除Google所提供的功能外，用户还可以设置检索结果的性质，可以设置只返回媒体类型，或者某些特定领域的页面，还可以选择进行检索的数据库，以及结果的显示排列方式等等。

然而这种定制服务的方式，还是给用户增添了许多麻烦，它要求用户须按照指定的操作来进行搜索才能获得更加满意的结果，然而即便是这样也无法实现真正的个性化服务，同样的操作下，仍然会给出相同结果集。

5）P2P对等网络　　

P2P是peer-to-peer的缩写，意为对等网络。

其在加强网络上人的交流、文件交换、分布计算等方面大有前途。

长久以