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

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



搜索引擎对一个查询的搜索结果进行排名，取决于两组关键信息：网页的质量，网页与搜索内容的相关性。



网页的质量

在互联网上，如果一个网页被很多其他网页锁链接，说明它受到普遍的承认和信赖，那么它的排名就越高。这就是 PageRank 的核心思想。它把整个互联网当作一个整体来对待，而不是将每个网页孤立考虑，不仅关注网页的内容，也关注网页之间的关系，利用网页之间的关系信息提高搜索结果排名质量。



在此基础上，对来自不同网页的链接区别对待，网页排名更高的那些网页的链接被认为更可靠，给予这些链接以更大的权重。类似于显示生活中的投票，大股东的表决权更大，大咖的话语受重视的程度更大。PageRank 算法中，排名高的网页贡献的链接权重也更大。



至此，遇到了一个问题：计算搜索结果的网页排名过程中需要用到网页本身的排名。 似乎成了“先有鸡还是先有蛋”的问题。



佩奇和布林用迭代方法解决了这个问题。先假定所有网页的排名是相同的（给出一个初始值），算出各个网页的第一次迭代排名，然后根据第一次迭代排名算出第二次迭代排名。他们两人从理论上证明了不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到排名的真实值。

网页本身和查询的相关性

对搜索结果进行排名时，应该将网页本身质量好，并且和搜索的关键词相关性高的网页排在前面。为了避免内容长的网页中同一关键词多次出现，比内容短的网页“占优”，需要根据网页的长度对关键词进行归一化，用关键词出现的次数除以网页的总字数，称为关键词频率（Term Frequency，缩写TF）。



另外，需要忽略一些对主题没什么用处，但会大量出现的词。例如“的”、“地”、“得”等。这些词称为停止词（Stop Word）。停止词的权重为零。



对待不同的词还要给予不同的权重，例如对于专业的词，在所有网页中出现的概率比较小，出现的时候对网页内容主题的重要性更高，需要给予更大的权重。而对于通用的词，被所有网页所使用的可能性更大，出现的时候对网页内容主题的重要性更小，需要给予更小的权重。现在使用最多的权重计算方法是逆文本频率指数（Inverse Document Frequency，缩写 IDF）。计算某个关键词的 IDF 的公式是 log(D/Dw)，其中 D 是全部网页的数量，DW 是有这个关键词出现的网页的数量。



网页与搜索的 n 个关键词的相关性计算公式为：

TF1 * IDF1 + TF2 * IDF2 + ... + TFn * IDFn



综合以上两点考虑网页本身的质量，以及网页与搜索内容的相关性，从而计算出网页的搜索结果排名。



工程实现上，由于互联网上的网页数量十分巨大，因此需要采用稀疏矩阵计算的技巧简化计算量，并且采用并行计算的方式缩短响应时间。