架构师课作业 - 第十三周

作业

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

PageRank 的作用是, 根据页面的等级排序, 推荐用户等级最高的页面.

原理是, A 页面中包含 B 页面的链接, 则 A 的分值会流向 B

1. 比如现在有四个页面 A, B, C, D, A 页面的分值等于指向它的页面的分值.

P(A) = P(B) + P(C) + P(D)

2. 但存在一个页面中包含多个链接的情况, 这时指向 A 的分值需要被指向其他的页面均分.

P(A) = P(B)/L(B) + P(C)/L(C) + P(D)/L(D)

3. 当然还存在循环依赖的问题, 比如 A 页面也有链接, 最终经过各种环节又指向了 B 页面, 所以需要多次递归计算, 当 P 值趋向不变, 或是达到自定义的循环次数即可.

4. 还存在一种情况, 是某个页面的引用是自己本身, 会产生黑洞效应, 经过多次递归可能这个页面就排名很高了, 为了防止这一现象, 引入直接跳出的可能性, 作为第二种路径选择, 则该页面的跳转页面就不只是自己, 不会把所有页面的分值最终都导向自己.