充气玩具 网站制作

编辑备注：本文内容涵盖编程知识，如站长在阅读时遇到涉及程序算法公式时，建议只需了解大意即可，无需解读公式，重在了解PageRank算法的基本概念。

作者：张洋

很早就对 Google 的 PageRank 算法很感兴趣，但一直没有深究，只有个轮廓性的概念。前几天趁团队 outing 的机会，在动车上看了一些相关的资料，趁热打铁，将所看的东西整理成此文。

本文首先会讨论搜索引擎的核心难题，同时讨论早期搜索引擎关于结果页面重要性评价算法的困境，借此引出 PageRank 产生的背景。第二部分会详细讨论 PageRank 的思想来源、基础框架，并结合互联网页面拓扑结构讨论 PageRank 处理 Dead Ends 及平滑化的方法。第三部分讨论 Topic-Sensitive PageRank 算法。最后将讨论对 PageRank 的 Spam 攻击方法：Spam Farm 以及搜索引擎对 Spam Farm 的防御。

搜索引擎的难题

Google 早已成为全球最成功的互联网搜索引擎，但这个当前的搜索引擎巨无霸却不是最早的互联网搜索引擎，在 Google 出现之前，曾出现过许多通用或专业领域搜索引擎。Google 最终能击败所有竞争对手，很大程度上是因为它解决了困扰前辈们的最大难题：对搜索结果按重要性排序。而解决这个问题的算法就是 PageRank。毫不夸张的说，是 PageRank 算法成就了 Google 今天的低位。要理解为什么解决这个难题如此重要，我们先来看一下搜索引擎的核心框架。

搜索引擎的核心框架

虽然搜索引擎已经发展了很多年，但是其核心北京东城区网站建设公司却没有太大变化。从本质上说，搜索引擎是一个资料检索系统，搜索引擎拥有一个资料库（具体到这里就是互联网页面），用户提交一个检索条件（例如关键词），搜索引擎返回符合查询条件的资料列表。理论上检索条件可以非常复杂，为了简单起见，我们不妨设检索条件是一至多个以空格分隔的词，而其表达的语义是同时含有这些词的资料（等价于布尔代数的逻辑与）。例如，提交张洋博客，意思就是给我既含有‘张洋’又含有‘博客’词语的页面，以下是 Google 对这条关键词的搜索结果：

可以看到我的博客出现在第五条，而第四条是我之前在博客园的博客。

当然，实际上现在的搜索引擎都是有分词机制的，例如如果以张洋的博客为关键词，搜索引擎会自动将其分解为张洋的博客三个词，而的作为停止词（Stop Word）会被过滤掉。关于分词及词权评价算法（如 TF-IDF 算法）是一个很大的话题，这里就不展开讨论了，为了简单此处可以将搜索引擎想象为一个只会机械匹配词语的检索系统。

这样看来，建立一个搜索引擎的核心问题就是两个：1、建立资料库；2、建立一种数据结构，可以根据关键词找到含有这个词的页面。

第一个问题一般是通过一种叫爬虫（Spider）的特殊程序实现的（当然，专业领域搜索引擎例如某个学术会议的论文检索系统可能直接从数据库建立资料库），简单来说，爬虫就是从一个页面出发（例如新浪首页），通过 HTTP 协议通信获取这个页面的所有内容，把这个页面 url 和内容记录下来（记录到资料库），然后分析页面中的链接，再去分别获取这些链接链向页面的内容，记录到资料库后再分析这个页面的链接……重复这个过程，就可以将整个互联网的页面全部获取下来（当然这是理想情况，要求整个 Web 是一个强连通（Strongly Connected），并且所有页面的 robots 协议允许爬虫抓取页面，为了简单，我们仍然假设 Web 是一个强连通图，且芜湖网站建设公司不考虑 robots 协议）。抽象来看，可以将资料库看做一个巨大的 key-value 结构，key 是页面 url，value是页面内容。

第二个问题是通过一种叫倒排索引（inverted index）的数据结构实现的，抽象来说倒排索引也是一组 key-value 结构，key 是关键词，value 是一个页面编号集合（假设资料库中每个页面有唯一编号），表示这些页面含有这个关键词。本文不详细讨论倒排索引的建立方法。

有了上面的分析，就可以简要说明搜索引擎的核心动作了：搜索引擎获取张洋博客查询条件，将其分为张洋和博客两个词。然后分别从倒排索引中找到张洋所对应的集合，假设是{1， 3， 6， 8， 11， 15}；博客对应的集合是{1， 6， 10， 11， 12， 17， 20， 22}，将两个集合做交运算（intersection），结果是{1， 6， 11}。最后，从资料库中找出1、6、11对应的页面返回给用户就可以了。

搜索引擎的核心难题

上面阐述了一个非常简单的搜索引擎工作框架，虽然现代搜索引擎的具体细节原理要复杂的多，但其本质却与这个简单的模型并无二异。实际 Google 在上述两点上相比其前辈并无高明之处。其最大的成功是解决了第三个、也是最为困难的问题：如何对查询结果排序。

我们知道 Web 页面数量非常巨大，所以一个检索的结果条目数量也非常多，例如上面张洋博客的检索返回了超过 260 万条结果。用户不可能从如此众多的结果中一一查找对自己有用的信息，所以，一个好的搜索引擎必须想办法将质量较高的页面排在前面。其实直观上也可以感觉出，在使用搜索引擎时，我们并不太关心页面是否够全（上百万的结果，全不全有什么区别？而且实际上搜索引擎都是取 top，并不会真的返回全部结果。），而很关心前一两页是否都是质量较高的页面，是否能满足我们的实际需求。

因此，对搜索结果按重要性合理的排序就成为搜索引擎的最大核心，也是 Google 最企业官网建设终成功的突破点。

早期搜索引擎的做法

不评价

这个看起来可充气玩具 网站制作能有点搞笑，但实际上早期很多搜索引擎（甚至包括现在的很多专业领域搜索引擎）根本不评价结果重要性，而是直接按照某自然顺序（例如时间顺序或编号顺序）返回结果。这在结果集比较少的情况下还说得过去，但是一旦结果集变大，用户叫苦不迭，试想让你从几万条质量参差不齐的页面中寻找需要的内容，简直就是一场灾难，这也注定这种方法不可能用于现代的通用搜索引擎。

基于检索词的评价

后来，一些搜索引擎引入了基于检索关键词去评价搜索结构重要性的方法，实际上，这类方法如 TF-IDF 算法在现代搜索引擎中仍在使用，但其已经不是评价质量的唯一指标。完整描述 TF-IDF 比较繁琐，本文这里用一种更简单的抽象模型描述这种方法。

基于检索词评价的思想非常朴素：和检索词匹配度越高的页面重要性越高。匹配度就是要定义的具体度量。一个最直接的想法是关键词出现次数越多的页面匹配度越高。还是搜索张洋博客的例子：假设A页面出现张洋5次，博客10次；B页面出现张洋2次，博客8次。于是A页面的匹配度为 5 + 10 = 15，B页面为 2 + 8 = 10，于是认为A页面的重要性高于B页面。很多朋友可能意识到这里的不合理性：内容较长的网页往往更可能比内容较短的网页关键词出现的次数多。因此，我们可以修改一下算法，用关键词出现次数除以页面总词数，也就是通过关键词占比作为匹配度，这样可以克服上面提到的不合理。

早期一些搜索引擎确实是基于类似的算法评价网页重要性的。这种评价算法看似依据充分、实现直观简单，但却非常容易受到一种叫Term Spam的攻击。