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

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

1、学校代码：10254 密级： 论文编号： 上海海事大学上海海事大学 SHANGHAI MARITIME UNIVERSITY 硕士学位论文硕士学位论文 MASTER DISSERTATION 论论文文题题目：目：搜索引擎排序算法的分析与研究搜索引擎排序算法的分析与研究 学科学科专业专业： ：计计算机算机应应用技用技术术 作者姓名：作者姓名： 指指导导教教师师： ： 完成日期完成日期： ： 毕业设计（论文）原创性声明和使用授权说明毕业设计（论文）原创性声明和使用授权说明 原创性声明原创性声明 本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师 的指导下进行的研究工作及取得的成果。尽我所知

2、，除文中特别加以 标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究 成果，也不包含我为获得 及其它教育机构的学位或学历而 使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均 已在文中作了明确的说明并表示了谢意。 作 者 签 名： 日 期： 指导教师签名： 日 期： 使用授权说明使用授权说明 本人完全了解 大学关于收集、保存、使用毕业设计（论文） 的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本； 学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与 阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论 文；在不以赢利为目的前提下，学校可以公

3、布论文的部分或全部内容。 作者签名： 日 期： 学位学位论论文原文原创创性声明性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律后果由本人承担。 作者签名： 日期： 年 月 日 学位学位论论文版文版权权使用授使用授权书权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权 大

4、学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存和汇编本学位论文。 涉密论文按学校规定处理。 作者签名：日期： 年 月 日 导师签名： 日期： 年 月 日 指导教师评阅书指导教师评阅书 指导教师评价：指导教师评价： 一、撰写（设计）过程 1、学生在论文（设计）过程中的治学态度、工作精神 优 良 中 及格 不及格 2、学生掌握专业知识、技能的扎实程度 优 良 中 及格 不及格 3、学生综合运用所学知识和专业技能分析和解决问题的能力 优 良 中 及格 不及格 4、研究方法的科学性；技术线路的可行性；设计方案的合理性 优 良 中 及格 不及格 5、

5、完成毕业论文（设计）期间的出勤情况 优 良 中 及格 不及格 二、论文（设计）质量 1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格 2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格 三、论文（设计）水平 1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格 2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格 3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格 建议成绩：建议成绩： 优优 良良 中中 及格及格 不及格不及格 （在所选等级前的内画“”） 指导教师：指导教师： （签名）

6、单位：单位： （盖章） 年年 月月 日日 评阅教师评阅书评阅教师评阅书 评阅教师评价：评阅教师评价： 一、一、论论文（文（设计设计） ）质质量量 1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格 2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格 二、二、论论文（文（设计设计）水平）水平 1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格 2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格 3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格 建议成绩：建议成绩： 优优 良良 中中 及

7、格及格 不及格不及格 （在所选等级前的内画“”） 评阅教师：评阅教师： （签名） 单位：单位： （盖章） 年年 月月 日日 教研室（或答辩小组）及教学系意见教研室（或答辩小组）及教学系意见 教研室（或答辩小组）评价：教研室（或答辩小组）评价： 一、答一、答辩过辩过程程 1、毕业论文（设计）的基本要点和见解的叙述情况 优 良 中 及格 不及格 2、对答辩问题的反应、理解、表达情况 优 良 中 及格 不及格 3、学生答辩过程中的精神状态 优 良 中 及格 不及格 二、二、论论文（文（设计设计） ）质质量量 1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格 2、是否完成指定的论

8、文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格 三、三、论论文（文（设计设计）水平）水平 1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格 2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格 3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格 评定成绩：评定成绩： 优优 良良 中中 及格及格 不及格不及格 （在所选等级前的内画“”） 教研室主任（或答辩小组组长）：教研室主任（或答辩小组组长）： （签名） 年年 月月 日日 教学系意见：教学系意见： 系主任：系主任： （签名） 年年 月月 日日 论文独创性声明论文独创性声

9、明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。 论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机构已 经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。 作者签名： 日期： 论文使用授权声明论文使用授权声明 本人同意上海海事大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文复印件，允许论文被查阅和借阅；学校可以上网公布 论文的全部或部分内容，也可以采用影印、缩印或者其他复印手段保留 论文。保密的论文在解密后遵守此规定。 作者签名： 导师签名： 日期： 摘 要 I 摘 要 随着现代科技的进步，互联网得到了飞速

10、的发展，逐渐成为人们日常学习、 生活、工作中最重要的获取知识和信息的工具。进入 21 世纪以来，网络信息成 几何级数的增长，快速精确查找需要的信息变得越来越难，这使得发展搜索引 擎技术成为一种必要，它能帮助人们快速有效地获取信息。 本文介绍了搜索引擎的概念及其发展历史、搜索引擎的分类、结构与工作 原理、搜索引擎的评价标准、常用的中英文搜索引擎，以及搜索引擎排序算法 作了简单的介绍。 如何使广大网民快速找到所要的知识和信息资源，成为搜索引擎技术研究 的重点。本文针对一些已有算法：PageRank 算法、HillTop 算法、Direct Hit 算 法等存在的不足，即 PageRank 算法平均

11、分配权威值；Hilltop 中利用“专家页 面”不合理，容易产生 Spam；Direct Hit 算法处理重复点击、与新页面不理想 的问题，提出改进算法的思路。针对 PageRank 算法权威值的计算，引入非均衡 分配的思想，改进 PageRank 算法平均分配权威值的问题；引入社区发现技术来 改进算法，该算法利用社区作为“专家页面” ，不仅可以改善 Hilltop 算法找 “专家页面”不合理的现象，而且对于 Direct Hit 算法处理新页面不理想、用户 重复点击等问题也能起到一定的效果。 关键词：搜索引擎，排序算法，社区发现技术，PageRank，HillTop，Direct Hit A

12、BSTRACT II ABSTRACT With the progress of the information technology, Internet develops fast and becomes an important means of obtained the knowledge and information which may be used in peoples study, daily life and work. Since we enter into 21th century, the information of internet increased at a g

13、eometric progression. Querying information become more and more difficult, it becomes a need of developing the search engine technologies. It can help people acquire information quickly and effectively. This paper introduce the conception and the developing history, classify, structure and operating

14、 principles of the search engine. At the same time, it describes the common Chinese and English, the evaluation standard of the search engine and introduces the common algorithm step by step. How to make the searching be quick is the main point of the search engine researching. This paper according

15、to some existing algorithm and puts forward improving ways to solve the shortcomings of the existing algorithms. Such as the PageRank algorithms PR values which is equal division, HillTop algorithm easily generate the spam because of utilizing the expert pages illegitimacy and non-ideal processing m

16、ethods for repeat spot bowling of the Direct Hit algorithm. We induct the unbalance idea for PageRank algorithms problems of not equal division， and the discovery technology of community to settle the standing problems of HillTop algorithm utilize the expert pages illegitimacy and non-ideal processi

17、ng methods for repeat spot bowling of the Direct Hit algorithm. This algorithm could be help for reducing the adverse effects caused by these algorithms. At last, we summarize the work of this paper and predict the future development of the search engine algorithm. Maozhong Fu (Computer Application)

18、 Directed by Prof. Maoting Gao ABSTRACT III Keyword: Search Engine, sorting algorithm, the technology of the community discovery, PageRank, HillTop, Direct Hit 目 录 IV 目 录 第一章第一章 绪论绪论 .1 1.1 研究背景和意义.1 1.2 搜索引擎的发展历史.2 1.2.1 搜索引擎的起源2 1.2.2 搜索引擎的现状3 1.2.3 搜索引擎的未来4 1.3 搜索引擎排序算法的演进.6 1.3.1 搜索引擎排序算法的起源和现状6

19、 1.3.2 搜索引擎排序算法存在的问题.7 1.4 本文的组织框架及所做工作.7 第二章第二章 搜索引擎概述搜索引擎概述 .9 2.1 搜索引擎的分类.9 2.1.1 按所覆盖内容.9 2.1.2 按是否有人参与 .9 2.1.3 按检索层次.10 2.2 搜索引擎的结构及工作原理.12 2.2.1 搜索引擎组成结构.12 2.2.2 搜索引擎工作原理.14 2.3 常用搜索引擎.15 2.3.1 常用中文搜索引擎.15 2.3.2 常用英文搜索引擎.17 2.4 搜索引擎的评价标准.19 2.5 本章小节.20 第三章第三章 搜索引擎常用排序算法及相关技术搜索引擎常用排序算法及相关技术 .

20、21 3.1 搜索引擎常用的排序算法.21 3.1.1 词频位置加权排序算法.21 3.1.2 PageRank 算法 22 3.1.3 Direct hit 算法 .24 3.1.4 Bayesian 算法25 3.1.5 Web Query 算法26 3.1.6 Hilltop 算法.26 3.1.7 HITS 算法.27 3.1.8 竞价排名.27 3.2 搜索引擎的相关技术.28 3.2.1 SEO 技术28 3.2.2 Spam 作弊技术31 3.3 本章小结.34 第四章第四章 利用社区发现技术改进排序算法利用社区发现技术改进排序算法 .35 4.1 PAGERANK算法及其改进分

21、析35 目 录 V 4.1.1 PageRank 算法优缺点分析 .35 4.1.2 PageRank 算法改进思路 .36 4.2 另两种常用算法及其改进思路.38 4.2.1 HillTop 算法38 4.2.2 Direct Hit 算法40 4.3 利用社区发现技术改进排序算法.41 4.3.1 什么是社区发现技术41 4.3.2 利用社区发现技术改进排序算法的过程42 4.3.3 算法总结44 4.4 实验过程.45 4.3.1 实验环境45 4.3.2 过程描述46 4.3.3 实验结果46 4.3.4 实验评价48 4.5 结果分析50 4.6 本章小结50 第五章第五章 工作总

22、结与展望工作总结与展望 .51 5.1 工作总结.51 5.2 展望.51 致致 谢谢 .53 参考文献参考文献 .54 攻读硕士期间发表论文和参加科研情况攻读硕士期间发表论文和参加科研情况 .58 一、发表的论文.58 二、参加的科研项目.58 绪 论 1 第一章第一章 绪论绪论 本章首先介绍了本课题的研究背景和意义，其次论述了搜索引擎的发展及 其未来，以及搜索引擎排序算法发展过程以及存在的问题，最后对本文的工作 安排和论文结构做了详细的说明。 1.1 研究背景和意义 随着信息技术的进步，互联网作为信息的载体得到了飞速的发展，成为人 们学习、工作、生活中获取知识和信息的主要来源。根据美国因特

23、网监测公司 “网器 ( Netcraft ) ” 28 日宣布1，截止 2 月底，全球互联网网站数量超过 1.6 亿，较一个月前增加了 450 万，达 162662053。据国外权威通讯社报道，网站 数量在 2005 年增加了 1700 万，在 2006 年增加了 2740 万。美国、德国、中国、 韩国和日本的网站发展速度最快。过去两年间，博客及网上购物的兴起和创建 网站操作的简单化等因素结合在一起，使得网站数量猛增。 现有搜索引擎给人们带来了很多方便的同时，也逐渐暴露了自身的一些问 题，这些弊端主要表现在以下方面： 1) 网络信息量过于庞大，网络错综复杂，没有特定的网络模型，描述不便。 2)

24、 检索结果信息过多，有用信息不全。 3) 检索结果缺乏个性化，不能满足不同用户的需求。 4) 不同国家的搜索引擎差别较大，对不同语言的适应性较差。 5) 多媒体信息检索还不完善。 6) 网页的更新速度远远快于索引数据库的更新。 7) 垃圾网页过多，许多虚假广告、不健康信息、错误信息充斥互联网。 8) 广告的比例较大，干扰正常的浏览。 如何快速准确的查找用户所需的信息成为互联网急需解决的问题，这就为 搜索引擎技术的发展提供了土壤。现有的排序算法有很多，如 PageRank 算法2、 HillTop 算法3、Direct Hit 算法4等，但是没有一个是完美无缺的。本文在介绍 搜索引擎及其相关技术

25、的基础上，结合已有的排序算法，提出了自己的解决思 路，以改善搜索引擎排序算法的质量，使用户能够快速准确的找到所需信息， 同时也为以后排序算法的研究提供一个有价值的参考。 绪 论 2 本文是在上海市教委科研项目“基于统计学习的数据挖掘技术研究” （项目 编号：06FZ007）的支持下，开展搜索引擎排序算法的分析与研究。 1.2 搜索引擎的发展历史 搜索引擎是用于帮助互联网用户查询信息的搜索工具，它以一定的策略在 互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提 供检索服务，从而起到信息导航的作用。下面将介绍搜索引擎的发展历程。 1.2.1 搜索引擎的起源 简单地说，搜索引擎起

26、源于传统的信息全文检索理论5，即计算机程序通 过扫描每一篇文章中的每一个词，建立以词为单位的排序文件，检索程序根据 检索词在每一篇文章中出现的频率和每一个检索词在一篇文章中出现的概率， 对包含这些检索词的文章进行排序，最后输出排序的结果。在早期的时候，互 联网上面的搜索引擎和今天人们常用的搜索引擎有所不同，早期的搜索引擎更 像是如今很多中文的“ICP(Internet Content Provider)”网站，把因特网中的资源 服务器的地址收集起来，由其提供的资源类型的不同而分成不同的目录，再一 层层地进行分类。人们要找自己想要的信息可按他们的分类一层层进入，就能 最后到达目的地，找到自己想要

27、的信息。这其实是最原始的方式，只适用于因 特网信息并不多的时候，因为如果信息一旦多起来，查找的时候所花费的时间 就很长了。 1990 年，互联网还没有得到全面的推广，但是，通过网络传输文件已经比 较普遍，真正意义上的搜索引擎是 1994 年创立的 Lycos(http:/ 他由 Michael Mauldin 将 John Leavitt 的 Spider 程序6接入其索引程序中产生的。 互联网搜索引擎除了需要有全文检索系统之外，还要有所谓的“蜘蛛” (Spider) 系统7，即能够从互联网上自动收集网页的数据搜集系统。“蜘蛛”系 统是 John Leavitt 开发的，并且由 Michael

28、 Mauldin 将这个系统融合到了 Lycos 搜索引擎里面去，它能够将搜集所得的网页内容交给索引和检索系统处理，就 形成了现在常见的互联网搜索引擎系统。当然，一个完整的搜索引擎系统还需 要有一个检索结果的页面生成系统，也就是要把检索结果高效地组装成万维网 页面。 概括起来说搜索引擎是为查询而生的，用户需求的不断更新、发展是搜索 绪 论 3 引擎技术不断进步的动力。 1.2.2 搜索引擎的现状 经过了多年的发展，现在的搜索引擎功能越来越强大，提供的服务也越来 越全面，当你登录某一个网站，在互联网上搜索各个网站的某一类内容，比如， 输入“猪流感”，希望得到最新、最全面的信息，你需要等待多长时间

29、？几年前， 人们希望十几秒，最多 30 秒钟就能得到结果，而现在的期望值是 12 秒，也就 是说，伴随点击鼠标的“咔哒”一声，显示屏的页面已经变了，排在最前面的 十几、二十条信息的标题已经出现在你的面前。除了速度的不断提升之外，搜 索引擎目前的特点可概括为以下几个方面： 1) 目录型和检索型的搜索引擎相互结合8 由于目录型和检索型的搜索引擎有各自的优点和缺点，目前它们谁也无法 完全取代谁，于是很多搜索站点都同时提供这两种类型的服务。例如 Yahoo 是 目录型搜索引擎的代表，但同时它也提供基于关键词的检索服务；而 Infoseek 则主要是一个检索型的搜索引擎，但它同时也建立了一个由人工编辑的

30、小型目 录。 2) 多样化和个性化的服务 绝大多数搜索引擎现在都提供多样化的服务，以吸引更多的用户，商业搜 索引擎尤其注重这一点。以 Sohu 为例，用户可以从它的首页上查看新闻、理财 信息、公共交通、浏览黄页，可以进行网上购物、交易、交友，或者使用免费 E-Mail 和网上聊天等服务。近期许多搜索引擎已开始提供个性化的服务，例如 Yahoo 的“My Yahoo”、Infoseek9的“Personalized start page”、Lycos 的 “My Lycos”等，它们允许用户为自己定制起始页面，并选择感兴趣的内容和 经常使用的服务放在该页面上。 3) 强大的查询功能 与最早的搜索

31、引擎相比，现在的搜索引攀在查询功能方面己经有了很大的 改进。除了简单的 AND、OR 和 NOT 逻辑外，不少搜索引擎还支持相似查询， 例如 AltaVista、Northern light、Lycos 等支持短语查询，AltaVista 的高级搜索功 能支持 NEAR 逻辑等。域搜索也是一项很实用的功能，它允许用户把查询范围 限制在网页的某个域中，例如标题、URL、图像标记或链接等， AltaVista、Northern light、Infoseek 和百度等搜索引擎都支持对网页的不同域进 行搜索。 绪 论 4 但是在搜索引擎快速发展的同时，其自身也存在着一些问题： 1) 提供的查询方式相当

32、有限，与用户的交互性差，信息检索质量不高。 2) 仅支持单个关键词或者一组关键词及其逻辑运算符组成的查询，而并不 支持自然语言搜索或语义搜索。 3) 不能利用历史信息进行搜索。用户的每次搜索都是从头开始，而不是从 原有的查询结果中作进一步选择。 4) 呈现方式单一、呆板。多数搜索引擎只返回一个长长的搜索结果列表， 其中可能有数以万计的包含关键词的网页，但这些网页是否以及在多大程度上 与用户的搜索意图相关，则不得而知。 1.2.3 搜索引擎的未来 互联网信息的快速发展促进了搜索引擎技术的不断进步，呈现出一个喜人 的应用前景，未来的搜索引擎不仅要满足用户简单的查询需求，更要能动态的 适应信息和用户

33、不断改变所带来的更高的要求，搜索引擎以后的发展将致力于 以下几个方面： 1) 十分注意提高信息查询结果的精度，提高检索的有效性 用户在搜索引擎上进行信息查询时，并不十分关注返回结果的多少，而是 看结果是否和自己的需求吻合。对于一个查询，传统的搜索引擎动辄返回几十 万、几百万篇文档，用户不得不在结果中筛选。解决查询结果过多的现象目前 出现了几种方法：一是通过各种方法获得用户没有在查询语句中表达出来的真 正用途，包括使用智能代理跟踪用户检索行为，分析用户模型，使用相关度反 馈机制，使用户告诉搜索引擎哪些文档和自己的需求相关(及其相关的程度)， 哪些不相关，通过多次交互逐步求精；二是用正文分类(Te

34、xt Categorization)技 术将结果分类，使用可视化技术显示分类结构，用户可以只浏览自己感兴趣的 类别；三是进行站点类聚或内容类聚，减少信息的总量。 2) 重视交叉语言检索的研究和开发 交叉语言信息检索是指用户用母语提交查询，搜索引擎在多种语言的数据 库中进行信息检索，返回能够回答用户问题的所有语言的文档。如果再加上机 器翻译，返回结果可以用母语显示。该技术目前还处于初步研究阶段，主要的 困难在于语言之间在表达方式和语义对应上的不确定性。但对于经济全球化、 互联网跨越国界的今天，无疑具有很重要的意义。 3) 自然语言理解技术 绪 论 5 自然语言理解是计算机科学中的一个引人入胜的、

35、富有挑战性的课题。从 计算机科学特别是从人工智能的观点看，自然语言理解的任务是建立一种计算 机模型，这种计算机模型能够像人那样理解、分析并回答自然语言。以自然语 言理解技术为基础的新一代搜索引擎，人们称之为智能搜索引擎。由于它将信 息检索从目前基于关键词层面提高到基于知识(或概念)层面，对知识有一定的 理解与处理能力，能够实现分词技术、同义词技术、概念搜索、短语识别以及 机器翻译技术等。因而这种搜索引擎具有信息服务的智能化、人性化特征，允 许网民采用自然语言进行信息的检索，为他们提供更方便、更确切的搜索服务。 4) 个性化的搜索10 一种搜索引擎是否具有智能，是否能够满足用户的需求，要看它是否

36、可以 分析用户的个人特点并制定相应的“对策”，给出最合适的排序。个性化搜索 引擎很强大，对抓取和用户的搜索行为进行分析，通过他们的算法，可以实现 不同的人在搜索同样关键词的时候，根据不同人的各种属性（地域、年龄、性 别、爱好、职业、历史搜索等等）分别得到最适合他们的结果；可以根据用户 各自的差异和特点，提供最适合该用户的网页呈现，划分具有共同爱好、特性 的用户群体。浏览器可以在客户端自动获取分析用户各自感兴趣的信息，实现 个性化的搜索。 如现在流行的Google为用户提供个性搜索(Individual Search)服务，用户在使 用高级搜索的时候可以设置检索词所在的位置，如正文、标题、仅在U

37、RL、或 者文本等等，还可以通过逻辑关系限制检索，如可以含有、一定含有、一定不 含有等等，以及对于检索的时间范围、地域范围做出限制。 Baidu也提供了个性搜索功能，除Google所提供的功能外，用户还可以设置 检索结果的性质，可以设置只返回媒体类型，或者某些特定领域的页面，还可 以选择进行检索的数据库，以及结果的显示排列方式等等。然而这种定制服务 的方式，还是给用户增添了许多麻烦，它要求用户须按照指定的操作来进行搜 索才能获得更加满意的结果，然而即便是这样也无法实现真正的个性化服务， 同样的操作下，仍然会给出相同结果集。 5) P2P对等网络 P2P是peer-to-peer的缩写，意为对等

38、网络。其在加强网络上人的交流、文 件交换、分布计算等方面大有前途。长久以来，人们习惯的互联网是以服务器 为中心，人们向服务器发送请求，然后浏览服务器回应的信息。而P2P所包含 的技术就是使联网电脑能够进行数据交换，但数据是存储在每台电脑里，而不 绪 论 6 是存储在既昂贵又容易受到攻击的服务器里。网络成员可以在网络数据库里自 由搜索、更新、回答和传送数据。所有人都共享了他们认为最有价值的东西， 这将使互联网上信息的价值得到极大的提升。 1.3 搜索引擎排序算法的演进过程 1.3.1 搜索引擎排序算法的起源和现状 从搜索引擎的发展历史可以看出其搜索结果是由一个从无序到有序，再到 按用户需要排序的

39、过程。早期的搜索引擎只是简单地从数据库中取得数据，然 后按照数据被检索出的自然顺序返回给用户。之后的搜索引擎应用了关键词的 相关性，对于用户提交的关键词，如果它出现的位置越重要，在文档中的出现 频率越高，则认为此网页与检索词的相关性越高，越能满足用户的需求。这些 基本上是沿用了图书情报界的研究成果。而现在的搜索引擎大部分都用到了链 接分析技术，它是应用了文献引文索引机制的思想，即某个人的论文被别人引 用的次数越多、引用它的论文质量越高，那么，他的论文就是一篇好的论文。 当前流行的搜索引擎如Google、百度都用到了链接分析，它的结果可以反映网 页的重要程度，但并不代表用户对网页的需求程度。 对

40、搜索引擎排序技术的研究有很多，1998年斯坦福大学的博士研究生 Sergey Brin 和 Lawrence Page提出了网络链接分析的一个新算法 PageRank，该 算法是建立在随机冲浪者模型上的。同年J.Kleinberg提出了Hits算法，该算法专 注于改善泛指主题检索的结果。R.Lempel和S.Moran提出了SALSA11 ( Stochastic Approach for Link-Structure Analysis)算法，D. Cohn和 H. Chang 提出了Phits算 法。 随后Hits的变种算法相继提出，如Monika R.Henzinger 和 Krishna

41、 Bharat 提出了HillTop算法，IBM Almaden 研究中心的Clever工程组提出了ARC (Automatic Resource Compilation)算法，Allan Borodin等提出Hub平均(Hub- Averaging-Kleinberg)算法12等，这两种算法都是基于概念模型的。 2001年1月康柏系统研究中心的Krishna Bharat和多伦多大学的George A. Mihaila提出了HillTop算法，该算法利用专家网页对网页进行评判。2004年10月 斯坦福大学的Z.Gyongyi和Hector Garcia-Mo-lina提出了TrustRank

42、算法13，该算 法通过选择不可能作弊的站点，用这些站点对其他网页进行评判。2005年5月A. Benczur和K. Csalogany在第一届AIR Web 学术会议上提出 SpamRank 算法14， 绪 论 7 该算法判断出一些肯定是作弊的站点，与TrustRank算法思路正好相反。 现代搜索引擎的搜索结果不仅仅考虑信息的本身，还融合了关键词和检索 出文档的相关性，使其更为贴近用户需求。另外，搜索引擎对排名采用了多因 素的融合，这些因素有域名因素、文档和页面信息、链接因素、搜索结果因素、 用户数据因素等。 1.3.2 搜索引擎排序算法存在的问题 上面提到了很多排序算法，但是没有一个是十全十

43、美的，每个算法往往致 力于解决某个方面的问题，其他方面可能有所欠缺，现在也有很多综合的排序 算法方面的研究，但仍然难以达到预期的效果。虽然单一的网页排序已经有了 比较成熟的算法，但是，目前还没有一个搜索引擎的排序结果能完全符合用户 的需求，还存在以下方面的问题： 1) 一些网站在页面的标题、锚文本、正文或者Html中恶意堆砌关键词，而 没有用户所需的内容。搜索引擎分析网页的时候，会给这些关键词较高的权重。 当用户搜索这些关键词的时候，这些页面就可能以高的排名返回给用户。目前 的搜索引擎虽然对此做出了相应对策，但从搜索结果来看，依然存在这个问题。 2) 链接分析出现以后，出现了很多作弊行为，网站

44、管理员可以通过制造大 量虚假链接来提升其站点排名，他们还可以通过和其他网站交换链接来增加链 入的URL数目，人为提高了自己站点的反向链接数。 3) 尽管目前搜索引擎的排序方法在一定时间内都会更新一次，来防止一些 网站管理员的作弊，但目前Spam页面的大量存在使得搜索引擎往往不能返回相 关性比较好的结果。 1.4 本文的主要工作及组织结构 本文首先介绍了搜索引擎的发展历史，排序算法的现状及存在的问题；其 次综述网络搜索引擎的工作原理、结构以及分类评价标准。 在此基础上对现有的排序算法进行研究，发现不足之处如：PageRank 平均 分配权威值、Hilltop 中利用“专家页面”不合理，容易产生

45、Spam、Direct Hit 算法不易处理重复点击的作弊行为，然后针对这些缺点引入非均衡分配的思想 来改进 PageRank 算法，利用社区发现技术来减少 HillTop 算法和 Direct Hit 算 法中不利因素对排序结果的影响，以此来改善排序的质量，有效降低 Spam 的 绪 论 8 在排名中的影响，防止网页作弊，使排序结果更合理，从而更好的满足用户的 需求。 本文的结构按如下的方式进行组织： 第一章，绪论。提出选题的意义和背景，介绍了搜索引擎的发展历史，然 后着重研究了互联网的信息特征和目前搜索引擎的不足之处，引出了本文将要 改善的地方排序技术，简述了搜索引擎排序算法的现状，最后概

46、括了本文 将要研究的内容。 第二章，搜索引擎概述。本章主要介绍搜索引擎的分类方法，及其结构与 工作原理，然后综述了现在流行的中外搜索引擎，最后阐述了搜索引擎的评价 标准，如查全率和查准率，覆盖率，死链接率和响应时间等。 第三章，搜索引擎常用排序算法及相关技术。主要分析了现在流行的排序 算法，如词频位置加权算法、PageRank 算法、Direct hit 算法、HillTop 算法等。 其次介绍了搜索引擎的相关技术，包括 SEO 技术15与 Spam 作弊技术16。 第四章，利用社区发现技术改进排序算法。针对 PageRank 平均分配权威值、 Hilltop 中提取“专家页面”不够合理，容易

47、产生 Spam、Direct Hit 算法重复点 击的问题，提出改进排序算法的思路，并加以比较，分析。 第五章，总结展望。总结本文所做的工作，展望未来搜索引擎排序技术的 发展，提出下一步工作的思路。 第二章 搜索引擎概述 9 第二章第二章 搜索引擎搜索引擎概述概述 本章首先概述了搜索引擎分类方法并作了简单的介绍，其次对搜索引擎工 作原理及结构，搜索引擎的每一个组成部分进行了详细的描述，最后阐述了搜 索引擎的评价标准。 2.1 搜索引擎的分类 实际上，通常意义上的搜索引擎只是信息检索系统的前端，面向用户的一 端，而整个信息检索还包括后端的收集、索引信息等功能模块。由于 Web 信息 检索系统很多，功能上也有差异，人们在充分利用这些便利搜索工具的同时， 也会感到无所适从，无从选择。据统计，各种各样的网络信息搜索工具已经有 上千种。从不同的角度，其分类也各不相同。 2.1.1 按所覆盖内容 如果按搜索引擎所覆盖内容的范围来分，可分为通用型、专业型和特殊型 搜索引擎。 1) 通用型搜索引擎所采用的信息资源极为广泛，对资源的主题范围和数据 类型基本没有限制。所以它适用于各种用