《网络信息检索》课件第7章

第7章搜索引擎7.1

概述7.2链接分析7.3相关排序7.4大规模搜索引擎7.5小结思考题

7.1概述

7.1.1发展概况

在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网指数速度的扩张，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大众信息检索需求的搜索引擎网站便应运而生了。

现代意义上的搜索引擎的早期历史可以参看第1章1.3.1节，先后涌现出了Archie[1]、WAIS[2-3]、Gopher[4]、

Wanderer[5]、ALIWEB[6]()、JumpStation[7]、TheWorldWideWebWorm[8]和Repository-BasedSoftwareEngineering(RBSE)spider[9]等。

1994年7月，卡耐基-梅隆大学(CarnegieMellonUniversity)的MichaelMauldin将爬虫程序接入到其索引程序中，创建了Lycos[11]()；同年4月，斯坦福大学(StanfordUniversity)的两名博士生杨致远和DavidFilo共同创办了Yahoo(),并使搜索引擎的概念深入人心。在这个时期，以Yahoo、AltaVista()、Excite()、Infoseek()等搜索引擎为代表，各搜索引擎的开发设计力求在数据库覆盖范围、检索响应时间、检索结果反馈、用户界面友好等方面有所突破。最初的搜索引擎采用分类目录的形式来组织Internet资源，如Yahoo和Excite等，按学科、字母顺序、时间先后、地理区域，或是这些方法的组合。这种方法的优点是资源结构清晰，符合人们的使用习惯，但必须花费大量的人力来搜集、组织信息，需要人工维护，内容覆盖范围有限等。随着网络信息的剧增，单纯依靠人工的方法来组织所有的信息资源已不大可能。

1998年9月，斯坦福大学的两个博士生LarryPage和SergeyBrin创建了Google，这标志着新一代的搜索引擎出现了。Google搜索引擎通过估算反馈网页质量及相关程度来决定排名次序，搜索结果的排名与网页质量有密切的关系，因为人们一般不会关注低质量的网页。这种搜索技术可以让用户尽可能获得好的搜索结果和良好的用户体验，因此也使得搜索引擎进一步走向了实用性，成为网络上最关键的应用之一。目前，互联网上的搜索引擎非常多，呈现百花齐放的局面，如MSN()、Overture()、LookSmart()、HotBot()，以及最大的中文搜索引擎百度()等。其检索的信息量也与日俱增。目前全球最大的搜索引擎Google()，已可索引和检索80多亿网页，而2008年面世的搜索引擎Cuil()，号称可索引和检索1000多亿网页，百度也号称超过10亿个索引页面。选择多了，对用户来说也是一件难事。每个搜索引擎都有它自己的特点和长处，是否可以集众搜索引擎之所长，来更好地满足用户的需求？元搜索引擎(MetaSearchEngine)就是一种集成化的检索软件，通过多个成员搜索引擎提供的服务向用户提供统一的检索服务，如Metacrawler()、Savysearch()等元搜索引擎，主要目的是综合各种搜索引擎的长处，尽量减少用户的检索过程，提高检索效率。

按照索引方式的不同，搜索引擎可分为以下3种类型，这3种类型都有各自的特点和代表。

1．机器人搜索引擎

由信息搜集系统(Crawler)自动在互联网中搜集和发现信息，由索引器(Indexer)建立索引，由检索器(Searcher)根据用户的查询检索索引库，并将结果按一定的排列顺序返回给用户。机器人搜索引擎的最大特点是可以自动采集和更新信息，信息量大，且不需要人工干预，目前流行的搜索引擎大多属于此类。但机器人搜索引擎也有缺点，如返回的信息过多，且存在大量不相关的信息，用户必须在结果中筛选。Google和百度都属于机器人搜索引擎。

2．目录搜索引擎

与机器人搜索引擎完全不同的是，目录搜索引擎通常以人工方式或半自动方式搜集信息，由编辑员审核信息，人工形成信息摘要，并将信息置于事先确定的分类框架中，提供目录浏览和直接检索。目录索引虽然有搜索功能，但在严格意义上不算是真正的搜索引擎，仅仅是按目录分类的网站链接列表而已。用户完全可以不用进行关键词查询，仅靠分类目录也可找到需要的信息。目录式搜索引擎的特点是信息准确，导航质量高，但需要人工介入，维护的工作量较大，且信息量少，更新不及时。比较著名的目录索引搜索引擎有Yahoo、OpenDirectoryProject(DMOZ，)和LookSmart等。

3．元搜索引擎

元搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行去重、重新排序等处理后，作为自己的结果返回给用户。元搜索引擎的特点是返回的信息量更大、更全，但用户也因此需要做更多的筛选。著名的元搜索引擎有Dogpile()、Vivisimo()等。在搜索结果排列方面，有的直接按来源引擎排列搜索结果，如Dogpile，有的则按自定的规则将结果重新排列组合，如Vivisimo。7.1.2术语与定义

搜索引擎实际上是一个网络应用软件系统，它能够接受用户通过浏览器提交的查询词或者短语，例如“汶川地震”、“奥运会”、“春晚”等等，并在可以接受的时间内返回一个和该用户查询匹配的网页列表，列表的每一条目至少包括标题、网址链接和摘要等信息。下面给出搜索引擎的一些相关术语介绍。

超链接：超链接是联系两个网页的结构化单位，如图7-1所示，网页间的这种联系通过在源网页(SourcePage)的指定位置处插入一个超链接来实现，超链接包含了目标网页(DestinationPage)的URL[12]。图7-1超链接示意图链接分析(LinkAnalysis)：链接分析是对网页之间链接方式的分析，通过这种分析，我们可以提取出网络拓扑结构图的一些有用信息，可以分析某个网站的拓扑结构、声望和分类等，从而实现辅助检索的目的。

反向链接和正向链接(Inlink&Outlink)：如果网页A有超链接指向网页B，则称网页B有一个来自A的反向链接“inlink”链入，同时，称网页A有一个正向链接“outlink”链出到B，如图7-2所示，网页C有两个反向链接，分别来自A和B，A和B则分别有一个正向链接，都指向C。图7-2正向链接、反向链接示意图入度和出度(NumberofInlink&Outlink)：网页的反向链接的个数称为网页的入度，网页的正向链接的个数称为网页的出度。

锚文本(AnchorText)：锚文本即链接文本，它概括了所指向的网页的主题，而这种概括通常要比该网页自身的描述还要准确。例如，在个人网站上把中央电视台()作为新闻频道的链接，访问者通过点击网站上的“新闻频道”就能进入中央电视台网站，那么“新闻频道”就是中央电视台网站首页的锚文本。锚文本还可以指向一些普通的搜索引擎不能索引的文件，如图像、程序和数据库文件等。信息摘要(Summary)：信息摘要是指对网页信息内容进行概括，不加评论和补充解释，简明准确地提取主要内容而形成的短文。

网页快照(SnapShot)：搜索引擎在收录网页时，都会做一个备份，大多是文本的，保存了该网页的主要文字内容，这个备份称为网页的快照。当被访网页被删除或者连接失效时，用户可以使用网页快照来查看这个网页的主要内容，由于快照以文本内容为主，访问速度比对应网页要快。

搜索引擎类别各异，但基本架构是类似的，也就是说，它们一般都具有以下这些模块。

爬行程序(Crawler)：通过评估链接或者预定义的地址来发现网页。主要工作是下载网页，并分析网页源码，发现网页上的所有链接，并决定网络爬虫的爬行方向。索引器(Indexer)：索引器解析每个网页，并分析不同的元素，如文本、头、结构或格式特征、特殊的HTML标签等，形成特殊的数据结构存入索引库中。

索引库(IndexingDatabase)：搜索引擎所下载和分析的数据的存储区域，也称为搜索引擎的数据库。

结果引擎(ResultsEngine)：结果引擎从索引库中提取信息，并负责对结果排序。它基于搜索引擎的排序算法(RankingAlgorithm)，决定哪些网页与用户的查询最吻合，而且应以什么样的顺序排列。检索服务器(QueryServer)：检索服务器实际上是一个web服务器，检索界面是一个包含输入框的HTML页面，用户可以在输入框内输入感兴趣的检索词，检索服务器还负责将用户查询的结果转换为HTML页面。

PageRank：简称PR，PageRank[18]是Google衡量网页重要性的工具，测量值范围为1~10，分别表示某网页的重要性。在Google工具栏可以随时获得某网页的PageRank值。

不同搜索引擎的实现机制可能是不同的。例如，Spider、Crawler和Indexer可能总共由一个程序完成，完成网页的下载、分析和利用其链接发现新的资源，然而，这些模块都是搜索引擎所必有的。7.1.3工作原理

现代大规模高质量搜索引擎一般采用如图7-3所示的称为三段式的工作流程[13]，即网页收集、预处理和查询服务。图7-3搜索引擎三段式工作流程其中收集阶段主要进行网页的批量搜集，增量式搜集；预处理阶段则进行关键词的提取，重复网页的消除，链接分析，建立索引等工作；查询服务则采用不同的查询方法对用户的查询关键词与索引库进行匹配，将得到的结果生成信息摘要，并按照一定的顺序输出给用户。这些工作在前面的章节均有介绍。

下面以开源软件项目Nutch[14]为例介绍一个搜索引擎的工作原理。

Nutch是Apache[15]开源组织的子项目，是一个开源搜索引擎系统。Nutch能够提供Web网页和FTP站点等资源的抓取和检索服务；可以对html、doc、pdf和text等多种格式的文本进行解析和存储。

Nutch采用了插件的开发模式，使整个系统具有非常好的可扩展性。图7-4所示就是Nutch的系统结构，图中的数据模块以及一些意义描述见表7-1。

Nutch的系统工作原理依然可以采用三段式工作流程来描述。Nutch搜索引擎的工作大体按照以下流程进行。图7-4Nutch的系统结构

1.数据搜集

Nutch搜索引擎系统的爬虫(Crawler)是一个增量式的爬行系统，其工作原理是通过对第n轮爬行抓取的网页进行解析，得到新的URL链接地址，并丰富现有的URL库，这个URL库将是第n+1轮抓取网页的基础。选择第n+1轮需要抓取哪些网页也是有一定策略的，根据是否是新网页、网页内容更新频率、URL深度等信息确定即将采集的网页URL集合。

在Nutch中，系统在WebDB中选择需要采集的URL地址，将这些地址放入一个新的Segment目录的fetchlist文件中。网页采集模块根据fetchlist中的URL列表，对相应的URL发送HTTP请求，下载相应的网页，并保存于上文介绍过的Fetcher、ParseData、ParseText和Content文件中。

2.数据预整理

数据整理可以分成两个阶段，第一个阶段是对采集回来的数据存储和分析，第二阶段是建立索引。

(1)数据分析。爬虫程序在网络中抓取的数据，根据不同的需要，将数据分别保存于Fetcher、Content、ParseData、ParseText文件中。在这些文件中，不仅仅包含抓取的网页的基本信息，而且包括抓取网页的状态信息、网页之间的连接信息、HTTP协议信息等等。大量试验表明，返回用户查询结果所依赖的索引(Index)文件中，如果仅仅包含网页文档信息，这个结果就是很不理想的，并且会受到很多噪声信息的影响；一个好的索引文件中至少要包括网页的重要性信息、网页之间的链接信息、单个网页的内容信息、单个网页的题目(Title)和URL等等。尤其前两者反映了网页与网页之间的链接拓扑，是两个非常重要的信息。数据分析的目的也在于将这两个信息提取出来。

(2)建立索引。Nutch使用开源索引系统Lucene[16]对文档进行索引。对于每篇文档，至少包含如表7-2所示的索引域(Field)。在明确了需要什么样的数据之后，就可以建立索引了。但是中文和英文不同，不同的语义单元不是自然间隔的，而需要使用一定的策略将中文文本切分成一个个词汇，这个步骤一般称为“分词”或“切词”。“分词”的基础在于开发者需要拥有一个丰富的“词典”，用分词程序从网页文字中分出“词典”所含的词语来。一般来讲，通过分词可以得到很多词，同一个词可能在一篇网页中多次出现。从效果(effectiveness)和效率(efficiency)两方面考虑，不应该让所有的词都出现在网页的表示中，要去掉诸如“的”、“了”等没有内容指示意义的停用词。上文中提到的9个索引域中的content、anchor、title3个索引域的内容要先经过中文分词再写进索引文件。

如第4章所述，索引文件的工作原理是通过某些关键词能够迅速定位到出现这个关键词的某篇文档。Nutch采用倒排索引机制，将海量网页文档排序顺序存储的同时，建立排好序的关键词列表(倒排表)，用于存储“关键词到文档”的映射关系，并利用这样的映射关系建立索引。

3.检索服务

检索与索引是两个相关的过程，索引的实质是建立关键词与文档映射的倒排表的过程，检索是通过倒排表和关键词读取相应的文档的过程。

(1)查询。一般来讲，系统面对的是查询短语。就英文来说，它是一个词的序列；就中文来说，它是包含若干个词的一段文字。一般地，我们用q0表示用户提交的原始查询，例如，q0=“华南理工大学”。首先需要“分词”，即把它分成一个词的序列。如上例，则为“华南理工大学”。然后需要删除那些没有查询意义或者几乎在每篇文档中都会出现的词(例如“的”)，最后形成一个用于参加匹配的查询词表，q={t1，t2，…，tm}，在本例中就是q={华南，理工，大学}。倒排文件是上文中提到的索引文件，它保存了关键词与出现该关键词的文档的对应关系，显然，q中的词必须是包含在倒排文件词表中才有意义。有了这样的q，它的每一个元素都对应倒排文件中的一个置入文件表，记作(ti为查询词)，它们的交集或并集即为对应查询的结果文档集合，从而实现了查询和文档的匹配。上述过程的基本假设是：用户希望结果网页包含所输入的查询文字。

(2)排序。在得到结果集之后，用户还不能将这些结果立即返回给用户，因为从用户的角度来看，这些结果中的相当多数都属于没有用的信息，只有少量的信息对用户有价值，所以这些信息应该在返回给用户的结果集的前n位出现。评价一个网页应该在返回结果集中的位置由很多因素决定，比如查询词在某篇文档中出现的频率、出现的位置、网页重要性评价等，具体的算法在本章“相关排序”一节中讨论。

(3)动态摘要。搜索引擎给出的结果是一个有序的条目列表，每一个条目有三个基本的元素：标题、网址和摘要。其中的摘要需要从网页正文中生成。当用户输入某个查询时，一般希望摘要中能够突出显示和查询直接对应的文字，希望摘要中出现和查询词相关的句子。因此，生成摘要通常采用“动态摘要”方式，即在响应查询时，根据查询词在文档中的位置，提取周围的文字，在显示时将查询词高亮度显示。这是目前大多数搜索引擎采用的方式。在实际工作中，索引文件不仅要记录每个关键词在每篇文档中出现与否，还要记录出现的位置和出现频率等信息。有了这些信息，我们就可以和上文中提及的ParseText文件配合使用，根据实际需要(如关键词前后显示多少文本文字，摘要中显示多少关键词)得到相应的动态摘要。

(4)网页快照。目前几乎所有的大型搜索引擎都提供“网页快照”服务，其目的是使用户在网络无法联通要察看的网页的情况下通过“网页快照”也可以看到要访问的网页内容，但是这里看到的网页内容并不是实际上最新的，而是通过还原在抓取网页时获取的HTML源代码而得到的“旧”网页。在Nutch中，用户通过点击某个网页的“网页快照”链接，将这篇文档的docID和segment目录位置发送到服务器端，从相应目录下的Content文件中还原出以前的网页，形成网页快照返回给用户。

7.2链接分析

尽管Web页面的情况比传统信息检索面对的情况要复杂许多，但其中的复杂性也给我们带来了新的机会。这主要体现在两个方面：首先可以利用网页间的链接关系进行链接分析，量化网页信息；其次，在Web查询模式下产生了许多新的信息可资利用，如Web用户行为信息等。

从开发利用的角度看，网页和普通文本的不同主要反映在两个方面：HTML标签和网页之间的超链接。

(1)HTML设计通常采用丰富的标签，这是网页作者用来将网页的不同部分以不同的形式呈现给用户的手段，包括文字的布局，字体、字号的变化等。因此，标签能给我们提示其中文字的重要程度。例如，在同一篇文字中，比较大的字体往往是作者比较强调的内容；而对于在同一网页内容分块且有一定布局的文字，放在前面和中间的应该是作者比较强调的，等等。一般搜索引擎都在网页的预处理阶段记录了这些信息，并用于结果排序。

(2)链接反映的是网页之间形成的“参考”、“引用”和“推荐”关系。若一篇网页被较多的其他网页链接，则它相对较被人关注，其内容应该是较重要或者较有用。因此，可以认为一个网页的“入度”是衡量它重要程度的一种有意义的指标。这和科技论文的情况类似，被引用较多的就是较好的文章。同时，人们注意到，网页的“出度”对分析网上信息的状况也很有意义，因此可以考虑同时用两个指标来衡量网页。这些想法就是斯坦福大学Google研究小组和IBM公司的Clever系统开发小组几乎在同一时间分别提出的著名的PageRank技术和HITS技术的基础。7.2.1PageRank

PageRank是Google公司创始人LarryPage和SergeyBrin在就读于斯坦福大学研究生院时提出的一种算法，它基于“从许多优质网页链接过来的网页，必定还是优质网页”的思想判定所有网页的重要性，并有效地利用了Web所拥有的庞大链接构造的特性。

从网页A导向网页B的链接被看做对页面A对页面B的支持投票，Google根据这个投票数来判断页面的重要性。可是Google不仅仅只看投票数(即链接数)，对投票的页面也进行分析。“重要性”高的页面所投的票的评价会更高，因为接受这个投票的页面也会被认为是“重要的页面”。一个网页的排名是由链接向它的那些网页的排名决定的，而那些网页的排名又由链接向它们的网页排名决定。因此，一个网页的PageRank总是递归地由其他网页的PageRank值决定，任何网页都对其他网页造成排名的影响，PageRank的计算实际上最终归结于整个网络的结构。

PageRank还可以用一种“随机冲浪”模型[17]来定义，如图7-5所示。该模型描述网络用户对网页的访问行为，网络用户可以被看成是一个随机冲浪者，因为用户一般随机选择一个网页作为上网的起始网页，看完这个网页后，从该网页内所含的超链接内随机地选择一个页面继续进行浏览，沿着超链接前进了一定数目的网页后，用户对这个主题感到厌倦，重新随机选择一个网页进行浏览，如此反复。由“随机冲浪”模型我们可以知道，每个网页可能被访问到的次数越多就越重要，这样的“可能被访问的次数”也就定义为网页的权值：PageRank值。图7-5随机冲浪模型示意图

1．PageRank概念模型

每个网页都有一些正向链接(出链)和反向链接(入链)，PageRank就是利用网页的正向、反向链接来衡量其重要性的。我们不可能找到一个网页的所有反向链接，但我们可以知道它的所有正向链接。

网页的反向链接值可以有很大的差异，例如，某著名网页的主页有62804个反向链接，而普通网页一般只有几个。通常地，我们认为反向链接数大的网页要比反向链接数小的网页重要，但简单的只对反向链接进行的引用计算并不符合直观上对重要性的认识。例如，如果一个网页只有一个来自政府权威网站主页的入链，虽然它的反向链接数仅为1，但它却是非常重要的网页，应该比那些反向链接数较大但来历不明的网页排名更靠前。PageRank尝试仅从链接结构取得“重要性”的近似值。

Larry和Sergey在文献[19]中给出的PageRank定义是：如果一个网页的所有反向链接的PageRank值之和高，则该网页的PageRank值也高。这就表明，高PageRank值的网页要么有很多反向链接，要么反向链接数少，但反向链接的PageRank值都很高。

设u为一个网页，Fu为u的正向链接集，Bu为u的反向链接集，Nu=|Fu|为u的出度，c为规范化因子，c的引入是为了使得所有网页的总PageRank值是个常数。

从PageRank的概念模型出发，有如下的简单的PageRank计算公式：

(7-1)由式(7-1)我们可以看到，一个网页的PageRank值被平均地分配到它的所有正向链接中，图7-6是用式(7-1)对PageRank进行简单计算的例子。

图7-6中，网页A的PageRank值为100，有两个出度，每个出度为下游网页带去100/2=50的PageRank值；网页C的PageRank值为6，有两个出度，每个出度为下游网页带去6/2=3的PageRank值；网页B有两个入度，分别是从A和C而来，正是A和C的下游网页，其PageRank值为A和C带来的PageRank值之和：50+3=53。图7-6PageRank的简单计算示意图

2．PageRank的计算方法

上一节给出了PageRank的简单概念模型，这一节介绍PageRank的具体计算公式，本节的例子主要来自网站(pr.efactory.de)[20]。下面是LarryPage和SergeyBrin给出的PageRank最初的算法，这个算法考虑网页的所有反向链接的PageRank值，如式(7-2)所示：(7-2)式中：PR(A)是网页A的PageRank值；PR(Tn)是链接向网页A的网页Tn的PageRank值；C(Tn)是网页Tn的出度；d是阻尼因子，取值范围为0~1，一般取为0.85[17]。由式(7-2)我们可以知道，PageRank不是对整个网站进行排序，而是对每个网页分别计算的，而每个网页的PageRank值是由那些链接到网页A的网页递归计算出来的。另外，链接到A的网页Tn的PageRank值并不是均一的，它们受到各自出度C(Tn)的影响，这意味着Tn的出站链接越多，A从Tn受惠的PageRank值就越少，这也正符合上一节所说的“网页的Rank值被平均地分配到它的所有正向链接中”。

【例7-1】

考虑一个只包含3个网页A，B和C的小网络，它们之间的链接关系如图7-7所示，此处设阻尼系数d为0.5，试计算每个页面的PR值并作分析。图7-7小网络的PageRank解：按照公式(7-2)得到如下方程：

PR(A)=0.5+0.5PR(C)

PR(B)=0.5+0.5(PR(A)/2)

PR(C)=0.5+0.5(PR(A)/2+PR(B))

对以上三元一次方程进行求解，解得：PR(A)=14/13=1.08，PR(B)=10/13=0.77，PR(C)=15/13=1.15。

由上面的计算可以知道，所有页面的PageRank之和等于3，即等于网络中的页面总数，这是一个普遍的现象，在进行PageRank计算时，我们可以用它来验证结果是否正确。对于PageRank算法，LarryPage和SergeyBrin还给出了一种简单直观的解释，他们将PageRank视作一种用户行为模型，用户不关心网页内容而随机点击链接，而网页的PageRank值则决定了用户随机点击访问到这个页面的概率，这也是一个页面的PageRank值不能完全通过链接传给另一个页面，而只能使其受惠PR(Ti)/C(Ti)的原因。因此，一个页面通过随机冲浪到达的概率就是链入它的页面的链接被点击的概率之和，另外，阻尼系数d减小了这个概率，阻尼系数的引入，是因为用户不可能无限地点击链接，常常随机跳入另一个页面。阻尼系数d定义为用户不断随机点击链接的概率，它取决于点击的次数，取值范围在0到1之间，d的值越高，继续点击链接的概率就越大。因此，用户停止点击并随机冲浪到另一个页面的概率在式子中用常数1－d表示，即随机冲浪到另一个页面的概率总是1－d，1－d本身也是页面所具有的PageRank值。

LarryPage和SergeyBrin在论文中[17]给出了PageRank的第二种计算公式：(7-3)其中，N是所有网页的总数，第二种算法和第一种算法实际上并没有什么本质区别，但在随机冲浪模型中，第二种算法的PageRank是用户在点击了许多链接后到达该网页的概率值，所以所有网页的PageRank值之和为1。在实际计算中可采用一种近似的迭代方法来计算各个网页的PageRank值[21]。先给每个网页分配一个初始值，然后利用上面的PageRank计算公式，循环进行有限次运算得到网页的近似PageRank值，根据LarryPage和SergeyBrin公开发表的文章，他们实际需要进行100次迭代才能得到整个互联网的PageRank值。表7-3是例7-1中的3个网页例子的迭代过程。从表7-3我们看到，通过迭代的计算，所有网页的PageRank总和收敛于网页总数，所以网页PageRank的平均值为1，最小值为1－d，而最大值为dN+(1－d)。

3．影响PageRank的因素

影响PageRank的因素很多，包括入链、出链和阻尼因子等。下面具体讨论各种因素对PageRank值的影响。为了可比较，以下的算法都是基于第一种算法即公式(7-2)来计算的。

(1)入链。前面的章节已经介绍过，对于一个网页来说，反向链接数越大，PageRank值就会越高，因此，入链的增加，会提高网页的PageRank值。回顾公式(7-2)，也许读者会认为增加一个入链X，页面A的PageRank值会增加d×PR(X)/C(X)，其中PR(X)是页面X的PageRank值，而C(X)是它的出链数。这个结果看起来是正确的，但实际上，A也链接到其他网页，因此，这些网页也会从中受惠，如果这些网页又链接回A，则A的PageRank值会因此又增加，下面用一个例子说明这种情况。

【例7-2】如图7-8所示，有一个包含4个网页A，B，C，D的网络结构，它们之间构成环形链接，没有任何外部网页链接到它们中的任何一个网页，因此，它们的PageRank值均为1，现在增加一个网页X链接到A，PR(X)为10，假定阻尼因子为0.5，试计算各页面的PR值，并分析入链的影响。图7-8入链对PageRank的影响解：可得到下面的方程：

PR(A)=0.5+0.5(PR(X)+PR(D))=5.5+0.5PR(D)

PR(B)=0.5+0.5PR(A)

PR(C)=0.5+0.5PR(B)

PR(D)=0.5+0.5PR(C)

由以上方程，我们得到的最终结果是：通过上面的例子我们可以看到，增加一个入链X的最初影响可以通过如下公式计算得到：

这个影响会顺着链接扩散，最终给4个网页的PageRank都带来放大的效果。

(2)阻尼因子。阻尼系数越大，页面PageRank的收益就越大，且整个回路上都能获得更大的收益(即入链收益能

更平均地分布到各个回路页面上)。针对例7-2，将阻尼系数改为0.75，则有：

PR(A)=0.25+0.75(PR(X)+PR(D))=7.75+0.75PR(D)

PR(B)=0.25+0.75PR(A)

PR(C)=0.25+0.75PR(B)

PR(D)=0.25+0.75PR(C)解得：

PR(A)=11.97，PR(B)=9.23

PR(C)=7.17，PR(D)=5.63

可以看到，入链X对A一个显著增加的初始影响，如下所示：这个影响导致页面A的PageRank几乎增加了一倍。而且当d=0.5时，A的PageRank是D的4倍，但当d=0.75时，A的PageRank值仅是D的2倍多。所以，随着阻尼因子的增大，入链的影响将从接收入链的网页向整个站点的其他网页偏移。

(3)出链。由于PageRank是基于整个网络结构来计算的，因此，出链的改变必然也会对网页的PageRank带来

影响。

【例7-3】如图7-9所示，有两个站点，分别由两个网页组成(A与B，C与D)，开始时没有互相链接，则各自的PageRank值为1，下面增加从A到D的链接，设d=0.75，试计算各页面的PR值，并分析出链的影响。图7-9出链对PageRank的影响解：根据图7-9，可得如下公式：

PR(A)=0.25+0.75PR(B)，PR(B)=0.25+0.375PR(A)

PR(C)=0.25+0.75PR(D)，PR(D)=0.25+0.75PR(C)+0.375PR(A)

上述方程的解为可见第一个站点的PageRank总值为25/23，小于2；第二个站点总值为67/23，大于2，而两个站点形成的总PageRank值为92/23＝4。所以，增加链接对整个Web的PageRank值无影响，而且一个站点的PageRank的损失必定被另一个网站所获得。

(4)网页数量。由于网络上所有累加的网页PageRank值之和等于网页的总数，因此很容易想到增加网页数量会对

所有网页的PageRank值有影响，但问题远不止这么简单，下面的例子说明了这个问题。

【例7-4】

计算图7-10中各网页的PageRank值，已知PR(X)＝10，d=0.75。图7-10网页数量对PageRank的影响解：根据图7-10(a)，可以得到如下方程：

PR(A)=0.25+0.75(10+PR(B)+PR(C))

PR(B)=PR(C)=0.25+0.75解上述方程得：在增加一个页面D后，网络变为图7-10(b)，相应的方程变为：PR(A)=0.25+0.75(10+PR(B)+PR(C)+PR(D))PR(B)=PR(C)=PR(D)=0.25+0.75解上述方程得：可以看到，网页增加后，总的PageRank值并没有明显增加，上例从33变为34，但几乎每个页面的PageRank值减小了(除了A)，这是由于新加的页面分享了入链X带来的PageRank值。

(5)悬摆链(DanglingLinks)。当一个页面没有出链时，它的PageRank值不会传递给别的页面，Page和Brin把这样页面的链接称为悬摆链，如图7-11所示。图7-11悬摆链示意图

【例7-5】

计算图7-11中各网页的PageRank值。假设d=0.75。

解：页面A和页面B互相链接，页面A还链接到页面C，但页面C没有链接到其他任何网页，所以A到C的链接为悬摆链，从这个网络图得到如下方程：

PR(A)=0.25+0.75PR(B)

PR(B)=0.25+0.375PR(A)

PR(C)=0.25+0.375PR(A)

解上述方程可得：可见，3个网页的PageRank值之和为36/23，差不多是3的一半，悬摆链带来负面的影响。据Page和Brin称，Google的索引中悬摆链的数目非常大，主要是由于受到robot.txt的限制及索引了一些没有链出的文件类型如pdf等。

为了消除这种负面影响，Google在计算PageRank时，将此类链接从数据库里去掉，在计算完毕后，再单独计算悬摆链所链到的页面。比如还是上一个例子，可先从数据库中删掉页面C，如图7-12所示，从而A和B各有PageRank值1，完成计算后，C被赋予PageRank值：0.25+0.375PR(A)=0.625。尽管如此，最终累加起来的PageRank值仍不等于网页数量，但至少把悬摆链造成的负面影响降低了不少。而有时候去掉一个网页会出现另一个新的悬摆链，因此，删除网页的步骤应该是迭代进行的，如图7-13所示。图7-12消除悬摆链的影响图7-13消除悬摆链的影响迭代过程虽然影响PageRank的因素有很多，但Ng等人的研究[22]表明链接分析具有一定的稳定性，拓扑结构的微小变化不会导致查询排序结果的重大改变。7.2.2HITS

HITS(Hypertext-InducedTopicSearch)[23-24]是由康奈尔大学(CornellUniversity)的JonKleinberg博士于1998年首先提出的，它是IBM公司阿尔马登研究中心(IBMAlmadenResearchCenter)的名为“CLEVER”的研究项目中的一部分。

Kleinberg认为搜索开始于用户的检索提问，每个页面的重要性也依赖于用户的检索提问，他将用户检索提问分为3种：特指主题检索提问(SpecificQueries，也称窄主题检索提问)、泛指主题检索提问(Broad-TopicQueries，也称宽主题检索提问)和相似网页检索提问(SimilarQueries)。HITS算法专注于改善泛指主题检索的结果。

Kleinberg将网页分为两类，即权威网页(authority)和中心网页(hub)。权威网页是具有较高价值的网页，依赖于指向它的页面，而中心网页是指向较多权威网页的网页，依赖于它所指向的页面。因此，每个页面可以用两个级别的值来衡量，即hub值和authority值。HITS算法的目标就是通过一定的迭代计算方法得到针对某个检索提问的最具价值的网页，即排名最高的权威网页。

1．HITS算法思想

HITS算法的基本思想是建立一个与查询式有关的图，叫主题子图(FocusedSubgraph)。如图7-14所示。图7-14主题子图假设给出一个泛指主题的查询串a，构造主题子图的过程如下：

(1)用基于文本的搜索引擎得到某一查询的结果集合R，称为根集(RootSet)；

(2)将R所指向的网页集合以及其他指向R的网页集合包含进来形成集合S，称为基本集合(BaseSet)。

为了控制该图的节点数量，在下面两点上施加控制：首先因为从搜索引擎返回结果的数量一般很大，所以有必要将其限制在一个小的范围t内，如设置t为200；其次某个网页的链入网页的数量也可能很大，所以将其限制在一个给定的范围d内，如设置d为50。同时，为了消除那些纯粹是导航用链接的影响，需要删除站内链接(即超链接的链源和链宿都在同一个主机上)。在构造完主题子图之后，我们可以通过一种迭代算法来计算出网页的authority值和hub值。

2．HITS算法过程

由于权威网页和中心网页有一种相互加强的关系，即具有较高hub值的网页应该指向较多的高authority值的网页，而高authority值的网页应该被多个高hub值的网页所指向。假定有网页i，令ai为其authority值，hi为其hub值，B(i)为网页i的反向链接集，F(i)为i的正向链接集，则有：(7-4)对于图7-15的例子，根据公式(7-4)，页面1的authority值和hub值分别为

a1=h2+h3+h4

h1=a5+a6+a7图7-15直观表示示意图下面对算法的实现流程进行介绍。

每一个页面p，被赋予一个非负的authority值ap和一个非负的hub值hp，ap和hp值越大，其网页的权威级别和中心级别就越高。事实上，存在这样的关系：如果网页指向了很多较高authority值的页面，那么它应该被赋予更高的hub值；同样，如果p被具有很多较高hub值的页面所指向，那么它应该被赋予较高的authority值。

基于如上权值的概念，定义两种操作：I操作和O操作。I操作被定义来计算authority值，公式如下：

(7-5)

O操作被定义来计算hub值，公式如下：(7-6)需要对以上权值进行规范化。规范化authority值的公式：(7-7)

规范化hub值的公式：(7-8)这样可以迭代地进行I操作和O操作，直到最近两轮迭代的规范化authority值以及hub值的差异已经很小，则认为已收敛，即收敛时满足‖at－at－1‖+‖ht－ht－1‖<ε。

HITS迭代算法流程描述如下：输入：(G，k)，G是链接页面的集合，k是一个自然数

令z

表示矢量(1，1，1，…，1)∈Rn

a0:=z

h0:=z

While‖ai－ai－1‖+‖hi－hi－1‖<ε，do

对(ai－1，hi－1)应用I操作，获得新的ai′

对(ai′，hi－1)应用O操作，获得新的hi′

标准化authority值ai′，获得ai

标准化hub值hi′，得到hi

End

返回(ak，hk)最后可以将中心值最大的前C个网页和权威值最大的前C个网页作为最终的返回结果。

HITS算法处理的对象(Web网页)个数相对较少，一般也就在几万个以内，计算速度相对较快。因为它是面向查询的算法，对用户响应的时间要快，所以一般情况下只是求出方程组的次优解就可以了。在Kleinberg的实验中，循环迭代20次，就可使前C个(C取5~10之间)网页排序足够地稳定了。需要特别指出的是，因为一个网页本身有很多个不同的主题，这使得HITS算法的结果容易出现主题漂移(TopicDrift)和概念泛化(ConceptGeneralization)现象。例如，本来查询的是“物理”，但结果可能出现“数学”和“自然科学”等主题。为了使结果的主题单一化，很多学者利用了许多其他的文字信息来解决这个问题，如利用URL对应的锚文字、URL所在的上下文信息、URL本身的文字信息等等。

【例7-6】

针对图7-16所示的Web结构图，试计算每个网页的hub和authority值。图7-16HITS计算实例解：根据上图构造主题子图V＝{A，B，C}，邻接矩阵E＝{〈A，A〉，〈A，B〉，〈A，C〉，〈B，A〉，〈B，C〉，〈C，B〉}，表示为由此得到其转置矩阵为因此有：

初始化时，令aA=aB=aC=hA=hB=hC=1。第一次迭代，计算a值：

aA=2，aB=2，aC=2计算h值：

hA=6，hB=4，hC=2为简便计算，采用最大值的规范化方法。规范化a：

aA=1，aB=1，aC=1规范化h：继续迭代，直至收敛。最后：aA=1，aB=0.732，aC=1hA=1，hB=0.732，hC=0.2687.2.3算法比较

显而易见，PageRank和HITS都是基于链接分析的搜索引擎排序算法，并且均利用了特征向量作为理论基础和收敛性依据。但两种算法的不同点也非常明显：

(1)从算法思想上看，虽然均同为链接分析算法，但二者之间还是有一定的区别。HITS的原理如前所述，其authority值只是相对于某个检索主题的权重，因此HITS算法也常被称为查询依赖(QueryDependent)算法。而PageRank算法独立于检索主题，因此也常被称为查询独立(QueryIndependent)算法。PageRank的发明者Page和Brin把引文分析思想借鉴到网络文档重要性的计算中来，利用网络自身的超链接结构给所有的网页确定一个重要性的等级数。当然PageRank并不是引文分析的完全翻版，根据Web自身的性质等，它不仅考虑了网页引用数量，还特别考虑了网页本身的重要性。简单地说，重要网页所指向的链接将大大增加被指向网页的重要性。

(2)从权重的传播模型来看，HITS首先通过基于文本的搜索引擎来获得最初的处理数据，网页重要性的传播是通过hub页向authority页传递，而且Kleinberg认为，hub与authority之间是相互增强的关系；而PageRank则是基于随机冲浪模型，网页的重要性只是从一个authority页传递给另一个authority页。

(3)从处理的数据量及检索响应时间来分析。表面上看，HITS算法对需排序的网页数量较小，所计算的网页数量一般为1000~5000个，但由于需要从基于内容分析的搜索引擎中提取根集并扩充基本集，这个过程需要耗费相当长的时间。而PageRank算法表面上看，处理的数据数量上远远超过了HITS算法，但由于其计算在用户查询前已由服务器端独立完成，无需在每次查询时计算，因此从检索响应时间来看，PageRank算法比HITS要快很多。

7.3相关排序

相关排序的意思是在用户通过搜索引擎提交查询词后，搜索引擎系统按照一定的规则将结果集中的结果按照一定的策略进行排序的过程。

一般来讲，大型搜索引擎能够索引的网页一般都在以亿为单位的数量级上，用户在提交查询词后，往往都会得到很多(几万甚至几十万)结果，而在这些结果中，对用户真正有用的信息往往是小部分(几条或者几十条结果)，如果这些结果不作任何处理就返回给用户，用户将面对大量的无用信息。所以，一个好的搜索引擎系统都会采用一定的算法将用户最需要的结果放在前面。如何确定在大量的文档集中，对于某一组查询词，哪些文档可以排在最前面(最匹配)就是相关排序需要研究的内容。一般来讲，在确定结果集之后，会对每篇文档(或网页)给出一个分数，然后按照分数进行降序排列，将排序后的结果返回给用户。

相关排序的基础是信息检索模型，相关知识请参考本书第2章。在这里结合开源搜索引擎Nutch和其采用的索引和检索工具Lucene，具体介绍一下检索结果分数的计算以及排序过程。7.3.1Lucene检索模型

在第2章中，已经就布尔模型、向量模型、概率模型和其他扩展模型作了详细的介绍，Lucene采用向量模型作为其理论模型，把索引中的每个词作为空间的一个维度，把每一篇文档作为空间中的一个向量，把每一个查询也作为空间中的一个向量，通过计算文档和查询的余弦来表示文档和查询的相关程度，其计算文档和查询相关度的公式如下所示[25]，其中各项的意义与公式(2-8)相同。(7-9)其中，wk，i=tfk，i×idfk，wk，q=boostk×idfk，t表示查询集中关键词的数量，tfk，i表示关键词k在文档i中的权重，idfk表示关键词k在整个文档集中的逆文档频率，boostk表示关键词的权重，如下式：(7-10)(7-11)为了简化式(7-9)，令，fieldLength表示查询所在的域的长度，或者简单理解为某篇文档中查询范围内词汇的数量。这样一来，公式(7-9)可以写为：

其中，与文档无关，不会影响具体文档的排名。

当只有一个查询词时，上式又可以简化为：(7-12)(7-13)在实际应用中，Lucene在上式的基础上又增加了一个调整参数Boost，所以，式(7-13)可以表示为：(7-14)令或Boost=fieldBoost×doc.boost其中fieldBoost是域的加权因子，doc.boost是文档的加权因子。令queryWeight=fieldBoost×idfk×queryNormfieldWeight=tfk，i×idfk×fieldNorm因此可以得到如下的得分公式：

score(di,k)=sim(di,k)=fieldWeightk×queryWeightk

=(tfk,i×idfk×fieldNorm)×(Boostk×idfk×queryNorm)

(7-15)

这里的score表示的就是查询词与某篇文档的相关度，或者说，相关度越高的文档得分就越高，也就会排在结果集的前面。

当查询集中的查询词不止一个时，查询的结果就需要进行扩充，也就演化为(7-16)其中：(7-17)总结得分公式中的各因子的描述如表7-4所示。

【例7-7】

有3篇文档的内容如下：

Document1：广州华南理工大学争创国家一流大学

Document2：广州华南理工大学

Document3：广州华南理工大学计算机科学与工程学院

对这三篇文档建立索引后，求检索“大学”一词得到的排序。

解：首先对文档进行分词，得到的结果是：

Document1：广州华南理工大学争创国家一流大学

Document2：广州华南理工大学

Document3：广州华南理工大学计算机科学工程学院

令fieldBoost=1，doc.Boost=1，所以，3篇文档的fieldNorm分别为0.3125，0.5，0.3125。注意，这个结果与理论计算结果不同，是因为Lucene在计算时只使用1个字节存储fieldNorm，所以误差很大。

根据前述，可以得到一个简化公式：score=tfk，i×idfk×fieldNorm

(7-18)“大学”在3篇文档的tf分别是：1.414，1，1，在3篇文档的idf分别是0.7123，0.7123，0.7123，所以3篇文档的得分分别是0.3147，0.3561，0.2226。

查询的排序结果是：Document2>Document1>Document3。

【例7-8】

依然考虑上例中的3篇文档，求检索“大学”、“计算机”两词得到的排序。

解：从检索词和3篇文档分词后的结果可以得到：

coorddocument1=0.5idf大学=0.7123

coorddocument2=0.5idf计算机=1.4055

coorddocument3=1

tf大学，document1=1.414tf计算机，document1=0

tf大学，document2=1tf计算机，document2=0

tf大学，document3=1tf计算机，document3=1

所以，3篇文档的fieldNorm依然分别为0.3125，0.5，0.3125。

将上述数据代入公式(7-16)得到如下结果：

scoredocument1=0.0711

scoredocument2=0.0805

scoredocument3=0.4923

所以,查询的排序结果应该是：Document3>Document2>Document1。7.3.2Nutch排序算法

Nucth的排序算法是在Lucene的基础上进行的扩充，其核心算法依然使用Lucene的排序算法。

Lucene实际上可以为任何文档提供检索服务，HTML文档当然也可以被Lucene检索，但是，由于网页的特殊性，Nutch使用Lucene对网页进行索引和检索时采用了本身特有的策略，简单来讲，就是把一篇网页的不同部分保存在不同的索引域中，检索时对不同的索引域赋予不同的权重。

目前，Nutch中的常见做法是将url、anchor、title和content分别索引，它们的具体意义和权重设置参见表7-5。设用户对Nutch提交检索词之后，Nutch对每篇文档的评分为

score=score(url)+score(anchor)+score(title)+score(content)

(7-19)

其中：

score(field)=weight(field)

=fieldWeight(field)×queryWeight(field)

field∈{url，anchor，title，content}

式中，fieldWeight(field)和queryWeight(field)的意义与7.4.1中完全相同，field项决定fieldBoost的取值，具体取值参见表7-4。同时，Nutch在实现排序算法时对Lucene的算法进行了一些改动：coord=1

doc.Boost是具体某篇文档的权重，表示这篇文档的重要性，它与网页之间的链接关系有关，与具体的查询词无关。在通过某个查询词计算所有文档的得分时，doc.Boost相对较高的文档将会拥有较高的权重。根据不同的需要，可以对doc.Boost进行如下设置：

doc.Boost=1，或doc.Boost=PageRank，或doc.Boost=lnCount(inlink)

当doc.Boost=1时，所有文档都没有设置权重。

当doc.Boost=PageRank时，所有文档的权重就等于每篇文档的PageRank。

当doc.Boost=lnCount(inlink)时，所有文档的权重等于链入这篇文档的链接总数的自然对数。在以上三种情况中，第二种和第三种都可以反映文档的重要性，第一种则不具备这种能力。

构成fieldWeight和queryWeight的其他参数，如tf和idf的意义及算法都与Lucene中相同，此处不再赘述。

最后，通过一个实际的例子说明Nutch的排序过程。

【例7-9】

考虑一个由4个网页组成的网站，4个网页的HTML代码如下。求Nutch对这4篇文档建立索引后，检索football的结果。sports.html：

〈html〉

〈head〉

〈title〉SportsPage〈/title〉

〈/head〉

〈body〉

THISISTHESPORTSPAGEFORTEST〈br〉

〈ahref=“football.html”〉FOOTBALL〈/a〉〈br〉

〈ahref=“basketball.html”〉BASKETBALL〈/a〉〈br〉

〈ahref="golf.html"〉GOLF〈/a〉〈br〉

〈/body〉

〈/html〉football.html：

〈html〉

〈head〉

〈title〉FOOTBALLPage〈/title〉

〈/head〉

〈body〉

THISISTHEFOOTBALLPAGEFORTEST〈br〉

〈ahref="basketball.html"〉BASKETBALL〈/a〉〈br〉

〈ahref="golf.html"〉GOLF〈/a〉〈br〉

〈ahref="sports.html"〉SPORTSHOME〈/a〉

〈/body〉

〈/html〉basketball.html：

〈html〉

〈head〉

〈title〉BASKETBALLPage〈/title〉

〈/head〉

〈body〉

THISISTHEBASKETBALLPAGEFORTEST〈br〉

〈ahref="football.html"〉FOOTBALL〈/a〉〈br〉

〈ahref="golf.html"〉GOLF〈/a〉〈br〉

〈ahref="sports.html"〉SPORTSHOME〈/a〉

〈/body〉

〈/html〉golf.html：

〈html〉

〈head〉

〈title〉GOLFPage〈/title〉

〈/head〉

〈body〉

THISISTHEGOLFPAGEFORTEST〈br〉

〈ahref="football.html"〉FOOTBALL〈/a〉〈br〉

〈ahref="basketball.html"〉BASKETBALL〈/a〉〈br〉

〈ahref="sports.html"〉SPORTSHOME〈/a〉

〈/body〉

〈/html〉解：首先通过上文中介绍的Nutch的评分算法对文档进行分析，之后通过实际系统的运行结果对分析的算法进行验证。先以football.html为分析对象。

(1)对football各项进行分析。

url：httphttp-1271270018080footballhtml

title：footballpage

content：footballpagethisisis-thethethe-footballfootballpageforforfor-testtestbasketballgolfsportshome

anchor：football

注意：对于anchor，由于所有网页链接到这个网页的锚文本都是FOOTBALL，所以anchor的内容只有一个football；Lucene默认的分析器在进行分析时对停用词进行了处理，将停用词和非停用词作了一些组合。

(2)计算tf值。(3)计算idf值。

(4)计算queryNorm。

(5)计算fieldNorm。

(6)综合计算结果：

score(url)=queryWeight(url)×fieldWeight(url)

=fieldBoost(url)×idf(url)×queryNorm(url)×tf(url)

×idf(url)×fieldNorm(url)

=4×1.6931472×0.124622196×1×1.6931472×0.109375

=0.1563014

score(title)=queryWeight(title)×fieldWeight(title)

=fieldBoost(title)×idf(title)×queryNorm(title)×tf(title)

×idf(title)×fieldNorm(title)

=1.5×1.6931472×0.124622196×1×1.6931472×0.625

=0.3349316

score(content)=queryWeight(content)×fieldWeight(content)

=fieldBoost(content)×idf(content)×queryNorm(content)

×tf(content)×idf(content)×fieldNorm(content)

=1×0.7768564×0.124622196×1.4142135×0.7768564×0.03125

=0.003323854

score(anchor)=queryWeight(anchor)×fieldWeight(anchor)

=fieldBoost(anchor)×idf(anchor)×queryNorm(anchor)

×tf(anchor)×idf(anchor)×fieldNorm(anchor)

=2×1.6931472×0.124622196×1×1.6931472×0.75

=0.5358905

最后：

score=score(url)+score(title)+score(content)+score(anchor)

=0.1563014+0.3349316+0.003323854+0.5358905

=1.0304474

其余3个网页的得分也可以按照上述计算顺序来计算，此处省略。

图7-17是通过Nutch搜索football的排序结果，很明显，这个结果非常理想，需要的football主题文档如预期那样出现在了首位。打开结果旁边的评分详解，可以更加直观地了解Nutch如何评分排序，如图7-18所示。图7-17搜索结果图7-18评分详解这个评分过程是输入football查询词后对football.html文档的评分过程，具体评分细节与上文分析的完全一致。

7.4大规模搜索引擎

搜索引擎最主要的组成部分是网页抓取(信息的采集)、索引器(信息的处理、组织和存储)和检索器(信息的检索)，分别对应前面的三段式工作流程。首先，网络爬虫从网络上抓取海量的网页，保存在本地原始的数据库中；其次，索引器对原始数据库中的网页集进行预处理，包括网页去噪、关键词的提取，重复网页的消除，链接分析，建立索引等工作，这样就建立了系统的索引数据库；最后用户通过用户接口(如浏览器)与检索器进行交互，检索器根据用户