架构师训练营第十三周命题作业

Google 搜索引擎是如何对搜索结果进行排序的？（请用自己的语言描述 PageRank 算法。）

PageRank 对网页的排名，是根据网页的分值由高到底排序的。那么，网页的分值是怎么来的呢？

互联网上的网页不计其数，每个网页可能包含其他网页的超链接形式的引用。网页被引用的次数越多，说明该网页越重要，所以分值也就越大。

每个网页的分值，都由指向它的网页的分值相加。若一个网页包含了 N 个网页的超链接，那么它的分支会被平均为 N 份，加到各个被指向的网页上。

比如有 A、B、C、D 四个网页，A 中包含了 D 的超链接，B 包含了 A 的超链接，C 包含了 B 的超链接：

A -> D

B -> A -> D

C -> B -> D

C -> E

那么各个网页的得分为：

PR(E) = PR(C)/2 （C 指向了 B、E 两个页面，所以 E 的得分为 C 的二分之一）

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

PR(C) = 0 （没有任何页面指向 C，所以 C 的分值为 0）

PR(B) = PR(C)/2

PR(A) = PR(B)/2

特别地，如果一个网页包含了指向自己的超链接，那么按前面的算法，会陷入一个死循环，而导致分值无限增加。为了避免这种情况，我们会给每个网页引入一个概率，模仿用户访问。每个网页都有一定的概率被访问到，反过来说，每个网页会有一定的概率被关闭。这样就解决了这种自引用导致的死循环问题。

还是前面的例子，引入这个概率 p 之后，每个网页的得分为：

PR(E) = p * PR(C)/2 + (1-p)/5

从 C 跳转到 E，本来是 1/2 的概率，再加上引入的 p，所以要乘以 p。同时，在跳往 E 之前，同时还有一定的概率关闭 E，而直接跳到其他几个页面之一去，关闭 E 的概率（也就是调往其他页面的概率）就是 1-p，E 也是有可能通过随机跳往的，所以随机跳往 E 的概率是 (1-p)/5。

其他页面的分值算法类似。