1、第7章 搜索引擎第7章 搜索引擎7.1概述7.2链接分析7.3相关排序7.4大规模搜索引擎7.5小结思考题第7章 搜索引擎7.1 概概 述述7.1.1 发展概况发展概况在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网指数速度的扩张，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大众信息检索需求的搜索引擎网站便应运而生了。现代意义上的搜索引擎的早期历史可以参看第1章1.3.1节，先后涌现出了Archie1、WAIS2-3、Gopher4、Wanderer5、ALIWEB6()、JumpStation7、The World Wide Web Worm8和Repositor
2、y-Based Software Engineering(RBSE)spider9等。第7章 搜索引擎1994年7月，卡耐基-梅隆大学(Carnegie Mellon University)的Michael Mauldin将爬虫程序接入到其索引程序中，创建了Lycos11()；同年4月，斯坦福大学(Stanford University)的两名博士生杨致远和David Filo共同创办了Yahoo(),并使搜索引擎的概念深入人心。在这个时期，以Yahoo、AltaVista()、Excite()、Infoseek()等搜索引擎为代表，各搜索引擎的开发设计力求在数据库覆盖范围、检索响应时间、检索
3、结果反馈、用户界面友好等方面有所突破。最初的搜索引擎采用分类目录的形式来组织Internet资源，如Yahoo和Excite等，按学科、字母顺序、时间先后、地理区域，或是这些方法的组合。这种方法的优点是资源结构清晰，符合人们的使用习惯，但必须花费大量的人力来搜集、组织信息，需要人工维护，内容覆盖范围有限等。随着网络信息的剧增，单纯依靠人工的方法来组织所有的信息资源已不大可能。第7章 搜索引擎1998年9月，斯坦福大学的两个博士生Larry Page 和 Sergey Brin创建了Google，这标志着新一代的搜索引擎出现了。Google搜索引擎通过估算反馈网页质量及相关程度来决定排名次序，搜
4、索结果的排名与网页质量有密切的关系，因为人们一般不会关注低质量的网页。这种搜索技术可以让用户尽可能获得好的搜索结果和良好的用户体验，因此也使得搜索引擎进一步走向了实用性，成为网络上最关键的应用之一。第7章 搜索引擎目前，互联网上的搜索引擎非常多，呈现百花齐放的局面，如MSN()、Overture()、LookSmart()、HotBot()，以及最大的中文搜索引擎百度()等。其检索的信息量也与日俱增。目前全球最大的搜索引擎Google()，已可索引和检索80多亿网页，而2008年面世的搜索引擎Cuil()，号称可索引和检索1000多亿网页，百度也号称超过10亿个索引页面。第7章 搜索引擎选择多
5、了，对用户来说也是一件难事。每个搜索引擎都有它自己的特点和长处，是否可以集众搜索引擎之所长，来更好地满足用户的需求？元搜索引擎(Meta Search Engine)就是一种集成化的检索软件，通过多个成员搜索引擎提供的服务向用户提供统一的检索服务，如Metacrawler()、Savysearch()等元搜索引擎，主要目的是综合各种搜索引擎的长处，尽量减少用户的检索过程，提高检索效率。按照索引方式的不同，搜索引擎可分为以下3种类型，这3种类型都有各自的特点和代表。第7章 搜索引擎1 机器人搜索引擎机器人搜索引擎由信息搜集系统(Crawler)自动在互联网中搜集和发现信息，由索引器(Indexe
6、r)建立索引，由检索器(Searcher)根据用户的查询检索索引库，并将结果按一定的排列顺序返回给用户。机器人搜索引擎的最大特点是可以自动采集和更新信息，信息量大，且不需要人工干预，目前流行的搜索引擎大多属于此类。但机器人搜索引擎也有缺点，如返回的信息过多，且存在大量不相关的信息，用户必须在结果中筛选。Google和百度都属于机器人搜索引擎。第7章 搜索引擎2 目录搜索引擎目录搜索引擎与机器人搜索引擎完全不同的是，目录搜索引擎通常以人工方式或半自动方式搜集信息，由编辑员审核信息，人工形成信息摘要，并将信息置于事先确定的分类框架中，提供目录浏览和直接检索。目录索引虽然有搜索功能，但在严格意义上不
7、算是真正的搜索引擎，仅仅是按目录分类的网站链接列表而已。用户完全可以不用进行关键词查询，仅靠分类目录也可找到需要的信息。目录式搜索引擎的特点是信息准确，导航质量高，但需要人工介入，维护的工作量较大，且信息量少，更新不及时。比较著名的目录索引搜索引擎有Yahoo、Open Directory Project(DMOZ，http:/dmoz.org)和LookSmart等。第7章 搜索引擎3 元搜索引擎元搜索引擎元搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行去重、重新排序等处理后，作为自己的结果返回给用户。元搜索引擎的特点是返回的信息量更大、更全，但用户也因
8、此需要做更多的筛选。著名的元搜索引擎有Dogpile()、Vivisimo()等。在搜索结果排列方面，有的直接按来源引擎排列搜索结果，如Dogpile，有的则按自定的规则将结果重新排列组合，如Vivisimo。第7章 搜索引擎7.1.2 术语与定义术语与定义搜索引擎实际上是一个网络应用软件系统，它能够接受用户通过浏览器提交的查询词或者短语，例如“汶川地震”、“奥运会”、“春晚”等等，并在可以接受的时间内返回一个和该用户查询匹配的网页列表，列表的每一条目至少包括标题、网址链接和摘要等信息。下面给出搜索引擎的一些相关术语介绍。超链接：超链接是联系两个网页的结构化单位，如图7-1所示，网页间的这种联
9、系通过在源网页(Source Page)的指定位置处插入一个超链接来实现，超链接包含了目标网页(Destination Page)的URL12。第7章 搜索引擎图7-1 超链接示意图第7章 搜索引擎链接分析(Link Analysis)：链接分析是对网页之间链接方式的分析，通过这种分析，我们可以提取出网络拓扑结构图的一些有用信息，可以分析某个网站的拓扑结构、声望和分类等，从而实现辅助检索的目的。反向链接和正向链接(Inlink&Outlink)：如果网页A有超链接指向网页B，则称网页B有一个来自A的反向链接“inlink”链入，同时，称网页A有一个正向链接“outlink”链出到B，如图7-2
10、所示，网页C有两个反向链接，分别来自A和B，A和B则分别有一个正向链接，都指向C。第7章 搜索引擎图7-2 正向链接、反向链接示意图第7章 搜索引擎入度和出度(Number of Inlink&Outlink)：网页的反向链接的个数称为网页的入度，网页的正向链接的个数称为网页的出度。锚文本(Anchor Text)：锚文本即链接文本，它概括了所指向的网页的主题，而这种概括通常要比该网页自身的描述还要准确。例如，在个人网站上把中央电视台()作为新闻频道的链接，访问者通过点击网站上的“新闻频道”就能进入中央电视台网站，那么“新闻频道”就是中央电视台网站首页的锚文本。锚文本还可以指向一些普通的搜索引
11、擎不能索引的文件，如图像、程序和数据库文件等。第7章 搜索引擎信息摘要(Summary)：信息摘要是指对网页信息内容进行概括，不加评论和补充解释，简明准确地提取主要内容而形成的短文。网页快照(Snap Shot)：搜索引擎在收录网页时，都会做一个备份，大多是文本的，保存了该网页的主要文字内容，这个备份称为网页的快照。当被访网页被删除或者连接失效时，用户可以使用网页快照来查看这个网页的主要内容，由于快照以文本内容为主，访问速度比对应网页要快。搜索引擎类别各异，但基本架构是类似的，也就是说，它们一般都具有以下这些模块。爬行程序(Crawler)：通过评估链接或者预定义的地址来发现网页。主要工作是下
12、载网页，并分析网页源码，发现网页上的所有链接，并决定网络爬虫的爬行方向。第7章 搜索引擎索引器(Indexer)：索引器解析每个网页，并分析不同的元素，如文本、头、结构或格式特征、特殊的HTML标签等，形成特殊的数据结构存入索引库中。索引库(Indexing Database)：搜索引擎所下载和分析的数据的存储区域，也称为搜索引擎的数据库。结果引擎(Results Engine)：结果引擎从索引库中提取信息，并负责对结果排序。它基于搜索引擎的排序算法(Ranking Algorithm)，决定哪些网页与用户的查询最吻合，而且应以什么样的顺序排列。第7章 搜索引擎检索服务器(Query Serv
13、er)：检索服务器实际上是一个web服务器，检索界面是一个包含输入框的HTML页面，用户可以在输入框内输入感兴趣的检索词，检索服务器还负责将用户查询的结果转换为HTML页面。PageRank：简称PR，PageRank18是Google衡量网页重要性的工具，测量值范围为110，分别表示某网页的重要性。在Google工具栏可以随时获得某网页的PageRank值。不同搜索引擎的实现机制可能是不同的。例如，Spider、Crawler和Indexer可能总共由一个程序完成，完成网页的下载、分析和利用其链接发现新的资源，然而，这些模块都是搜索引擎所必有的。第7章 搜索引擎7.1.3 工作原理工作原理现
14、代大规模高质量搜索引擎一般采用如图7-3所示的称为三段式的工作流程13，即网页收集、预处理和查询服务。图7-3 搜索引擎三段式工作流程第7章 搜索引擎其中收集阶段主要进行网页的批量搜集，增量式搜集；预处理阶段则进行关键词的提取，重复网页的消除，链接分析，建立索引等工作；查询服务则采用不同的查询方法对用户的查询关键词与索引库进行匹配，将得到的结果生成信息摘要，并按照一定的顺序输出给用户。这些工作在前面的章节均有介绍。下面以开源软件项目Nutch14为例介绍一个搜索引擎的工作原理。Nutch是 Apache15开源组织的子项目，是一个开源搜索引擎系统。Nutch能够提供Web网页和FTP站点等资源
15、的抓取和检索服务；可以对html、doc、pdf和text等多种格式的文本进行解析和存储。第7章 搜索引擎Nutch采用了插件的开发模式，使整个系统具有非常好的可扩展性。图7-4所示就是Nutch的系统结构，图中的数据模块以及一些意义描述见表7-1。Nutch的系统工作原理依然可以采用三段式工作流程来描述。Nutch搜索引擎的工作大体按照以下流程进行。第7章 搜索引擎图7-4 Nutch的系统结构第7章 搜索引擎第7章 搜索引擎1.数据搜集数据搜集Nutch搜索引擎系统的爬虫(Crawler)是一个增量式的爬行系统，其工作原理是通过对第n轮爬行抓取的网页进行解析，得到新的URL链接地址，并丰富
16、现有的URL库，这个URL库将是第n+1轮抓取网页的基础。选择第n+1轮需要抓取哪些网页也是有一定策略的，根据是否是新网页、网页内容更新频率、URL深度等信息确定即将采集的网页URL集合。在Nutch中，系统在Web DB中选择需要采集的URL地址，将这些地址放入一个新的Segment目录的fetchlist文件中。网页采集模块根据fetchlist中的URL列表，对相应的URL发送HTTP请求，下载相应的网页，并保存于上文介绍过的Fetcher、Parse Data、Parse Text和Content文件中。第7章 搜索引擎2.数据预整理数据预整理数据整理可以分成两个阶段，第一个阶段是对采
17、集回来的数据存储和分析，第二阶段是建立索引。(1)数据分析。爬虫程序在网络中抓取的数据，根据不同的需要，将数据分别保存于Fetcher、Content、Parse Data、Parse Text文件中。在这些文件中，不仅仅包含抓取的网页的基本信息，而且包括抓取网页的状态信息、网页之间的连接信息、HTTP协议信息等等。大量试验表明，返回用户查询结果所依赖的索引(Index)文件中，如果仅仅包含网页文档信息，这个结果就是很不理想的，并且会受到很多噪声信息的影响；一个好的索引文件中至少要包括网页的重要性信息、网页之间的链接信息、单个网页的内容信息、单个网页的题目(Title)和URL等等。尤其前两者
18、反映了网页与网页之间的链接拓扑，是两个非常重要的信息。数据分析的目的也在于将这两个信息提取出来。第7章 搜索引擎(2)建立索引。Nutch使用开源索引系统Lucene16对文档进行索引。对于每篇文档，至少包含如表7-2所示的索引域(Field)。第7章 搜索引擎第7章 搜索引擎在明确了需要什么样的数据之后，就可以建立索引了。但是中文和英文不同，不同的语义单元不是自然间隔的，而需要使用一定的策略将中文文本切分成一个个词汇，这个步骤一般称为“分词”或“切词”。“分词”的基础在于开发者需要拥有一个丰富的“词典”，用分词程序从网页文字中分出“词典”所含的词语来。一般来讲，通过分词可以得到很多词，同一个
19、词可能在一篇网页中多次出现。从效果(effectiveness)和效率(efficiency)两方面考虑，不应该让所有的词都出现在网页的表示中，要去掉诸如“的”、“了”等没有内容指示意义的停用词。第7章 搜索引擎上文中提到的9个索引域中的content、anchor、title 3个索引域的内容要先经过中文分词再写进索引文件。如第4章所述，索引文件的工作原理是通过某些关键词能够迅速定位到出现这个关键词的某篇文档。Nutch采用倒排索引机制，将海量网页文档排序顺序存储的同时，建立排好序的关键词列表(倒排表)，用于存储“关键词到文档”的映射关系，并利用这样的映射关系建立索引。第7章 搜索引擎3.检
20、索服务检索服务检索与索引是两个相关的过程，索引的实质是建立关键词与文档映射的倒排表的过程，检索是通过倒排表和关键词读取相应的文档的过程。(1)查询。一般来讲，系统面对的是查询短语。就英文来说，它是一个词的序列；就中文来说，它是包含若干个词的一段文字。一般地，我们用q0表示用户提交的原始查询，例如，q0=“华南理工大学”。首先需要“分词”，即把它分成一个词的序列。如上例，则为“华南 理工 大学”。然后需要删除那些没有查询意义或者几乎在每篇文档中都会出现的词(例如“的”)，最后形成一个用于参加匹配的查询词表，q=t1，t2，tm，在本例中就是q=华南，理工，大学。第7章 搜索引擎倒排文件是上文中提
21、到的索引文件，它保存了关键词与出现该关键词的文档的对应关系，显然，q中的词必须是包含在倒排文件词表中才有意义。有了这样的q，它的每一个元素都对应倒排文件中的一个置入文件表，记作 (ti为查询词)，它们的交集或并集即为对应查询的结果文档集合，从而实现了查询和文档的匹配。上述过程的基本假设是：用户希望结果网页包含所输入的查询文字。itL第7章 搜索引擎(2)排序。在得到结果集之后，用户还不能将这些结果立即返回给用户，因为从用户的角度来看，这些结果中的相当多数都属于没有用的信息，只有少量的信息对用户有价值，所以这些信息应该在返回给用户的结果集的前n位出现。评价一个网页应该在返回结果集中的位置由很多因
22、素决定，比如查询词在某篇文档中出现的频率、出现的位置、网页重要性评价等，具体的算法在本章“相关排序”一节中讨论。第7章 搜索引擎(3)动态摘要。搜索引擎给出的结果是一个有序的条目列表，每一个条目有三个基本的元素：标题、网址和摘要。其中的摘要需要从网页正文中生成。当用户输入某个查询时，一般希望摘要中能够突出显示和查询直接对应的文字，希望摘要中出现和查询词相关的句子。因此，生成摘要通常采用“动态摘要”方式，即在响应查询时，根据查询词在文档中的位置，提取周围的文字，在显示时将查询词高亮度显示。这是目前大多数搜索引擎采用的方式。在实际工作中，索引文件不仅要记录每个关键词在每篇文档中出现与否，还要记录出
23、现的位置和出现频率等信息。有了这些信息，我们就可以和上文中提及的Parse Text文件配合使用，根据实际需要(如关键词前后显示多少文本文字，摘要中显示多少关键词)得到相应的动态摘要。第7章 搜索引擎(4)网页快照。目前几乎所有的大型搜索引擎都提供“网页快照”服务，其目的是使用户在网络无法联通要察看的网页的情况下通过“网页快照”也可以看到要访问的网页内容，但是这里看到的网页内容并不是实际上最新的，而是通过还原在抓取网页时获取的HTML源代码而得到的“旧”网页。在Nutch中，用户通过点击某个网页的“网页快照”链接，将这篇文档的docID和segment目录位置发送到服务器端，从相应目录下的Co
24、ntent文件中还原出以前的网页，形成网页快照返回给用户。第7章 搜索引擎 7.2 链接分析链接分析尽管Web页面的情况比传统信息检索面对的情况要复杂许多，但其中的复杂性也给我们带来了新的机会。这主要体现在两个方面：首先可以利用网页间的链接关系进行链接分析，量化网页信息；其次，在Web查询模式下产生了许多新的信息可资利用，如Web用户行为信息等。从开发利用的角度看，网页和普通文本的不同主要反映在两个方面：HTML标签和网页之间的超链接。第7章 搜索引擎(1)HTML设计通常采用丰富的标签，这是网页作者用来将网页的不同部分以不同的形式呈现给用户的手段，包括文字的布局，字体、字号的变化等。因此，标
25、签能给我们提示其中文字的重要程度。例如，在同一篇文字中，比较大的字体往往是作者比较强调的内容；而对于在同一网页内容分块且有一定布局的文字，放在前面和中间的应该是作者比较强调的，等等。一般搜索引擎都在网页的预处理阶段记录了这些信息，并用于结果排序。第7章 搜索引擎(2)链接反映的是网页之间形成的“参考”、“引用”和“推荐”关系。若一篇网页被较多的其他网页链接，则它相对较被人关注，其内容应该是较重要或者较有用。因此，可以认为一个网页的“入度”是衡量它重要程度的一种有意义的指标。这和科技论文的情况类似，被引用较多的就是较好的文章。同时，人们注意到，网页的“出度”对分析网上信息的状况也很有意义，因此可
26、以考虑同时用两个指标来衡量网页。这些想法就是斯坦福大学Google研究小组和IBM公司的Clever系统开发小组几乎在同一时间分别提出的著名的PageRank技术和HITS技术的基础。第7章 搜索引擎7.2.1 PageRankPageRank是Google公司创始人Larry Page和SergeyBrin在就读于斯坦福大学研究生院时提出的一种算法，它基于“从许多优质网页链接过来的网页，必定还是优质网页”的思想判定所有网页的重要性，并有效地利用了 Web 所拥有的庞大链接构造的特性。从网页A导向网页B的链接被看做对页面A对页面B的支持投票，Google根据这个投票数来判断页面的重要性。可是
27、Google不仅仅只看投票数(即链接数)，对投票的页面也进行分析。“重要性”高的页面所投的票的评价会更高，因为接受这个投票的页面也会被认为是“重要的页面”。第7章 搜索引擎一个网页的排名是由链接向它的那些网页的排名决定的，而那些网页的排名又由链接向它们的网页排名决定。因此，一个网页的PageRank总是递归地由其他网页的PageRank值决定，任何网页都对其他网页造成排名的影响，PageRank的计算实际上最终归结于整个网络的结构。PageRank还可以用一种“随机冲浪”模型17来定义，如图7-5所示。该模型描述网络用户对网页的访问行为，网络用户可以被看成是一个随机冲浪者，因为用户一般随机选择
28、一个网页作为上网的起始网页，看完这个网页后，从该网页内所含的超链接内随机地选择一个页面继续进行浏览，沿着超链接前进了一定数目的网页后，用户对这个主题感到厌倦，重新随机选择一个网页进行浏览，如此反复。由“随机冲浪”模型我们可以知道，每个网页可能被访问到的次数越多就越重要，这样的“可能被访问的次数”也就定义为网页的权值：PageRank值。第7章 搜索引擎图7-5 随机冲浪模型示意图第7章 搜索引擎1 PageRank概念模型概念模型每个网页都有一些正向链接(出链)和反向链接(入链)，PageRank就是利用网页的正向、反向链接来衡量其重要性的。我们不可能找到一个网页的所有反向链接，但我们可以知道
29、它的所有正向链接。网页的反向链接值可以有很大的差异，例如，某著名网页的主页有62 804个反向链接，而普通网页一般只有几个。通常地，我们认为反向链接数大的网页要比反向链接数小的网页重要，但简单的只对反向链接进行的引用计算并不符合直观上对重要性的认识。例如，如果一个网页只有一个来自政府权威网站主页的入链，虽然它的反向链接数仅为1，但它却是非常重要的网页，应该比那些反向链接数较大但来历不明的网页排名更靠前。PageRank尝试仅从链接结构取得“重要性”的近似值。第7章 搜索引擎Larry和Sergey在文献19中给出的PageRank定义是：如果一个网页的所有反向链接的PageRank值之和高，则
30、该网页的PageRank值也高。这就表明，高PageRank值的网页要么有很多反向链接，要么反向链接数少，但反向链接的PageRank值都很高。设u为一个网页，Fu为u的正向链接集，Bu为u的反向链接集，Nu=|Fu|为u的出度，c为规范化因子，c的引入是为了使得所有网页的总PageRank值是个常数。从PageRank的概念模型出发，有如下的简单的PageRank计算公式：(7-1)BuvvNvRcuR)()(第7章 搜索引擎由式(7-1)我们可以看到，一个网页的PageRank值被平均地分配到它的所有正向链接中，图7-6是用式(7-1)对PageRank进行简单计算的例子。图7-6中，网页
31、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章 搜索引擎图7-6 PageRank的简单计算示意图第7章 搜索引擎2 PageRank的计算方法的计算方法上一节给出了PageRank的简单概念模型，这一节介绍PageRank的具体计算公式，本节的例子主要来自网站(pr.efactory.de)20。下面
32、是Larry Page和Sergey Brin给出的PageRank最初的算法，这个算法考虑网页的所有反向链接的PageRank值，如式(7-2)所示：(7-2)(T)PR(T)(T)PR(T)1(PR(A)11nnCCdd式中：PR(A)是网页A的PageRank值；PR(Tn)是链接向网页A的网页Tn的PageRank值；C(Tn)是网页Tn的出度；d是阻尼因子，取值范围为01，一般取为0.8517。第7章 搜索引擎由式(7-2)我们可以知道，PageRank不是对整个网站进行排序，而是对每个网页分别计算的，而每个网页的PageRank值是由那些链接到网页A的网页递归计算出来的。另外，链接
33、到A的网页Tn的PageRank值并不是均一的，它们受到各自出度C(Tn)的影响，这意味着Tn的出站链接越多，A从Tn受惠的PageRank值就越少，这也正符合上一节所说的“网页的Rank值被平均地分配到它的所有正向链接中”。【例例7-1】考虑一个只包含3个网页A，B和C的小网络，它们之间的链接关系如图7-7所示，此处设阻尼系数d为0.5，试计算每个页面的PR值并作分析。第7章 搜索引擎图7-7 小网络的PageRank第7章 搜索引擎解：解：按照公式(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)/
34、2+PR(B)对以上三元一次方程进行求解，解得：PR(A)=14/13=1.08，PR(B)=10/13=0.77，PR(C)=15/13=1.15。由上面的计算可以知道，所有页面的PageRank之和等于3，即等于网络中的页面总数，这是一个普遍的现象，在进行PageRank计算时，我们可以用它来验证结果是否正确。第7章 搜索引擎对于PageRank算法，Larry Page和Sergey Brin还给出了一种简单直观的解释，他们将PageRank视作一种用户行为模型，用户不关心网页内容而随机点击链接，而网页的PageRank值则决定了用户随机点击访问到这个页面的概率，这也是一个页面的Page
35、Rank值不能完全通过链接传给另一个页面，而只能使其受惠PR(Ti)/C(Ti)的原因。因此，一个页面通过随机冲浪到达的概率就是链入它的页面的链接被点击的概率之和，另外，阻尼系数d减小了这个概率，阻尼系数的引入，是因为用户不可能无限地点击链接，常常随机跳入另一个页面。阻尼系数d定义为用户不断随机点击链接的概率，它取决于点击的次数，取值范围在0到1之间，d的值越高，继续点击链接的概率就越大。因此，用户停止点击并随机冲浪到另一个页面的概率在式子中用常数1d表示，即随机冲浪到另一个页面的概率总是1d，1d本身也是页面所具有的PageRank值。第7章 搜索引擎Larry Page和Sergey Br
36、in在论文中17给出了PageRank的第二种计算公式：(7-3)(T)PR(T)(T)PR(T1PR(A)11nnCCdNd其中，N是所有网页的总数，第二种算法和第一种算法实际上并没有什么本质区别，但在随机冲浪模型中，第二种算法的PageRank是用户在点击了许多链接后到达该网页的概率值，所以所有网页的PageRank值之和为1。第7章 搜索引擎在实际计算中可采用一种近似的迭代方法来计算各个网页的PageRank值21。先给每个网页分配一个初始值，然后利用上面的PageRank计算公式，循环进行有限次运算得到网页的近似PageRank值，根据Larry Page和Sergey Brin公开发
37、表的文章，他们实际需要进行100次迭代才能得到整个互联网的PageRank值。表7-3是例7-1中的3个网页例子的迭代过程。第7章 搜索引擎第7章 搜索引擎从表7-3我们看到，通过迭代的计算，所有网页的PageRank总和收敛于网页总数，所以网页PageRank的平均值为1，最小值为1d，而最大值为dN+(1d)。第7章 搜索引擎3 影响影响PageRank的因素的因素影响PageRank的因素很多，包括入链、出链和阻尼因子等。下面具体讨论各种因素对PageRank值的影响。为了可比较，以下的算法都是基于第一种算法即公式(7-2)来计算的。(1)入链。前面的章节已经介绍过，对于一个网页来说，反
38、向链接数越大，PageRank值就会越高，因此，入链的增加，会提高网页的PageRank值。回顾公式(7-2)，也许读者会认为增加一个入链X，页面A的PageRank值会增加dPR(X)/C(X)，其中PR(X)是页面X的PageRank值，而C(X)是它的出链数。这个结果看起来是正确的，但实际上，A也链接到其他网页，因此，这些网页也会从中受惠，如果这些网页又链接回A，则A的PageRank值会因此又增加，下面用一个例子说明这种情况。第7章 搜索引擎【例例7-2】如图7-8所示，有一个包含4个网页A，B，C，D的网络结构，它们之间构成环形链接，没有任何外部网页链接到它们中的任何一个网页，因此，
39、它们的PageRank值均为1，现在增加一个网页X链接到A，PR(X)为10，假定阻尼因子为0.5，试计算各页面的PR值，并分析入链的影响。第7章 搜索引擎图7-8 入链对PageRank的影响第7章 搜索引擎解：解：可得到下面的方程：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)由以上方程，我们得到的最终结果是：67.135PR(D),33.237PR(C)67.3311PR(B),33.6319PR(A)通过上面的例子我们可以看到，增加一个入链X的最初影
40、响可以通过如下公式计算得到：第7章 搜索引擎这个影响会顺着链接扩散，最终给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.75 PR(C)51105.0)(PR(X)XCd第7章 搜索引擎解得：PR(A)=11.97，PR(B)=
41、9.23PR(C)=7.17，PR(D)=5.63可以看到，入链X对A一个显著增加的初始影响，如下所示：5.711075.0)(PR(X)XCd这个影响导致页面A的PageRank几乎增加了一倍。而且当d=0.5时，A的PageRank是D的4倍，但当d=0.75时，A的PageRank值仅是D的2倍多。所以，随着阻尼因子的增大，入链的影响将从接收入链的网页向整个站点的其他网页偏移。第7章 搜索引擎(3)出链。由于PageRank是基于整个网络结构来计算的，因此，出链的改变必然也会对网页的PageRank带来影响。【例例7-3】如图7-9所示，有两个站点，分别由两个网页组成(A与B，C与D)，
42、开始时没有互相链接，则各自的PageRank值为1，下面增加从A到D的链接，设d=0.75，试计算各页面的PR值，并分析出链的影响。第7章 搜索引擎图7-9 出链对PageRank的影响第7章 搜索引擎解：解：根据图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)上述方程的解为2335PR(D),2332PR(C)2311PR(B),2314PR(A)可见第一个站点的PageRank总值为25/23，小于2；第二个站点总值为67/23
43、，大于2，而两个站点形成的总PageRank值为92/234。所以，增加链接对整个Web的PageRank值无影响，而且一个站点的PageRank的损失必定被另一个网站所获得。第7章 搜索引擎(4)网页数量。由于网络上所有累加的网页PageRank值之和等于网页的总数，因此很容易想到增加网页数量会对所有网页的PageRank值有影响，但问题远不止这么简单，下面的例子说明了这个问题。【例例7-4】计算图7-10中各网页的PageRank值，已知PR(X)10，d=0.75。第7章 搜索引擎图7-10 网页数量对PageRank的影响第7章 搜索引擎解：解：根据图7-10(a)，可以得到如下方程：
44、PR(A)=0.25+0.75(10+PR(B)+PR(C)PR(B)=PR(C)=0.25+0.752PR(A)解上述方程得：14101PR(C),14101PR(B),14260PR(A)在增加一个页面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.753PR(A)第7章 搜索引擎解上述方程得：1470PR(D),1470PR(C)1470PR(B),14260PR(A)可以看到，网页增加后，总的PageRank值并没有明显增加，上例从33变为34，但几乎每个页面的Pa
45、geRank值减小了(除了A)，这是由于新加的页面分享了入链X带来的PageRank值。(5)悬摆链(Dangling Links)。当一个页面没有出链时，它的PageRank值不会传递给别的页面，Page和Brin把这样页面的链接称为悬摆链，如图7-11所示。第7章 搜索引擎图7-11 悬摆链示意图第7章 搜索引擎【例例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.3
46、75PR(A)PR(C)=0.25+0.375PR(A)解上述方程可得：2311PR(C),2311PR(B),2314PR(A)第7章 搜索引擎可见，3个网页的PageRank值之和为36/23，差不多是3的一半，悬摆链带来负面的影响。据Page和Brin称，Google的索引中悬摆链的数目非常大，主要是由于受到robot.txt的限制及索引了一些没有链出的文件类型如pdf等。为了消除这种负面影响，Google在计算PageRank时，将此类链接从数据库里去掉，在计算完毕后，再单独计算悬摆链所链到的页面。比如还是上一个例子，可先从数据库中删掉页面C，如图7-12所示，从而A和B各有PageR
47、ank值1，完成计算后，C被赋予PageRank值：0.25+0.375PR(A)=0.625。尽管如此，最终累加起来的PageRank值仍不等于网页数量，但至少把悬摆链造成的负面影响降低了不少。而有时候去掉一个网页会出现另一个新的悬摆链，因此，删除网页的步骤应该是迭代进行的，如图7-13所示。第7章 搜索引擎图7-12 消除悬摆链的影响第7章 搜索引擎图7-13 消除悬摆链的影响迭代过程第7章 搜索引擎虽然影响PageRank的因素有很多，但Ng等人的研究22表明链接分析具有一定的稳定性，拓扑结构的微小变化不会导致查询排序结果的重大改变。第7章 搜索引擎7.2.2 HITSHITS(Hype
48、rtext-Induced Topic Search)23-24是由康奈尔大学(Cornell University)的Jon Kleinberg博士于1998年首先提出的，它是IBM公司阿尔马登研究中心(IBM Almaden Research Center)的名为“CLEVER”的研究项目中的一部分。Kleinberg认为搜索开始于用户的检索提问，每个页面的重要性也依赖于用户的检索提问，他将用户检索提问分为3种：特指主题检索提问(Specific Queries，也称窄主题检索提问)、泛指主题检索提问(Broad-Topic Queries，也称宽主题检索提问)和相似网页检索提问(Simi
49、lar-Page Queries)。HITS算法专注于改善泛指主题检索的结果。第7章 搜索引擎Kleinberg将网页分为两类，即权威网页(authority)和中心网页(hub)。权威网页是具有较高价值的网页，依赖于指向它的页面，而中心网页是指向较多权威网页的网页，依赖于它所指向的页面。因此，每个页面可以用两个级别的值来衡量，即hub值和authority 值。HITS算法的目标就是通过一定的迭代计算方法得到针对某个检索提问的最具价值的网页，即排名最高的权威网页。第7章 搜索引擎1 HITS算法思想算法思想HITS算法的基本思想是建立一个与查询式有关的图，叫主题子图(Focused Subg
50、raph)。如图7-14所示。图7-14 主题子图第7章 搜索引擎假设给出一个泛指主题的查询串a，构造主题子图的过程如下：(1)用基于文本的搜索引擎得到某一查询的结果集合R，称为根集(Root Set)；(2)将R所指向的网页集合以及其他指向R的网页集合包含进来形成集合S，称为基本集合(Base Set)。为了控制该图的节点数量，在下面两点上施加控制：首先因为从搜索引擎返回结果的数量一般很大，所以有必要将其限制在一个小的范围t内，如设置t为200；其次某个网页的链入网页的数量也可能很大，所以将其限制在一个给定的范围d内，如设置d为50。第7章 搜索引擎同时，为了消除那些纯粹是导航用链接的影响，
