陈老师｜PageRank 还在发挥作用吗？

PageRank是Google发明的用来衡量网页质量和重要性的，将无序的网页们变得有序。PageRank的发明，让Google的搜索结果大大领先于别的搜索引擎，从而开创了Google搜索独占鳌头的时代。

PageRank 的基本思想是被重要的网页所指的网页更重要： 如果一个网页被很多其它网页链接到的话说明这个网页比较重要，也就是PageRank值会相对较高；如果一个PageRank值很高的网页链接到一个其它的网页，那么被链接到的网页的PageRank值会相应地因此而提高。

简单的回顾一下PageRank 的计算公式。

上式是计算网页A的PageRank。Ti是页面中存在着到网页A的链接的网页。C(Ti)是网页Ti中的存在的所有链接的数量。d是阻尼系数，一般定义为用户随机点击链接(random walk)的概率，通常取值0.85。而（1-d）代表着不考虑入站链接的情况下随机进入一个页面的概率。

形象的解释，PageRank就像模拟一个悠闲的上网者，上网者首先随机选择一个网页打开，然后在这个网页上呆了几分钟后，跳转到该网页所指向的链接，这样无所事事、漫无目的地在网页上跳来跳去，PageRank就是估计这个悠闲的上网者分布在各个网页上的概率。这里， 上网者是一个悠闲的上网者，而不是一个愚蠢的上网者，上网者是聪明而悠闲。他悠闲，漫无目的，总是随机的选择网页。他聪明，在走到一个终结网页或者一个陷阱网页，不会傻傻的干着急，他会在浏览器的地址随机（1-d）输入一个地址，当然这个地址可能又是原来的网页，但这里给了他一个逃离的机会，让他离开这万丈深渊。

由于 PageRank给原本无序的网页带来了有序 ，在网页搜索中，PageRank发挥的作用是巨大的，总结如下几点。

第一，引导爬虫优先爬取高质量的网页 。爬虫从一些种子网页出发，提取网页中所有出现的链接，然后沿着新出现的链接，接着爬取，循环往复。在PageRank发明之前，爬虫要么随机选取新发现的链接，或是根据链接被发现的次数，来指导爬取的先后顺序，这样很难控制所爬取的网页的质量。PageRank发明之后，系统围绕每个时段的所有网页的快照，计算每个链接的PageRank，并排序。然后，爬虫根据PageRank的大小，择优爬取。由于资源限制，很难爬取所有网页，有了PageRank，就可以在有限资源下，快速的爬取千亿级别的高质量网页。由于PageRank能够保证爬下来索引的网页集合是高质量，尽可能减少作弊网页，为之后的处理提供了优质的起点。

第二，提高搜索结果排序 。在搜索词和文档的相关性差不多的情况下，PageRank大的排在前，也就是说用户先看到的是高质量的网页结果。常用的做法是将PageRank作为一个因子和相关性分数相乘得到最后的排序分数。比如，网页A和B和某个搜索词的相关性分数都是0.8，但PR(A) = 0.9，PR(B) = 0.8，那么Score(A) = 0.8*0.9 = 0.72，Score(B) = 0.8*0.8 = 0.64，显然A应该排在B之前。

第三，保证高质量网页能检索出来 。每个网页都有一个ID，ID按照PageRank的大小来赋值的，PageRank越大的高质量网页被赋予越小的ID。然后，倒排索引是根据ID排序的。这样检索时，只要检查前面的几千或上万个网页就行，不用检查所有含有某个词的网页，况且在响应时间要求下，不可能检查所有的包含搜索词的网页。比如，几乎所有的网页都包含“的”，如果搜索词中有“的”，系统不可能检查所有的网页并且给每个网页打分，那么，我们就需要只看前面的高质量的网页，也就是说ID小的网页。这样，至少保证我们的搜索结果中先出现的是好的网页。在这个过程中，一般使用固定大小的最小堆，如果下一个网页的相关性分数小于现在的最小值，扔掉。否则取代当前的最小值，再调整堆。