网络搜索引擎的分析.doc

《网络搜索引擎的分析.doc》由会员分享，可在线阅读，更多相关《网络搜索引擎的分析.doc（38页珍藏版）》请在三一办公上搜索。

1、本 科 生 毕 业 论 文网络搜索引擎的分析院 系： 信息科学与技术 专 业： 计算机科学与技术 学生姓名： 学 号： 指导教师： 摘要随着互联网的飞速发展，信息革命引发的一个特别的工具-搜索引擎，其作用是在几十亿之间现有的网站中找出具体的用户想要查找的资料。大家都知道，网络搜索引擎已成为最重要的网络信息搜索工具，以获取以无法估计的速度出现的网页信息。到目前为止，很多以前流行的搜索引擎已经渐渐消失，其他新的搜索引擎又开始出现。但是在近几年出现的基于各种不同搜索算法的搜索引擎中， Google已经成为最流行的和成功的搜索引擎之一，Google为何能够成功在很大程度上归因于简单而优雅的PageRa

2、nk算法。该算法的实现原理很简单，当用户提交他或她的想要查询信息时，搜索引擎分析其数据库中已经存放网站，然后返回用户想要查询的超链接列表。更重要的是，此列表按照与用户查询信息的相关度进行排序，以方便用户准确有效地找到想要查询的网页。本论文首先讨论搜索引擎的发展历史、现实重要意义以及其发展趋势。接着详细介绍网页排序算法的实现原理、该算法的优缺点和如何改进该算法、以及对网页排序算法进行实例分析，进一步论述了Google采用的网页排序算法为何会取得如此大的成功。最后重点地介绍如何构建简单有效的搜索引擎，这也是全文的难点，这里只是实现搜索引擎的核心功能，还有更多搜索的功能急需进一步完善。关键词： 搜索

3、引擎 网页排序算法 构建搜索引擎 超链接AbstractWith the development of Internet, the information revolution gives rise to the search engine, a special tool whose task is to identify specifically information among billions of existing websites those are relevant to the users query. As we all know, web search engines ha

4、ve become the most important tools to access information that appear at the speed unevaluated. By now, many of search engines have gone out of business while others have merged. However, among millions of them based on various algorithms that have emerged in recent years, Google has become one of th

5、e most popular and successful one and this companys triumph largely attributes to the simple but elegant algorithm, PageRank algorithm. This principle of this algorithm implements as follows. When a user submits his or her query, the search engine analyzes its repository of stored web sites and retu

6、rns the list of hyperlinks to those that contain information requested by the query. Most importantly, this list is ordered so that most relevant web sites come up first, which might be convenient for the users to find the targets wanted. In this paper it begins our topic with the search engines his

7、tory of development, its practical significance and the future trend developed. Then we discuss the principle of PageRank algorithm in detail, the algorithms merit and shortage, also the modified methods about this algorithm and numerical tests on PageRank algorithm. And it indicates that why Google

8、s core search algorithm have so much potential for development. The last but not least, how to build effective search engines will be introduced. And How to efficiently build a simple engine will be the focus of this paper. In addition, the search engine is constructed to only achieve the core funct

9、ion, and there are many urgent functions to be improved.Keywords: search engine PageRank algorithm build the index hyperlink目 录摘要IAbstractII第一章 前言11.1搜索引擎的历史11.2搜索引擎的分类21.3搜索引擎的现实意义31.4搜索引擎的发展趋势4第二章 搜索引擎原理52.1搜索引擎原理分析52.1.1收集信息62.1.2建立索引72.1.3查询并返回结果72.1.4用户接口72.2PageRank算法82.2.1算法原理82.2.2算法实例分析92.2

10、.2.1第一次计算92.2.2.2第二次计算122.2.2.3第N次计算142.2.3算法的不足142.2.3.1偏重旧网页152.2.3.2主题飘移现象152.2.3.3专业站点被忽视152.2.3.4网页中超链接对网站PR值的影响152.2.4算法的改进162.2.4.1具有时间反馈的改进162.2.4.2基于网页链接和内容分析的改进17第三章 构建搜索引擎193.1Lucene入门193.1.1什么是Lucene193.1.2Lucene的特点193.1.3Lucene构建搜索引擎基本流程203.1.3.1建立索引203.1.3.2搜索流程213.2Lucene检索结果排序223.2.1

11、评分算法公式223.2.2评分算法的特点与不足223.2.3评分算法公式的改进233.2.4另一种评分算法-向量空间算法243.3Lucene构建搜索引擎253.3.1构建运行环境253.3.2搜索引擎的代码实现253.3.2.1索引建立253.3.2.2查询263.3.2.3搜索结果28第四章 结论31致谢32参考文献33第一章 前言1.1 搜索引擎的历史实际上所说搜索引擎是在近10年的不断发展中逐步形成的，建立在互联网中和计算机技术之上。其实也有人说搜索引擎的鼻祖就是黄页，诞生于19世纪末，因为黄页在电话诞生后成为了以电话为主体的信息门户，而且黄页把有电话的企业分门别类，的确与现的搜索引擎

12、有相似之处。下面就简短地介绍搜索引擎的发展历史1： 1990 年由Montreal 的McGill University 学生Alan Emtage、Peter Deutsch、Bill Wheelan 发明的Archie。后来,程序员们开发出了一个名叫“spider”(蜘蛛)的“Robot”(机器人)程序,它能自动以人类无法达到的速度不断重复地在网络上检索信息。 1993年Matthew Gray开发了 World Wide Web Wanderer，这是第一个利用HTML网页之间的链接关系来检测万维网规模的“机器人（Robot）”程序。开始，它仅仅用来统计互联网上的服务器数量，后来也能够捕

13、获网址（URL）。 1994年，第一个既可搜索又可浏览的分类目录EINet Galaxy(Tradewave Galaxy)诞生。除了网站搜索，它还支持Gopher和Telnet 搜索。 1994年7月，卡内基梅隆大学（Carnegie Mellon University） 的Michael Mauldin将John Leavitt的spider程序接入到其索引程序中，创建了Lycos。除了相关性排序外，Lycos还提供了前缀匹配和字符相近限制，Lycos第一个在搜索结果中使用了网页自动摘要，而最大的优势还是它远胜过其它搜索引擎的数据量。 1995年12月，DEC的正式发布AltaVista。

14、AltaVista是第一个支持自然语言搜索的搜索引擎，第一个实现高级搜索语法的搜索引擎（如AND, OR, NOT等)。 1999年2月，Google完成了从Alpha版到Beta版的蜕变。Google以网页级别（PageRank）为基础，判断网页的重要性，使得搜索结果的相关性大大增强。而且Google在PageRank、动态摘要、网页快照、DailyRefresh、多文档格式支持、地图、股票、词典、寻人等集成搜索、多语言支持等，像Altavista一样，再一次彻底改变了搜索引擎的定义。 2000年1月，超链分析专利发明人、前Infoseek资深工程师李彦宏与好友徐勇（加州伯克利分校博士）在北

15、京中关村创立了百度（Baidu）公司。2001年8月发布B搜索引擎Beta版（此前Baidu只为其它门户网站搜狐、新浪、Tom等提供搜索引擎），2001年10月22日正式发布Baidu搜索引擎。 2005年6月，新浪正式推出自主研发的搜索引擎“爱问”。1.2 搜索引擎的分类计算机技术飞速发展，关于搜索引擎的定义和发展过程，按其工作方式主要可分为全文搜索引擎、目录索引类搜索引擎和元搜索引擎三类2。 全文搜索引擎全文搜索引擎是名副其实的搜索引擎，它通过从互联网上提取各网页的信息而建立的数据库中，检索与用户查询条件匹配的相关记录，然后按一定的顺序返回给用户。而数据库的建立是通过一个叫网络机器人或叫网

16、络蜘蛛的软件，定期自动分析网络上的各种链接并获取网页信息内容，按规则加以分析整理，记入数据库。此搜索引擎主要依靠网络机器人搜索数据，因此需要的数据库容量非常庞大，但是收集内容往往不够准确。可以看出，百度和Google就是典型的全文搜索引擎系统： 目录索引类搜索引擎目录索引类搜索引擎虽然也具有搜索功能，却从严格意义上来讲不能算是真正的搜索引擎。因为此搜索引擎是通过人工的方式收集整理网络资料形成数据库的，能够提供更为准确的查询结果，但收集的内容却非常有限。用户完全可以不用进行关键词查询，仅靠分类目录也可找到需要的信息。主要代表如Yahoo雅虎，Open Directory Project（DMOZ

17、），网易搜索。 元搜索引擎元搜索引擎可以在接受用户查询请求时，同时在其他多个引擎上进行搜索，并将搜索结果返回给用户。著名的元搜索引擎有InfoSpace、Dogpile、Vivisimo。 1.3 搜索引擎的现实意义互联网正以前所未有的态势改变整个世界，它现在已经成为了人类有史以来资源数量最多、资源种类最全、资源规模最大的一个综合信息库。其信息来源丰富、分布广泛，各种类型信息资源异构地分布于网络空间中，如果不能使庞杂的信息有序化，就很难获取。如何准确有效地从互联网上获取信息，搜索引擎的重要性就显得越来越重要。搜索引擎的工作原理实质是信息的获取，传统的信息获取技术是通过线性匹配查找的资源，这种方

18、法无需对查找资源中的信息进行预处理，仅适用于资源较少的情况。但面对当前海量的信息，如何能够快速、准确、全面地获取信息呢？一般信息获取可为以下几个部分：1) 在获取信息之前，必须先构建文本数据库。这个文本数据用来保存所有用户可能检索的信息，数据库的信息可能会不断地变化。但是一旦文本模型确定下来后，就不应对其再进行大的变动。2) 有了这种文本模型后，就应该根据数据库内的文本建立索引。索引可以大大提高信息检索的速度。采用哪种方式取决于信息检索系统的规模。大型信息检索系统均采用倒排的方式来建立索引。3) 建立好索引后，就可以开始对其进行检索。通常是用户提交一个检索请求，该请求将被分析，然后利用文本操作

19、进行处理。对于真实的信息检索系统，在真正处理查询请求前还可以进行一些预处理。4) 根据用户的查询返回检索结果，通常需要对检索结果进行一定的排序与过滤，以便把重要的检索信息排在最前面。 用流程图表示搜索引擎工作流程如下： 图1-1 搜索引擎工作流程1.4 搜索引擎的发展趋势在互联网的发展初期，网站的数量比较少，信息查找相对容易。但是伴随着网络信息以指数的膨胀速度增长，单纯的简单搜索已经远远无法满足用户的需要。因此各类搜索引擎的品牌越来越多，如最初的Google、Yahoo到现今的baidu、MSN、Sogou等满足大众信息检索需求的专业搜索网站也应运而生。现在的搜索引擎往往将自己的搜索范围扩大到

20、整个因特网上，然而数据库规模庞大，为了提高查询速度而往往忽视了查询信息质量。对于一次检索，大型搜索引擎往往有成千上万条符合要求的信息，而用户只会浏览其中几十条，也就是说用户并不需要得到所有符合检索要求的信息，因此全面、准确、快速是衡量搜索引擎的重要标准。搜索引擎的发展趋势应该是更强调人的因素，用户只需告诉搜索引擎想要查询什么，而无需理会如何实现。而搜索引擎应该具有判断性收集信息的功能，即根据特定用户的行为来决定信息的取舍，提供多样化服务，也就是说将自动分类技术、中文内容分析技术及区域识别技术应用到大型搜索引擎中，除了在信息检索速度、更新频率等基本技术指标方面处于领先地位外，相关网页检索、纠错、

21、模糊查询、语音查询技术也具有较高的水准3。目前各搜索引擎的搜索功能仍然处理数据库基础建设和流程挖掘层面，搜索结果仍处于对数据初步加工过程。但相信在不远的将来，搜索必然搜索流程的多次加工和搜索输出项的个性化发展。一方面搜索巨头的发展必将导致搜索服务继续呈现高度集中的趋势；另一方面搜索技术、权力、需要、主体、利益等方面发生潜移默化的变化，又开始呼唤中小服务商的崛起以及与之密切相关的搜索领域的多样化竞争格局，搜索商业的集中和发散同时存在。第二章 搜索引擎原理2.1 搜索引擎原理分析搜索引擎一般由搜索软件、索引软件和查询软件组成，其中搜索软件用来在网络上收集网络信息；索引软件对收集到网页的信息进行自动

22、标引，并建立索引数据库；查询软件则通过查询索引数据库为用户提供服务。各种网络搜索引擎通过网络搜索软件定期或不定期地在网络上搜索信息，并对搜索到网络信息进行收集和整理，从而建立可供查询的索引数据库。因此搜索引擎的工作包括以下三个过程：一是在互联网中发现、搜索网页信息；二是对搜索的信息进行提取和组织，生成索引数据库；三是由检索程序根据用户输入的查询关键词，在索引数据库中快速查询出相关文档，进行文档与查询内容的相关度比较，对检出结果进行排序，并将查询结果返回给用户。以下是搜索引擎的基本结构4： 图2-1 搜索引擎系统结构图 下面详细地分析搜索引擎的工作三个流程以及相关的用户接口：2.1.1 收集信息

23、搜索引擎中网页的采集工作主要由网络搜索软件(如Robot、Spider、Worm)完成, 开发出性能良好的网络搜索软件是一个艰巨的工作。由于网络带宽窄、网页更新快, 搜索引擎的网络搜索软件搜集所有网页已经成为不可能的事情，优先获取重要网页逐渐成了网络信息搜索中重点研究的问题。不同种类的搜索引擎有各自的信息收集方式和范围，这样就导致不同的搜索在检索结果的数量以及质量产生很大的差别。例如有些搜索引擎会把搜索范围发往每一个站点，记录下每一网页的所有文本内容；有些搜索引擎则会搜索那些刚刚被更新的网站，然后再将其链接收集起来；有些搜索引擎首先分析数据库中的地址，以判别哪个站点最受欢迎，然后再去记录这些网

24、站的信息。当然，除了主动搜索方式外，用户还可以手动提交网页的URL，即由网站的拥有者自行向搜索引擎提交网页，并将提交的网页放入搜索引擎数据库中。2.1.2 建立索引搜索引擎的第二个过程是对搜索软件采集到的信息进行自动标引，建立可供查询的索引数据库。当然不同搜索引擎的索引数据库规模和记录的内容是不同的，数据库的规模将直接影响查询的召回率。例如，有些搜索引擎对网页内容全文索引，即对网页中每一单词进行索引；有些搜索引擎对网页某些特征或分类进行信息提取；还有一些搜索引擎则根据网页的热门程度来决定是否对网页建立索引。2.1.3 查询并返回结果搜索引擎的最后一个阶段是负责接收用户请求和对该请求进行检索，并

25、按相关度返回给用户。大多数搜索引擎除具备分类浏览和自由词全文检索等基本功能外，还包括词语检索、范围检索、概念检索以及位置检索等。2.1.4 用户接口前面介绍搜索引擎的具体三个流程，下面谈一下用户接口的作用。用户接口主要是输入用户查询、显示查询结果以及提供用户相关性反馈机制。其最主要目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中获取有效、及时地信息。在众多智能搜索系统中,超链接分析是近期大家主要研究的问题, 而搜索引擎Google所采用的PageRank 算法尤其得到认可,下面就重点介绍PageRank算法的原理。2.2 PageRank算法2.2.1 算法原理 PageRank算法5

26、是1998年由斯坦福大学的Sergey Brin 和Lawrence Page 提出,它是基于以下原理:如果网页A存在一条指向网页P的超链,则认为网页A得到网页P的认可;如果有多个网页指向网页A,则认为网页P的地位比较重要,即当网页A有一个链接指向网页P时,就认为网页P获得了一定的分数,该分值的多少取决于网页A 的重要程度,即网页A 的重要性越大,网页P获得的分数就越高. 由于考虑到互联网上的链接相互指向的复杂程度6,每个网页所得的分数的计算过程是一个迭代的过程,最终网页将依照所得分数排序并将排序的结果交给用户,这个量化的分数就是PageRank值.用PageRank量化公式表示如下: 假设P

27、R(A)是网页A的页面级别； d 为界于(0,1)区间的衰减系数,一般取0.85左右； 表示指向网页A的其它网页； 为网页向外指出的链接数目. Page Rank公式如下： (2.1) 事实上，根据上述公式可知，PR值的计算并不是仅仅一次就能完成的；由于网页之间的相互链接，任意网页PR的变化，都会引起其他与之相关链接关系的网页PR的变化，因此计算某一网页的PR值，都要经过多次反复计算，在达到一定次数的重复计算后，各网页基本达到稳定。 由上述公式可知，某网页有较多的链入网页，则说明其它许多网页都认为该网页比较重要的；若较高PR的网页指向该网页，则认为有更重要的网页认为该网页重要；若其它网页都只一

28、条链接指向该网页P，则认为许多网页都认为该网页比较重要，这样网页P被推荐的机会就会更大。网页的PR值越高，那么该网页在检索结果列表的位置就越靠近。2.2.2 算法实例分析 我们清楚了PageRank算法迭代公式为： 下面我们来举个实例具体分析PageRank算法的实现：假设有五个网页，它们之间的链接关系如下：图2-2 初始链接结构根据上述迭代公式，每个网页的PR初始值为1，其中衰减因子d为0.75，这样每个网页就相当有0.25(1-d)不用于传递，即每个网页中0.75被平均地传递到其它链出网页中，下列是迭代公式的计算过程：2.2.2.1 第一次计算l 首先，对于网页A，它有一个链出网页，考虑衰

29、减因子之后，网页A有0.25不用传递，其它0.75被传递到网页B。 同理，网页B、网页C、网页D也同样只有一个链出网页。l 其次，对于网页E，它有三个链出网页A、B、D，这样在考虑衰减因子后，网页中的0.75被平均传递到网页A、B、D。l 最后，得到第一次计算结果的PR情况：l 网页APR(A)=0.25(网页A未传递给其它网页)+0.25(来自网页E) =0.5即l 网页BPR(B)=0.25(网页B未传递给其它网页)+0.75(来自网页A)+0.25(来自网页E)+0.75（来自网页D）=1.25 即l 网页CPR(C)= 0.25(网页C未传递给其它网页)=0.25即 PR(C)=0.2

30、5l 网页DPR(D)=0.25(网页D未传递给其它网页)+0.75(来自网页C)+0.25(来自网页E)=1.25即l 网页EPR(E) =0.25(网页E未传递给其它网页)+0.75(网页B未传递给其它网页)=1.00即 l 这样可以得到第一次计算过程中网页之间传递的PR情况如下： 图2-3 第一次计算后网页链接2.2.2.2 第二次计算由于第一次计算后改变各网页的PR值，势必会引起与它相邻网页PR值的改变，例如对于网页A，网页E的PR值改变必然会引起网页A的PR值改变。因此计算仍然需要继续。第二次计算各网页的PR值与第一次计算各网页的PR值方法相似，计算过程如下：l 网页APR(A)=0

31、.25(网页A未传递给其它网页)+0.50(来自网页E)=0.75即l 网页BPR(B)=0.25(网页B未传递给其它网页)+0.375(来自网页A)+0.25(来自网页E)+0.9375（来自网页D）=1.8125 即l 网页CPR(C) =0.25l 网页DPR(D)=0.25(网页D未传递给其它网页)+0.1875(来自网页C)+ 0.25(来自网页E)=0.6875即l 网页E PR(E) =0.25(网页E未传递给其它网页)+0.75(网页B未传递给其它网页) =1.00即 这样就可以得到第二次计算后 图2-4 第二次计算后网页链接情况2.2.2.3 第N次计算 每次计算后各网页PR

32、值随着改变，从而引起了新一轮的计算，这样不断进行迭代计算各网页的PR值，直至各网页的PR值趋于稳定状态，最终的稳定状态PR值将作为各网页的最终PR值。由上述计算过程可以看出，PageRank算法使所有网页的总和非常巧妙地达到平衡，就像物理中能量守恒定律，所有网页的PR值总和保持不变。例如上述计算中，各网页的初始PR值总和为5，第一次计算后各网页的PR值总和也为5，第二次计算后各网页的PR值总和也为5。同时，我们可以发现网页之间可以通过相互链接7来获得反馈值，例如由上述计算可知，各网页相互链接，各网页与其它网页链接可以得到链接网页的反馈值。由此我们可以想到假如在一个网站上，网站拥有者可以根据各网

33、页链接的设置来影响到网页的PR值，从而使网页的PR值受到更多主观因素的影响。例如Google如果认为某网站具有较大的影响力，那么它会把这个网站的PR值设置高一些，这样就可以方便用户更加准确搜索到对应的网站；假如Google认为某网站是低质量的垃圾网站，那么它就会把该网站的PR值设置相对低一点。2.2.3 算法的不足PageRank算法提出是成功的，符合网络发展搜索引擎的运作趋势，Google的成功运作就是一个极好例子。但是PageRank算法还存在一些明显的不足，因为PageRank算法的提出是基于传统文献引文分析方法，并不完全适应于网络环境。因为网页尤其是一些门户站点的网页有太多的分散主题，

34、不像一篇学术文献通常有较为集中的主题；而且由于网络世界的开放性，网页是时刻变化的，人们可以根据需要进行内容以及链接的变更，也可以采用有效的链接策略来影响网页的PR值，不像传统学术文献一经出版就很少进行更改。况且网站和网页日益商业化，很多公司的网页不会链接到其对手的网站。下面详细介绍PageRank算法的不足之处。 2.2.3.1 偏重旧网页从公式（2-1） （2-1） 可以看出PageRank算法偏重旧网页8，因为从(1)式中可以看出决定一个网页PR值的主要因素是指向该网页的链接个数，但由于网页在网络存在的时 间越长，那么它被链接的机会就越大。这样由(1)式可以看出旧网页PR值比 新网页PR值

35、大，也就是说PageRank偏重旧网页。2.2.3.2 主题飘移现象 由于PageRank算法仅仅对互联网络的拓扑结构分析，无法区分网页中的链接和该网页有关还是无关的，即无法判断网页间主题的相关性，这样容易在最后的推荐结果出现大量与主题无关却又与具有很高的PageRank值的网页，即出现所谓的主题飘移现象9。例如你在Google查询“图片”，但又因为某些重要网站但又与本次查询主题无关的网站PR值过高而出现在最前方，这样会加重用户搜索到相应目标的速度，在一定程度上加重了用户的负担。2.2.3.3 专业站点被忽视专业站点的访问量远远少于通俗站点的访问量10，比如某个学术网站，它的内容再好，也不可能

36、在短时间内迅速地得到大量的超级链接，所以无法得到合适的排名。但是专业站点的论述往往比通俗站点的论述更深刻、更有价值。2.2.3.4 网页中超链接对网站PR值的影响网页中的超链接形式11各异应该区别对待，而公式(1) 却无法正确对待一个网页中指向的超链接。例如下图：(B)图在(A)图的基础上在网页A增加三个指向重要网页D、网页E和网页F的超链接。从客观分析，应该网页A的PR值应该有所增加。但是由公式(1)分析，网页A的PR值不变，而且由于网页A的链接数据增加，因此网站B的PR值有所减少，这样不合常理的。产生这种情况的主要原因是过于简单地判定一个网页指出的超链接会对该网页产生负面影响。其实应该分别

37、看待这个问题：如果网页A中的一个超链接所指向的网页B在内容上与该网页内容相关，则此超链接增加网页A的PR值，否则该超链接会减少网页A的PR值。 图2-5 网页间链接结构2.2.4 算法的改进 根据上述对Page Rank算法不足之处的分析，可以看出一个新网站、小网站或者专业学术网站，由于它们不可能在短时间内迅速得到大量的超级链接，这样就会影响到搜索返回结果排名顺序的可靠性，因此必须对PageRank算法进行加以改进，为此我们可以从下面几个方面进行改进11。2.2.4.1 具有时间反馈12的改进由公式(1)可以PageRank算法存在偏重于旧网页的缺点，不能地反映网页的实际重要性，也不能很好地满

38、足客户的要求。因此应将某些关于日期的因素加入，比如网页的发布日期，因此网页发布日期的引入能够使在网络上存在时间长的网页在检索结果排名中沉下去，而新网页迅速升起来。但由于很多网页都是由系统自动生成，并且大量HTML网页的格式不规范，很难在网页中提取到此网页的发布时间。因此如何才能更好地表征新网页的特征呢？可以这样考虑，把网页存在的时间通过搜索引擎搜索周期数来表征，它的核心思想是考虑到搜索引擎的搜索周期为半个月到一个月，因此若一个网页存在的时间很久，那么它在一个搜索周期内此网页可能被搜索到多次。如果把我们一个网页无论被搜索到多次，都看作是搜索到一次，那么就可以有效地克服PageRank算法偏重于旧

39、网页。2.2.4.2 基于网页链接和内容分析的改进n 在PageRank算法中，由于知名网站被大量网站链接，这使得此知名网站获得较高的PR值，这样相对于某个特定的查询，即使它与查询微弱相关也会排在检索结果的前列，也就是出现了主题漂移现象，因此主题漂移使得查询的相关性遭到极大的破坏。如何才能有效地克服PageRank这种缺点呢？由此可以使用基于网页链接和内容的分析，对查询主题进行相关性评价。n 假设Q 为查询主题；为查询文档；项i在查询Q中出现的次数；项i在文档中出现的次数；是WWW上包含项i的文档数目的估计值；这样就可以得到主题Q与文档的相似度可以按以下公式计算： (2-2)n 在链接关系的基

40、础上，加入页面与查询主题的相关性权重，以使得所产生的PageRank值高的页面是针对用户查询主题的，这就形成了WPageRank算法。改进公式如下： (2-3)其中A为给定的一个网页，假设指向它的网页；分别网页所含的链接数；d为衰减因子， 一般取0.85；为网页A的WPageRank值。n 对于上述WPageRank算法公式可以这样理解，假设网络上有一个主题浏览者WPageRank13是访问到网页A的概率，它从初始页面集出发，按照页面链接前进，从不执行back操作。在每一个页面，浏览者对此页面的链接感兴趣的概率和此链接与主题的相关性成正比例。也有可能浏览者对此页面的链接不感兴趣，这个可能的概率

41、是d。从直观上看，如果有多个页面指向某个页面，则该页面的PageRank值必定会提高，但是WPageRank不一定会高；若有WPageRank很高的页面指向它，则此页WPageRank也会很高。因此可以很大地避免主题飘移的现象。第三章 构建搜索引擎3.1 Lucene入门3.1.1 什么是LuceneLucene是一个用Java写的全文检索引擎工具包14，可以方便地嵌入各种应用中以实现全文检索/索引功能，虽然它不是一个完整的全文检索引擎，但是它是一个全文检索引擎的架构，提供了完整的查询引擎和索引引擎及部分文本分析引擎。Lucene的目的是为软件开发人员提供一个简单易用的工具包，以方便地在目标系

42、统中实现全文检索的功能，或者以此为基础建立起完整的全文检索引擎。Lucene功能强大，能够对任何数据做索引和搜索。Lucene不管数据源是什么格式，只要它能被转化为文字的形式，就可以被Lucene所分析利用。例如在word、html、PDF还是其他什么形式的文件，只要可以从中抽取出文字形式的内容就可以被Lucene所用，就可以对它们进行索引以及搜索。Lucene是一个开放源代码的项目，自从问世之时起，就引发了开发源代码社区的巨大响应。主要因为Lucene提供一个全文检索引擎的架构，具有可扩展性且易理解，因而它不仅被用于构建具体的全文检索应用，而且也将它集成到了各种系统软件中，以及用它来构建各种

43、web应用，甚至某些商业软件也采用lucene作为其内部全文检索系统的核心。3.1.2 Lucene的特点Lucene作为一个全文检索引擎，具有以下突出的优点： 索引文件独立于应用平台，Lucene定义了一套以8位字节为基础的索引文件格式，使得能够兼容或者在不同的系统平台下共享建立的索引文件。 由于其源码的开放性，任何人都可以从网站上获取最新源码，并进行二次开发，扩展其功能。 强大的面向对象系统架构，有利于功能扩展，以模块化的思想来学习，更有利于理解。 扩展索引的时候不断创建新的索引文件，然后定期地把这些小索引文件合并到原先的大索引文件中。 在传统全文检索引擎的倒排索引基础上，实现分块索引，能

44、够对新的文件建立小文件索引，提升索引速度，再与原索引进行合并，以达到优化的目的。当然，Lucene也有许多不足之处： 不提供在Internet上采集信息的功能，也就是说没有提供专门的搜索软件对网页信息进行自动采集。 如何将用户最感兴趣、最重要的网页放在搜索结果的靠前位置，Lucene在这方面还有待完善。 只支持文本格式，如txt，html等，不支持word，PDF等文件。 由于中文分词的特殊性，Lucene在设计时并没有考虑亚洲文字的特殊性，因此不能对有中文内容的文件进行有效的搜索和查找。3.1.3 Lucene构建搜索引擎基本流程3.1.3.1 建立索引索引技术主要有3种：倒排索引，后缀数组

45、和签名文件15。其中Lucene采用的索引技术为倒排索引技术，它对于关键词的搜索非常有效。从整体看，Lucene建立索引有以下4步：l 提取文本为了能够使用Lucene对文档数据建立索引，需要将建立索引的文档数据转换成Lucene可以处理的类型。例如为word文档数据建立索引，首先应从此文档中提取文本信息，这样可以有利于Lucene的分析。图3-1 多类文档处理l 构建Document为了将前面所提取出来的文本组装成Lucene可以识别的格式，应建立适当的Document，因为任何需要进行索引的文件都必须被转化为Document对象才能被索引和搜索到。l 分析并建立索引在提取了需要Lucene

46、建立索引的数据并且创建了Document之后，接下来Lucene会首先对所要建立索引的数据进行分析，以使得在建立索引时可以更加容易地处理这些数据，然后索引器会按Lucene所规定的索引格式将数据写入索引文件中。3.1.3.2 搜索流程 初始化Lucene的检索工具IndexSearcher所有检索都会用到Lucene中最基本的检索工具IndexSearcher，但在使用IndexSearcher之前，还要对其进行初始化。即需要设置索引存放的路径，这样才能让查询器定位索引，用于后面进行搜索。 构建Query在使用Query之前，需要首先生成一个Query对象，需指明查询字段采用什么样的方式进行查询，如模糊查询、语义查询、短语查询、范围查询以及组合查询等。 搜索并处理