写点什么

架构师训练营第 13 周作业

用户头像
netspecial
关注
发布于: 2020 年 12 月 19 日
  • Google 搜索引擎是如何对搜索结果进行排序的?(请用自己的语言描述 PageRank 算法。)

PageRank,网页排名,又称网页级别,Google 左侧排名或佩奇排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google 公司创办人拉里·佩奇(Larry Page)之姓来命名。

  • PageRank 让链接来"投票"

PageRank 通过网络浩瀚的超链接关系来确定一个页面的等级。Google 把从A 页面到B 页面的链接解释为A 页面给B 页面投票,Google 根据投票来源(甚至来源的来源,即链接到A 页面的页面)和投票目标的等级来决定新的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级提升。

一个页面的"得票数"由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个页面的PageRank 是由所有链向它的页面(「链入页面」)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。

  • PageRank 算法

  • 假设一个由4个页面组成的小团体:A,B,C 和D。如果所有页面都链向A,那么A 的PR (PageRank) 值将是B,C 及D 的Pagerank 总和。





  • 继续假设B 也有链接到C,并且D 也有链接到包括A 的3个页面。一个页面不能投票2次。所以B 给每个页面半票。以同样的逻辑,D 投出的票只有三分之一算到了A 的PageRank 上。



  • 换句话说,根据链出总数平分一个页面的PR 值。



  • 互联网中如果一个网页只有对自己的出链,或者几个网页的出链形成一个循环圈。那么在不断地迭代过程中,这一个或几个网页的PR值将只增不减,显然不合理。为了解决这个问题。我们想象一个随机浏览网页的人,假定他有一个确定的概率会输入网址直接跳转到一个随机的网页,并且跳转到每个网页的概率是一样的。于是则此图中A的PR值可表示为:

默认是0.85

  • PageRank的计算公式

是被研究的页面,是所有对有出链的页面集合, 页面的出链数目, 是所有页面数量, 一般取0.85

  • 根据上面的公式,我们可以计算每个页面的PR值,在不断迭代趋于稳定的时候,停止计算,这个时候得到的就是所有页面最终的PageRank值。



用户头像

netspecial

关注

还未添加个人签名 2011.07.20 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第 13 周作业