网普技术论坛 网普科技  
» 游客:   网普主页 | 注册 | 登录 | 帮助
 

作者:
标题: [转]谈 Page Rank – Google 的民主表决式网页排名技术 上一主题 | 下一主题
网普科技
网普管理员

网普科技人民公仆


积分 3080
发贴 2863
注册 2004-6-26
来自 网普科技
状态 离线
#1  [转]谈 Page Rank – Google 的民主表决式网页排名技术

2006年2月27日 上午 08:38:00
发表者: 吴军, Google 工程师

大家可能听说过,Google 革命性的发明是它名为 “Page Rank” 的网页排名算法,这项技术彻底解决了搜索结果排序的问题。其实最先试图给互联网上的众多网站排序的并不是 Google。Yahoo!公司最初第一个用目录分类的方式让用户通过互联网检索信息,但由于当时计算机容量和速度的限制,当时的 Yahoo!和同时代的其它搜索引擎都存在一个共同的问题:收录的网页太少,而且只能对网页中常见内容相关的实际用词进行索引。那时,用户很难找到很相关信息。我记得 1999 年以前查找一篇论文,要换好几个搜索引擎。后来 DEC 公司开发了 AltaVista 搜索引擎,只用一台 ALPHA 服务器,却收录了比以往引擎都多的网页,而且对里面的每个词进行索引。AltaVista 虽然让用户搜索到大量结果,但大部分结果却与查询不太相关,有时找想看的网页需要翻好几页。所以最初的 AltaVista 在一定程度上解决了覆盖率的问题,但不能很好地对结果进行排序。

Google 的 “Page Rank” (网页排名)是怎么回事呢?其实简单说就是民主表决。打个比方,假如我们要找李开复博士,有一百个人举手说自己是李开复。那么谁是真的呢?也许有好几个真的,但即使如此谁又是大家真正想找的呢?:-) 如果大家都说在 Google 公司的那个是真的,那么他就是真的。

在互联网上,如果一个网页被很多其它网页所链接,说明它受到普遍的承认和信赖,那么它的排名就高。这就是 Page Rank 的核心思想。 当然 Google 的 Page Rank 算法实际上要复杂得多。比如说,对来自不同网页的链接对待不同,本身网页排名高的链接更可靠,于是给这些链接予较大的权重。Page Rank 考虑了这个因素,可是现在问题又来了,计算搜索结果的网页排名过程中需要用到网页本身的排名,这不成了先有鸡还是先有蛋的问题了吗?

Google 的两个创始人拉里•佩奇 (Larry Page )和谢尔盖•布林 (Sergey Brin) 把这个问题变成了一个二维矩阵相乘的问题,并且用迭代的方法解决了这个问题。他们先假定所有网页的排名是相同的,并且根据这个初始值,算出各个网页的第一次迭代排名,然后再根据第一次迭代排名算出第二次的排名。他们两人从理论上证明了不论初始值如何选取,这种算法都保证了网页排名的估计值能收敛到他们的真实值。值得一提的事,这种算法是完全没有任何人工干预的。

理论问题解决了,又遇到实际问题。因为互联网上网页的数量是巨大的,上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页,那么这个矩阵就有一百亿亿个元素。这样大的矩阵相乘,计算量是非常大的。拉里和谢尔盖两人利用稀疏矩阵计算的技巧,大大的简化了计算量,并实现了这个网页排名算法。今天 Google 的工程师把这个算法移植到并行的计算机中,进一步缩短了计算时间,使网页更新的周期比以前短了许多。

我来 Google 后,拉里 (Larry) 在和我们几个新员工座谈时,讲起他当年和谢尔盖(Sergey) 是怎么想到网页排名算法的。他说:"当时我们觉得整个互联网就像一张大的图(Graph),每个网站就像一个节点,而每个网页的链接就像一个弧。我想,互联网可以用一个图或者矩阵描述,我也许可以用这个发现做个博士论文。" 他和谢尔盖就这样发明了 Page Rank 的算法。

网页排名的高明之处在于它把整个互联网当作了一个整体对待。它无意识中符合了系统论的观点。相比之下,以前的信息检索大多把每一个网页当作独立的个体对待,很多人当初只注意了网页内容和查询语句的相关性,忽略了网页之间的关系。

今天,Google 搜索引擎比最初复杂、完善了许多。但是网页排名在 Google 所有算法中依然是至关重要的。在学术界, 这个算法被公认为是文献检索中最大的贡献之一,并且被很多大学引入了信息检索课程 (Information Retrieval) 的教程。

http://googlechinablog.com/2006/02/page-rank-google.html



天理路上甚宽,稍游心,胸中便觉广大宏朗;
人欲路上甚窄,才寄迹,眼前俱是荆棘泥涂。



网普科技,优质美国主机服务!
美国Linux主机,美国虚拟主机
支持PHP+MYSQL+cPanel+EMAIL
为用户负责,拒绝反动、赌博及色情内容! QQ:126818

发送QQ消息
2006-3-5 11:24 AM
查看资料  访问主页  发短消息  QQ   编辑帖子  引用回复 顶部
celn
网普高级成员





积分 209
发贴 197
注册 2004-6-30
状态 离线
#2  

看到这篇文章
我就想到我那个PR=7的站
555



Desert Eagle
2006-3-5 04:59 PM
查看资料  发送邮件  发短消息   编辑帖子  引用回复 顶部
茱莉娅
THE BODY SHOP美容顾问

茱莉娅美体小铺


积分 209
发贴 197
注册 2009-5-21
来自 茱莉娅美体小铺
状态 离线
#2  赞助商信息The body shop

茱莉娅美体小铺
茱莉娅美体小铺淘宝店
茱莉娅美体小铺


茱莉娅美体小铺淘宝店
2006-3-5 04:59 PM
查看资料  发送邮件  发短消息   编辑帖子  引用回复 顶部


可打印版本 | 推荐给朋友 | 订阅主题 | 收藏主题



论坛跳转:  




Powered by Discuz! 2.5 © 2001-2005 Comsenz Technology Ltd.
Processed in 0.008318 second(s), 9 queries, Gzip enabled
------------------------------------------------------------------------------
本论坛属网普科技交流与技术支持论坛!
拒绝任何人以任何形式在本论坛发表与中华人民共和国法律相抵触的言论!
美国主机, 美国虚拟主机, cPanel+PHP+Mysql+Ftp+Email+Zend+GD2+国际域名支持
技术支持 QQ: 126818 EMail & MSN: support[AT]netpu.net
[ 联系我们 ] - [ 网普科技 ]