中国的博客,走近我们的产品、技术和文化
Google 中国的博客,走近我们的产品、技术和文化
谈 Page Rank – Google 的民主表决式网页排名技术
2006年2月27日
发表者: 吴军, 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) 的教程。
標籤
编程之夏,UR
创新
创意改善社会 公益温暖中国
促进智能能源利用
大学
谷歌翻译,即时相机翻译,Instant Camera Translation
谷歌十周年系列
谷歌艺术与文化
观妙中国,Shadow Art,智玩皮影
广告
广告安全
互联网,Internet
科技
女性开发者
社会
视频广告
数据中心
数字营销
搜索
网站管理员
文化研究所
艺术计划
音乐搜索
愚人节
增强型广告系列
智能隐形眼镜项目
中小企业
adexchange
Admob
admob sdk
Ads
Adsense
AdWords
android
android m
Android应用开发中国大学生挑战赛
App Inventor
Calendar
cardboard
CES
Chrome
Chrome Web Store
Chrome,Chrome实验
Chrome实验
CI
Code Jam
corporate
Creative
Cross-device
Cultural Institute
culture
Data Center
DevArt
Developer
display
diversity
Doodle
DoubleClick
G+
G2G,Culture
GA&C
gaming
Global Impact Awards
Gmail
Gogle科学挑战赛
Good to Know
Google Ads
Google AdWords
Google Analytics
Google Art Project
Google Arts & Culture
Google Code-in竞赛
Google Demo Day Asia
Google Docs
Google Doodle
Google Drive
Google Drive 云端硬盘
Google Fiber
Google Font
Google for Startups
Google Green
Google I/O
Google Image Search
Google Keep
Google partners
Google Play
Google Science Fair
Google Search
Google Top Contributor Summit
Google Translate
Google Trend
Google Trends
Google Zeitgeist 2012
Google安全系统
Google博士生奖研金
Google翻译
Google奖学金
Google杰出贡献者峰会
Google科学挑战赛
Google网站管理员
Google网站管理员,Webmaster
Google文化研究所
Google在线营销挑战赛
Google中国教育高峰会
IME 输入法
Innovation
Made with Code
maps
mobile ads
mobile ads sdk
Modoo
moonshot
native ads
Nexus
programmatic buying
Project X
Pwn20wn及Pwnium3 黑客大赛
Remarketing. Ads
Search
Security
smb
Solve for X
Street view
student
UR
VR
Web Platform Docs
web security
Webmaster
year in search 2014
YouTube
zeitgeist
博客归档
2024
10月
8月
7月
6月
5月
4月
3月
2月
1月
2023
12月
11月
10月
9月
5月
4月
3月
2月
2022
11月
10月
5月
4月
2月
1月
2021
10月
9月
5月
4月
3月
2月
2020
12月
5月
4月
3月
2019
10月
8月
7月
6月
5月
4月
3月
2018
12月
10月
9月
8月
7月
6月
5月
3月
2月
1月
2017
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2016
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2015
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2014
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2013
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2012
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2011
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2010
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2009
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2008
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2007
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2006
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
Feed