大家可能聽說過，Google 革命性的發(fā)明是它名為 “Page Rank” 的網(wǎng)頁排名算法，這項技術徹底解決了搜索結果排序的問題。其實最先試圖給互聯(lián)網(wǎng)上的眾多網(wǎng)站排序的并不是 Google。Yahoo！公司最初第一個用目錄分類的方式讓用戶通過互聯(lián)網(wǎng)檢索信息，但由于當時計算機容量和速度的限制，當時的 Yahoo！和同時代的其它搜索引擎都存在一個共同的問題：收錄的網(wǎng)頁太少，而且只能對網(wǎng)頁中常見內容相關的實際用詞進行索引。那時，用戶很難找到很相關信息。我記得 1999 年以前查找一篇論文，要換好幾個搜索引擎。后來 DEC 公司開發(fā)了 AltaVista 搜索引擎，只用一臺 ALPHA 服務器，卻收錄了比以往引擎都多的網(wǎng)頁，而且對里面的每個詞進行索引。AltaVista 雖然讓用戶搜索到大量結果，但大部分結果卻與查詢不太相關，有時找想看的網(wǎng)頁需要翻好幾頁。所以最初的 AltaVista 在一定程度上解決了覆蓋率的問題，但不能很好地對結果進行排序。

Google 的 “Page Rank” （網(wǎng)頁排名）是怎么回事呢？其實簡單說就是民主表決。打個比方，假如我們要找李開復博士，有一百個人舉手說自己是李開復。那么誰是真的呢？也許有好幾個真的，但即使如此誰又是大家真正想找的呢？:-) 如果大家都說在 Google 公司的那個是真的，那么他就是真的。

在互聯(lián)網(wǎng)上，如果一個網(wǎng)頁被很多其它網(wǎng)頁所鏈接，說明它受到普遍的承認和信賴，那么它的排名就高。這就是 Page Rank 的核心思想。當然 Google 的 Page Rank 算法實際上要復雜得多。比如說，對來自不同網(wǎng)頁的鏈接對待不同，本身網(wǎng)頁排名高的鏈接更可靠，于是給這些鏈接予較大的權重。Page Rank 考慮了這個因素，可是現(xiàn)在問題又來了，計算搜索結果的網(wǎng)頁排名過程中需要用到網(wǎng)頁本身的排名，這不成了先有雞還是先有蛋的問題了嗎？

Google 的兩個創(chuàng)始人拉里•佩奇（Larry Page ）和謝爾蓋•布林 (Sergey Brin) 把這個問題變成了一個二維矩陣相乘的問題，并且用迭代的方法解決了這個問題。他們先假定所有網(wǎng)頁的排名是相同的，并且根據(jù)這個初始值，算出各個網(wǎng)頁的第一次迭代排名，然后再根據(jù)第一次迭代排名算出第二次的排名。他們兩人從理論上證明了不論初始值如何選取，這種算法都保證了網(wǎng)頁排名的估計值能收斂到他們的真實值。值得一提的事，這種算法是完全沒有任何人工干預的。

理論問題解決了，又遇到實際問題。因為互聯(lián)網(wǎng)上網(wǎng)頁的數(shù)量是巨大的，上面提到的二維矩陣從理論上講有網(wǎng)頁數(shù)目平方之多個元素。如果我們假定有十億個網(wǎng)頁，那么這個矩陣就有一百億億個元素。這樣大的矩陣相乘，計算量是非常大的。拉里和謝爾蓋兩人利用稀疏矩陣計算的技巧，大大的簡化了計算量，并實現(xiàn)了這個網(wǎng)頁排名算法。今天 Google 的工程師把這個算法移植到并行的計算機中，進一步縮短了計算時間，使網(wǎng)頁更新的周期比以前短了許多。

我來 Google 后，拉里 (Larry) 在和我們幾個新員工座談時，講起他當年和謝爾蓋(Sergey) 是怎么想到網(wǎng)頁排名算法的。他說："當時我們覺得整個互聯(lián)網(wǎng)就像一張大的圖（Graph)，每個網(wǎng)站就像一個節(jié)點，而每個網(wǎng)頁的鏈接就像一個弧。我想，互聯(lián)網(wǎng)可以用一個圖或者矩陣描述，我也許可以用這個發(fā)現(xiàn)做個博士論文。" 他和謝爾蓋就這樣發(fā)明了 Page Rank 的算法。

網(wǎng)頁排名的高明之處在于它把整個互聯(lián)網(wǎng)當作了一個整體對待。它無意識中符合了系統(tǒng)論的觀點。相比之下，以前的信息檢索大多把每一個網(wǎng)頁當作獨立的個體對待，很多人當初只注意了網(wǎng)頁內容和查詢語句的相關性，忽略了網(wǎng)頁之間的關系。

今天，Google 搜索引擎比最初復雜、完善了許多。但是網(wǎng)頁排名在 Google 所有算法中依然是至關重要的。在學術界, 這個算法被公認為是文獻檢索中最大的貢獻之一，并且被很多大學引入了信息檢索課程 (Information Retrieval) 的教程。