大家可能聽說過,Google革命性的發明是名為PageRank的網頁排名演算法,這項技術徹底解決了搜尋結果排序的問題。但其實,最早試圖為網路上眾多網站排序的並不是Google。
Yahoo!最初是第一個用目錄分類方式讓使用者檢索網際網路資訊的公司。但由於當時電腦容量與速度的限制,當時的Yahoo!與同時代的其他搜尋引擎都存在一個共同問題:收錄的網頁太少,而且只能針對網頁中常見用詞進行索引。那時使用者很難找到真正相關的資訊——我記得1999年以前查找一篇論文,得換好幾個搜尋引擎。
後來DEC公司開發了AltaVista,只用一台ALPHA伺服器,卻收錄了比以往都多的網頁,並對其中每個詞建立索引。AltaVista讓使用者搜尋到大量結果,但大部分與查詢不太相關,有時要翻好幾頁才找到想看的頁面。所以最初的AltaVista在一定程度上解決了覆蓋率問題,卻無法很好地排序。
PageRank到底是怎麼回事?簡單說就是民主表決。
打個比方:假如我們要找李開復博士,有一百個人舉手說自己是李開復,誰才是真的?也許有好幾個是真的,但即使如此,誰又是大家真正想找的那一位?如果大家都說在Google公司的那個是真的,那他就是真的。
在網際網路上,如果一個網頁被很多其他網頁所連結,說明它受到普遍承認與信賴,排名就該高。這就是PageRank的核心思想。
當然,實際演算法要複雜得多。例如,來自不同網頁的連結對待方式不同——本身排名高的網頁所給的連結更可靠,因此被賦予較大權重。但這帶來一個邏輯難題:計算排名時需要用網頁本身的排名,這豈不是「先有雞還是先有蛋」?
Google的兩位創辦人Larry Page與Sergey Brin把這個問題轉化為一個二維矩陣相乘的問題,並用迭代法求解。他們先假定所有網頁排名相同,根據這個初始值算出第一次迭代排名,再用第一次的結果算出第二次,如此反覆。兩人從理論上證明:不論初始值如何選取,這個演算法都能保證估計值收斂到真實值。值得一提的是,整個過程完全沒有任何人工干預。
理論解決了,實際問題隨之而來。網路上網頁數量龐大,上述二維矩陣的元素數量理論上是網頁數的平方。假定有十億個網頁,這個矩陣就有一百億億個元素,相乘的計算量極為可觀。Larry與Sergey利用稀疏矩陣計算技巧大幅簡化了計算量,讓演算法得以實際運行。今天Google的工程師把它移植到平行計算環境中,進一步縮短計算時間,使網頁更新週期比早期短了許多。
我來Google後,Larry曾在與幾位新員工座談時,談起他當年與Sergey是怎麼想到網頁排名演算法的。他說:「當時我們覺得整個網際網路就像一張大的圖(Graph),每個網站像一個節點,每個網頁的連結就像一條弧。我想,網際網路可以用一個圖或矩陣來描述,我也許可以用這個發現做篇博士論文。」兩人就這樣發明了PageRank。
網頁排名的高明之處,在於它把整個網際網路當作一個整體對待,無意識中符合了系統論的觀點。相比之下,早期的資訊檢索大多把每個網頁當作獨立個體,許多人只注意網頁內容與查詢語句的相關性,忽略了網頁之間的關係。
今天的Google搜尋引擎比最初複雜、完善許多,但網頁排名在所有演算法中依然舉足輕重。在學術界,這個演算法被公認為文獻檢索領域最大的貢獻之一,並被許多大學納入資訊檢索課程的教材。