發(fā)表者: 吳軍， Google 工程師
大家可能聽(tīng)說(shuō)過(guò)，Google 革命性的發(fā)明是它名為 “Page Rank” 的網(wǎng)頁(yè)排名算法，這項(xiàng)技術(shù)徹底解決了搜索結(jié)果排序的問(wèn)題。其實(shí)最先試圖給互聯(lián)網(wǎng)上的眾多網(wǎng)站排序的并不是 Google。
Yahoo！ 公司最初第一個(gè)用目錄分類(lèi)的方式讓用戶(hù)通過(guò)互聯(lián)網(wǎng)檢索信息，但由于當(dāng)時(shí)計(jì)算機(jī)容量和速度的限制，當(dāng)時(shí)的 Yahoo！ 和同時(shí)代的其它搜索引擎都存在一個(gè)共同的問(wèn)題： 收錄的網(wǎng)頁(yè)太少，而且只能對(duì)網(wǎng)頁(yè)中常見(jiàn)內(nèi)容相關(guān)的實(shí)際用詞進(jìn)行索引。那時(shí)，用戶(hù)很難找到很相關(guān)信息。我記得 1999 年以前查找一篇論文，要換好幾個(gè)搜索引擎。后來(lái) DEC 公司開(kāi)發(fā)了
AltaVista 搜索引擎，只用一臺(tái) ALPHA 服務(wù)器，卻收錄了比以往引擎都多的網(wǎng)頁(yè)，而且對(duì)里面的每個(gè)詞進(jìn)行索引。AltaVista 雖然讓用戶(hù)搜索到大量結(jié)果，但大部分結(jié)果卻與查詢(xún)不太相關(guān)，有時(shí)找想看的網(wǎng)頁(yè)需要翻好幾頁(yè)。所以最初的 AltaVista 在一定程度上解決了覆蓋率的問(wèn)題，但不能很好地對(duì)結(jié)果進(jìn)行排序。
Google 的 “Page Rank” （網(wǎng)頁(yè)排名）是怎么回事呢？其實(shí)簡(jiǎn)單說(shuō)就是民主表決。打個(gè)比方，假如我們要找李開(kāi)復(fù)博士，有一百個(gè)人舉手說(shuō)自己是李開(kāi)復(fù)。那么誰(shuí)是真的呢？也許有好幾個(gè)真的，但即使如此誰(shuí)又是大家真正想找的呢？:-) 如果大家都說(shuō)在 Google 公司的那個(gè)是真的，那么他就是真的。
在互聯(lián)網(wǎng)上，如果一個(gè)網(wǎng)頁(yè)被很多其它網(wǎng)頁(yè)所鏈接，說(shuō)明它受到普遍的承認(rèn)和信賴(lài)，那么它的排名就高。這就是 Page Rank 的核心思想。 當(dāng)然 Google 的 Page Rank 算法實(shí)際上要復(fù)雜得多。比如說(shuō)，對(duì)來(lái)自不同網(wǎng)頁(yè)的鏈接對(duì)待不同，本身網(wǎng)頁(yè)排名高的鏈接更可靠，于是給這些鏈接予較大的權(quán)重。Page Rank 考慮了這個(gè)因素，可是現(xiàn)在問(wèn)題又來(lái)了，計(jì)算搜索結(jié)果的網(wǎng)頁(yè)排名過(guò)程中需要用到網(wǎng)頁(yè)本身的排名，這不成了先有雞還是先有蛋的問(wèn)題了嗎？
Google 的兩個(gè)創(chuàng)始人拉里?佩奇 （
Larry Page ）和謝爾蓋?布林 (
Sergey Brin) 把這個(gè)問(wèn)題變成了一個(gè)二維矩陣相乘的問(wèn)題，并且用迭代的方法解決了這個(gè)問(wèn)題。他們先假定所有網(wǎng)頁(yè)的排名是相同的，并且根據(jù)這個(gè)初始值，算出各個(gè)網(wǎng)頁(yè)的第一次迭代排名，然后再根據(jù)第一次迭代排名算出第二次的排名。他們兩人從理論上證明了不論初始值如何選取，這種算法都保證了網(wǎng)頁(yè)排名的估計(jì)值能收斂到他們的真實(shí)值。值得一提的事，這種算法是完全沒(méi)有任何人工干預(yù)的。
理論問(wèn)題解決了，又遇到實(shí)際問(wèn)題。因?yàn)榛ヂ?lián)網(wǎng)上網(wǎng)頁(yè)的數(shù)量是巨大的，上面提到的二維矩陣從理論上講有網(wǎng)頁(yè)數(shù)目平方之多個(gè)元素。如果我們假定有十億個(gè)網(wǎng)頁(yè)，那么這個(gè)矩陣 就有一百億億個(gè)元素。這樣大的矩陣相乘，計(jì)算量是非常大的。拉里和謝爾蓋兩人利用稀疏矩陣計(jì)算的技巧，大大的簡(jiǎn)化了計(jì)算量，并實(shí)現(xiàn)了這個(gè)網(wǎng)頁(yè)排名算法。今天 Google 的工程師把這個(gè)算法移植到并行的計(jì)算機(jī)中，進(jìn)一步縮短了計(jì)算時(shí)間，使網(wǎng)頁(yè)更新的周期比以前短了許多。
我來(lái) Google 后，拉里 (Larry) 在和我們幾個(gè)新員工座談時(shí)，講起他當(dāng)年和謝爾蓋(Sergey) 是怎么想到網(wǎng)頁(yè)排名算法的。他說(shuō)："當(dāng)時(shí)我們覺(jué)得整個(gè)互聯(lián)網(wǎng)就像一張大的圖 （Graph)，每個(gè)網(wǎng)站就像一個(gè)節(jié)點(diǎn)，而每個(gè)網(wǎng)頁(yè)的鏈接就像一個(gè)弧。我想，互聯(lián)網(wǎng)可以用一個(gè)圖或者矩陣描述，我也許可以用這個(gè)發(fā)現(xiàn)做個(gè)博士論文。" 他和謝爾蓋就這樣發(fā)明了 Page Rank 的算法。
網(wǎng)頁(yè)排名的高明之處在于它把整個(gè)互聯(lián)網(wǎng)當(dāng)作了一個(gè)整體對(duì)待。它無(wú)意識(shí)中符合了系統(tǒng)論的觀(guān)點(diǎn)。相比之下，以前的信息檢索大多把每一個(gè)網(wǎng)頁(yè)當(dāng)作獨(dú)立的個(gè)體對(duì)待，很多人當(dāng)初只注意了網(wǎng)頁(yè)內(nèi)容和查詢(xún)語(yǔ)句的相關(guān)性，忽略了網(wǎng)頁(yè)之間的關(guān)系。
今天，Google 搜索引擎比最初復(fù)雜、完善了許多。但是網(wǎng)頁(yè)排名在 Google 所有算法中依然是至關(guān)重要的。在學(xué)術(shù)界, 這個(gè)算法被公認(rèn)為是文獻(xiàn)檢索中最大的貢獻(xiàn)之一，并且被很多大學(xué)引入了信息檢索課程 (Information Retrieval) 的教程。