Google的搜索結果排列算法

本文作者馬特-卡茲（Matt Cutts）是Google公司品質管理部門的軟件工程師。他的工作主要是給好的網站評定等級，並負責開發阻止虛假或垃圾網站出現在Google搜索結果上的技術。

圖書館管理員們提出最多的問題之一是：「對於什麼樣的結果應該位於搜索列表的最上方， Google是如何選擇的？」現在品質工程師馬特-卡茲介紹了快速入門的知識，解釋了Google是如何在網上爬行和索引，以及如何評定搜索結果等級的。馬特也向學校圖書館管理員提出建議，告訴他們如何輔導學生。
4 \( l; G! W8 r. \/ u4 \
爬行和索引

5 q2 P6 W$ J; Y" n在你瀏覽包含了Google搜索結果的網頁之前，要發生很多事情。首先是在萬維網數以十億計的網頁上爬行和索引，這個工作是由Googlebot完成的，它負責與全球的網絡服務器連接以收集文件。爬行不是真的在網上漫遊，而是訪問網絡服務器返回到一個特定的網頁上，接著掃瞄該網頁建立超鏈接並為每一個網頁編上號碼。爬行可收集大量的文件，但這些文件還不能直接用於搜索。

- ~' v& \9 ~* a3 r: ~. Q如果沒有索引，在你想查詢如「civil war」（南北戰爭）等內容時，Google的服務器將不得不在你每次搜索時閱讀每一份文件的內容。因此第二個步驟是要建立一個索引，這樣就需要「轉換」 爬行所獲得的數據。為了不必在每一份文件上掃瞄每一個單詞，就需要在數據上做些文章，以便顯示包含了特定單詞的所有文件。例如，假設單詞「civil」在編號為3、8、22、56、68和92的文件上出現過，而單詞「war」出現編號為2、8、15、22、68和77的文件上。
! J" Z& i; z5 U- K; h
7 b- N  E! g# P& w9 ^1 x3 z( t一旦建立了索引，就開始對文件進行等級評定並確定它們的相關性。假如某個人上Google搜索並輸入「civil war」，為呈現和評價搜索結果需要做兩件事：一是查找包含了用戶提問的網頁；二是按照相關性排定匹配網頁的位置。Google已經開發出一個有趣的技術可加速第一步驟的過程：不是將所有索引存儲在一台電腦上，而是使用數百台電腦做這種工作。由於任務被分配到很多電腦上，使得查詢答案更為迅速。
' K0 |& v5 l+ h% [; B9 Q0 r
' y; j/ ^$ E5 q為更加形象地描述這個過程，可以設想下一本30頁厚書的索引。如果一個人在索引中查找數頁的信息，那麼每一次搜索都至少需要花幾秒鐘的時間；但如果你將索引的每一頁分給不同的人去查找呢？三十個人分別查找索引的不同部分，要比一個人獨自查找快的多。同樣，Google也是將數據分配到各台電腦上以便可以更快地查找文件。

如何查找包含了用戶提問的網頁？讓我們返回到上面舉的「civil war」例子。單詞「civil」在編號為3、8、22、56、68和92的文件上，單詞「war」在編號為2、8、15、22、68和77的文件上，我們可以在網頁上顯示文件並尋找包含兩個單詞的文件（從下表中可以看出是8、22和68號文件）。
9 x6 V0 K7 b4 U" h* S$ \
! p' H& s: @3 a3 D; }$ @5 z8 p單詞civil 3 8 22 56 68 92
' t- {8 ]5 W# w. ?8 X
單詞war 2 8 15 22 68 77
6 ?" M) M! ^& _+ m. ]
兩個單詞都出現 8 22 68
: v& M5 }! S  z0 ~9 h. E* O
包含了一個單詞的文件列表被稱為「文件標識列表」，查找包含兩個單詞的文件被稱為「文件標識列表的交集」。
6 X' e/ d; N, t
# g* i/ E1 j) R! {; ?! k0 B) r1 k3 W評定搜索結果

% S3 ?* c( f3 f" h有了包含用戶提問的網頁後，就該按照相關性評定網頁了。Google使用了很多技術，其中 PageRank算法是最有名的。PageRank評定的是兩種事情：從網站到某一網頁有多少個鏈接，提供鏈接的網站的排名。使用PageRank，來自 CNN和紐約時報網站的鏈接的價值，是很多不太有名網站的兩倍。

除了PageRank外Google還使用了很多其他技術，例如一份文件所包含的 「civil」和「war」兩個單詞靠的很近，就比只使用了「war」單詞的包含「Revolutionary War」（獨立戰爭）的文件相關性要大的多。另外在題目中出現了「civil war」的網頁，它的相關性就比題目為「19th Century American Clothing」（19世紀的美國服裝）要重要的多。同樣如果「civil war」在網頁上出現了數次，比出現一次的網頁要相關的多。
7 P; m- L7 p! p3 \( [* F- d" G
7 W6 S% z% N. s4 K6 ^5 ^Google的目的是要找到知名度和相關性都大的網頁。如果兩個網頁出現匹配提問的信息數量幾乎一樣，我們常常會選擇更有名網站的鏈接。但如果其他方面表明一個網頁更為相關，也會選擇更少鏈接或更低排名的網頁。例如，一個網頁全篇都是講「南北戰爭」的內容，會比只是略微提到「南北戰爭」的網頁更為有用，即使這個網頁是出現不太有名的網站上。一旦我們有了文件的列表和分值，就會選擇最高分值、最匹配的文件。
  c9 U, s& ~2 k
. ~/ K3 y3 ]+ V  R# A3 E, H* ZGoogle從包含了提問單詞的每一份文件中提取幾句話作為摘要顯示，接著將排好的URLs和摘要顯示在搜索結果上。正如你所知道的運行一個搜索器需要大量的計算資源。每一次搜索需要500台以上的電腦一起工作，搜索的時間還不到半秒鐘。

一篇文章很難把GG的算法搞清楚

舊聞了。。不號