轉(zhuǎn)載自：[url]http://www.yeeyan.com/articles/view/thunder/364[/url]
原作者: Sergey Brin and Lawrence Page譯者: 雷聲大雨點(diǎn)大 (Blog)

譯者：本文是谷歌創(chuàng)始人Sergey和Larry在斯坦福大學(xué)計(jì)算機(jī)系讀博士時(shí)的一篇論文。發(fā)表于1997年。Google的一切應(yīng)該都起源與此。深入了解Google，深入了解互聯(lián)網(wǎng)的未來，當(dāng)讀此文。我把全文分成6個(gè)部分，推薦到這里。有興趣的朋友可以一起來翻譯。

我沒有發(fā)現(xiàn)本文的完整中譯，只找到了這個(gè)片段，由xfygx朋友翻譯了本文的第一部分，其他似乎沒有全部完成。

所以，這部分譯文是xfygx原作，而非我的翻譯！我只是就自己的理解做了些改動(dòng)。如果有幸xfygx朋友能看到我在他/她博客的留言，來我們譯言，我非常希望能把本文轉(zhuǎn)到他/她名下。

另外，如果您發(fā)現(xiàn)已有其他出色的完整中譯版了，請(qǐng)告訴我們。免得譯者們重復(fù)勞動(dòng)。
摘要
在本文中，我們將介紹Google，一個(gè)充分利用超文本文件（譯者：即HTML文件）結(jié)構(gòu)進(jìn)行搜索的大規(guī)模搜索引擎的原型。Google可以有效地對(duì)互聯(lián)網(wǎng)（Web）資源進(jìn)行爬行搜索（crawl）〔注 1〕和索引，比目前已經(jīng)存在的系統(tǒng)有更令人滿意的搜索結(jié)果。該原型的數(shù)據(jù)庫包括2400萬頁面的全文和之間的鏈接，可通過[url]http://google.stanford.edu/[/url]訪問。
設(shè)計(jì)搜索引擎是一項(xiàng)富有挑戰(zhàn)的任務(wù)。搜索引擎為數(shù)以億計(jì)的網(wǎng)頁建立索引，而這些網(wǎng)頁包含了同樣數(shù)量級(jí)的不同詞語。每天響應(yīng)數(shù)千萬計(jì)的查詢請(qǐng)求。盡管大規(guī)模網(wǎng)絡(luò)搜索引擎是很重要的，但在這個(gè)領(lǐng)域很少有理論研究。更由于技術(shù)的飛速發(fā)展和互聯(lián)網(wǎng)的普及，今天這樣的搜索引擎和三年前的搜索引擎會(huì)是非常不同的。本文對(duì)我們的大規(guī)模搜索引擎進(jìn)行了深入的討論，這也是目前為止我們所知道的公開發(fā)表的第一篇如此詳細(xì)的討論。
除了如何把傳統(tǒng)的搜索技術(shù)擴(kuò)展到前所未有的海量數(shù)據(jù)，我們還面臨這樣一個(gè)新的技術(shù)挑戰(zhàn)：如何使用超文本文件所蘊(yùn)含的擴(kuò)展信息以產(chǎn)生更好的搜索結(jié)果。本文討論了如何建立一個(gè)實(shí)用的大規(guī)模系統(tǒng)，以利用超文本文件中的額外信息。另外，我們也關(guān)注了如何有效處理超文本文件不可控的問題，因?yàn)槿藗兛梢噪S意發(fā)表超文 本文件（譯者：如個(gè)人網(wǎng)頁）。
關(guān)鍵詞
World Wide Web, Search Engines, Information retrieval, PageRank, Google
1.簡介
互聯(lián)網(wǎng)對(duì)信息檢索（Information Retrieval）領(lǐng)域產(chǎn)生了新的挑戰(zhàn)。網(wǎng)上的信息數(shù)量是在不斷的快速增長，同時(shí)有越來越多對(duì)網(wǎng)絡(luò)搜索毫無經(jīng)驗(yàn)的新用戶上網(wǎng)。在網(wǎng)上沖浪時(shí)，人們一般會(huì)利用網(wǎng)絡(luò)的“鏈接圖”（譯者：想像每個(gè)網(wǎng)頁是一個(gè)點(diǎn)，網(wǎng)頁之間的鏈接是從一個(gè)點(diǎn)指向另一個(gè)點(diǎn)的邊，這就構(gòu)成了一張有向圖。）。而這經(jīng)常從一個(gè)人工維護(hù)的網(wǎng)址列表（如Yahoo!）或是一個(gè)搜索引擎開始。人工維護(hù)的列表有效覆蓋了流行的主題，但這些是主觀的，花費(fèi)高昂，更新緩慢，并且不能覆蓋全部的主題，特別是冷僻的主題。依賴關(guān)鍵詞匹配的自動(dòng)搜索引擎通常返回太多的低質(zhì)量的匹配結(jié)果。更糟的是，一些廣告商通過某些方式誤導(dǎo)搜索引擎以試圖吸引人們的注意力。我們建立了一個(gè)大規(guī)模搜索引擎來解決已存在系統(tǒng)的許多問題。它充分利用超文本文件所表達(dá)額外信息來提供更高質(zhì)量的搜索結(jié)果。我們選擇這個(gè)名字，Google，是因?yàn)樗莋oogol（表示10的100次方)這個(gè)詞的常用拼寫法。而這個(gè)詞的意義與我們建立這個(gè)大規(guī)模搜索引擎的目標(biāo)是非常一致的。
1.1 互聯(lián)網(wǎng)搜索引擎 -- 擴(kuò)展：1994 - 2000
搜索引擎技術(shù)必須極大規(guī)模地?cái)U(kuò)展才能趕上互聯(lián)網(wǎng)的發(fā)展步伐。在1994年,最早的 web搜索引擎之一，World Wide Web Worm(WWWW) [McBryan 94]已經(jīng)索引了11萬web頁面和文檔。到了1997年的11月，頂級(jí)的搜索引擎聲稱的索引的頁面數(shù)量從2百萬(WebCrawler) 到10億(根據(jù) Search Engine Watch)。可以想像到2000年，索引全部的Web將需要包含超過十億的文檔。同時(shí)，搜索引擎需要處理的查詢請(qǐng)求也會(huì)有不可想像的增長。在1994年 3月到4月間，World Wide Web Worm平均每天收到1500個(gè)查詢。而到了1997年的11月，Altavista聲稱　它平均每天要處理大約2千萬的查詢。隨著web的用戶和使用搜索引擎的自動(dòng)系統(tǒng)數(shù)量的增加，到2000年，頂級(jí)的搜索引擎每天將會(huì)需要處理數(shù)以億計(jì)的查詢。我們的系統(tǒng)的目標(biāo)是解決這些由搜索引擎大規(guī)模擴(kuò)展所帶來的問題，包括質(zhì)量和可擴(kuò)展性。
1.2 Google:與Web同步發(fā)展
即便建立一個(gè)適應(yīng)今天互聯(lián)網(wǎng)信息量的搜索引擎已經(jīng)面臨著許多的挑戰(zhàn)。我們需要使用快速爬行搜索技術(shù)收集web文檔并保持它們的及時(shí)更新；我們需要可以有效存儲(chǔ)文檔索引和文檔自身（這不是必須的）的海量存儲(chǔ)空間；我們需要可以有效處理數(shù)百GB數(shù)據(jù)的索引系統(tǒng)；我們還需要可以在一秒內(nèi)處理成百上千的查詢的計(jì)算能力。
這些任務(wù)都隨著Web的增長而愈發(fā)變的困難。然而，硬件性能的提高和費(fèi)用的降低可以部分的抵消這些困難。但某些方面是個(gè)例外，如硬盤數(shù)據(jù)讀取的速度和操作系統(tǒng)的魯棒性（譯者：可以通俗地理解為穩(wěn)定性）都沒有顯著提高。在設(shè)計(jì)Google的過程中，我們已經(jīng)考慮到了Web 和技術(shù)這兩方面的發(fā)展。Google被設(shè)計(jì)為可以適應(yīng)極大數(shù)據(jù)量。它有效使用存儲(chǔ)空間來保存索引。它的數(shù)據(jù)結(jié)構(gòu)被優(yōu)化以便可以快速和有效的存取數(shù)據(jù)（見 4.2節(jié))。另外，我們認(rèn)為，相對(duì)于文本以及HTML文檔數(shù)量的增長，索引和存儲(chǔ)花費(fèi)它們的費(fèi)用最終會(huì)下降(見附錄B)。因此，Google這樣的集中式（譯者：而非分布到許多遠(yuǎn)程計(jì)算機(jī)，如P2P系統(tǒng)）搜索系統(tǒng)隨著互聯(lián)網(wǎng)的發(fā)展而擴(kuò)容就成為可能。
1.3 設(shè)計(jì)目標(biāo)
1.3.1 提高搜索質(zhì)量
我們的主要目標(biāo)是提高web搜索引擎的質(zhì)量。在1994年，一些人認(rèn)為用一個(gè)完整的搜索索引就可以很容易地找到任何信息。在1994年互聯(lián)網(wǎng)最佳－－導(dǎo)航員上，有這樣的話"最好的導(dǎo)航服務(wù)應(yīng)該是使用戶可以很容易的在Web上找到任何信息"。然而，到1997，這個(gè)任務(wù)仍是非常困難的。在最近使用搜索引擎的用戶都可以很容易的證實(shí)索引的完整性并不是決定搜索結(jié)果質(zhì)量的唯一因素。"垃圾結(jié)果" 經(jīng)常會(huì)使用戶找不到真正感興趣的結(jié)果。實(shí)際上，到1997年的十一月，四個(gè)頂級(jí)搜索引擎中，僅僅只有一個(gè)可以在搜索時(shí)發(fā)現(xiàn)它自身(對(duì)查詢自己名字的請(qǐng)求，返回結(jié)果中將自己排在結(jié)果中的前十名)。產(chǎn)生這個(gè)問題的主要原因之一是在這些搜索引擎的索引庫中文檔的數(shù)量成數(shù)量級(jí)地增長，而用戶看這么多文檔的能力卻不可能這樣增長。用戶往往只看結(jié)果中的前數(shù)十個(gè)。因此，隨著文檔規(guī)模的增加，我們需要工具來提高查準(zhǔn)率（在前十個(gè)結(jié)果中返回相關(guān)內(nèi)容）。實(shí)際上，我們說的"相關(guān)"是指最好的那一份，因?yàn)榭赡軙?huì)有幾萬份“稍微“相關(guān)的文檔。查準(zhǔn)率在我們的眼中是如此的重要，以至于我們甚至愿意為此損失一些查全率。最近的研究顯示，超文本文件中的信息可以有助于提高搜索和其他應(yīng)用[Marchiori 97] [Spertus 97] [Weiss 96] [Kleinberg 98]。特別是網(wǎng)頁鏈接的結(jié)構(gòu)，以及鏈接本身的文字，為相關(guān)性判定和進(jìn)行質(zhì)量的篩選提供了許多信息。Google使用了網(wǎng)頁鏈接結(jié)構(gòu)和錨（譯者：HTML中的語法，表示一個(gè)指向網(wǎng)頁的鏈接）鏈接中的文字。（詳見2.1和2.2節(jié)）
1.3.2 搜索引擎的理論研究
隨著WEB的巨大發(fā)展，互聯(lián)網(wǎng)也越來越商業(yè)化。在1993年，只有1.5%的web服務(wù)器是.com的域名。而到了1997年，這個(gè)數(shù)字已經(jīng)變成了60%。同時(shí)，搜索引擎的從學(xué)術(shù)研究變成了商業(yè)性質(zhì)。到目前為止，大多數(shù)的搜索引擎的開發(fā)都是由公司來進(jìn)行的，很少有詳細(xì)的技術(shù)資料被公開。這導(dǎo)致了這項(xiàng)技術(shù)帶有了許多神秘的色彩，并且是以廣告為主（見附錄A）。對(duì)于Google，我們有一個(gè)非常重要的目標(biāo)就是推動(dòng)搜索引擎在學(xué)術(shù)界的發(fā)展和理解。
另外的重要的設(shè)計(jì)目標(biāo)是建立一個(gè)可以讓一定數(shù)量的用戶實(shí)際使用的系統(tǒng)。用戶使用對(duì)我們來說非常重要，因?yàn)槲覀冋J(rèn)為真正利用了現(xiàn)代互聯(lián)網(wǎng)系統(tǒng)的海量數(shù)據(jù)的研究才是最有價(jià)值的。比如現(xiàn)在每天有數(shù)千萬用戶查詢，但由于這些數(shù)據(jù)被認(rèn)為具有商業(yè)價(jià)值，很難拿來作學(xué)術(shù)研究。
我們最終的設(shè)計(jì)目標(biāo)是建立一個(gè)可以支持在大規(guī)模互聯(lián)網(wǎng)數(shù)據(jù)上進(jìn)行研究活動(dòng)的系統(tǒng)構(gòu)架。為了支持研究活動(dòng)，Google存儲(chǔ)了全部的在爬行搜索中發(fā)現(xiàn)的實(shí)際數(shù)據(jù)，并壓縮起來。主要的目標(biāo)之一是建立一個(gè)環(huán)境，在這個(gè)環(huán)境中，研究者可以很快的利用這個(gè)難得的系統(tǒng)，處理web數(shù)據(jù)，產(chǎn)生令人感興趣的結(jié)果。在短時(shí)間內(nèi)系統(tǒng)就被建立起來，已經(jīng)有一些論文使用了通過Google生成的數(shù)據(jù)庫。還有許多其它的項(xiàng)目在進(jìn)行之中。另外的目標(biāo)是我們希望建立一個(gè)類似空間站的環(huán)境，使得研究者，甚至是學(xué)生可以在我們的大規(guī)模web數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)。

〔注 1〕爬行搜索，Crawl，是指搜索引擎會(huì)跟隨網(wǎng)頁間的鏈接從一個(gè)網(wǎng)頁“爬行”到下一個(gè)網(wǎng)頁。而對(duì)每一個(gè)網(wǎng)頁的分析和記錄，或者這個(gè)過程的結(jié)果，則稱為“索引”。


2.系統(tǒng)功能

Google搜索引擎通過兩個(gè)重要功能來產(chǎn)生高精確度的結(jié)果。第一，它利用互聯(lián)網(wǎng)的鏈接結(jié)構(gòu)為每個(gè)網(wǎng)頁計(jì)算出一個(gè)高質(zhì)量的排名。這個(gè)排名被稱為PageRank[注一]，具體在Larry Page98年的論文[Page 98]中有詳述。第二，Google利用鏈接本身來提高搜索結(jié)果的質(zhì)量。

2.1 PageRank: 給互聯(lián)網(wǎng)帶來秩序

現(xiàn)有的搜索引擎在很大程度上忽略了一個(gè)重要資源－－把互聯(lián)網(wǎng)看做是一個(gè)引用關(guān)系（鏈接關(guān)系）圖（見第一部分的注解）。我們已經(jīng)產(chǎn)生了包含5億1千8百萬這樣的超文本鏈接（就是網(wǎng)頁指向網(wǎng)頁的鏈接）的地圖－－這是對(duì)整個(gè)互聯(lián)網(wǎng)的一個(gè)相當(dāng)顯著的采樣。這樣的地圖讓我們能快速計(jì)算網(wǎng)頁的“PageRank”－－一個(gè)對(duì)于網(wǎng)頁被引用程度的客觀衡量，而被引用程度與人們對(duì)于網(wǎng)頁重要性的主觀認(rèn)識(shí)也很好地吻合。由于這樣的吻合，PageRank成為對(duì)用關(guān)鍵字搜索網(wǎng)頁返回的結(jié)果進(jìn)行排序的極好方式。對(duì)于最熱門的分類，局限于網(wǎng)頁標(biāo)題進(jìn)行簡單的文字查找，PageRank排序后的搜索結(jié)果效果極好。而在整個(gè)Google系統(tǒng)中進(jìn)行全文查找，PageRank的作用也是非常顯著的。

2.1.1 PageRank 計(jì)算簡述

學(xué)術(shù)文獻(xiàn)的引用機(jī)制被應(yīng)用到互聯(lián)網(wǎng)上－－主要就是計(jì)算一個(gè)網(wǎng)頁被引用，或被反向鏈接的次數(shù)。這給出了對(duì)一個(gè)網(wǎng)頁重要性或質(zhì)量的估計(jì)。PageRank進(jìn)一步發(fā)展了這個(gè)想法：來自不同頁面的鏈接被給以不同的權(quán)重，并依據(jù)一個(gè)網(wǎng)頁上鏈接的個(gè)數(shù)正態(tài)化。PageRank的定義如下：
我們假定網(wǎng)頁　A　有若干其他網(wǎng)頁（T1...Tn）指向它（即引用關(guān)系）。參數(shù)d是一個(gè)0,1之間的阻尼系數(shù)。我們通常把d設(shè)為0.85。下一節(jié)會(huì)有關(guān)于d的詳述。C(A)是從網(wǎng)頁A指向其他網(wǎng)頁的鏈接個(gè)數(shù)。那么網(wǎng)頁A的PageRank的計(jì)算如下：

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

我們注意到PageRank構(gòu)成一個(gè)分布于所有網(wǎng)頁上的概率分布函數(shù)，因此所有網(wǎng)頁的PageRank總和應(yīng)該為　1。

PageRank，或PR(A)可以通過一個(gè)簡單的循環(huán)算法來計(jì)算。這對(duì)應(yīng)于正態(tài)化后的互聯(lián)網(wǎng)鏈接矩陣的主要艾根向量的計(jì)算。另外，2千6百萬網(wǎng)頁的PageRank可以在一臺(tái)中型服務(wù)器上，通過幾小時(shí)的計(jì)算完成。這里有很多細(xì)節(jié)超出了本論文的討論范圍。

2.1.2 直觀解釋

PageRank 可以被想像成一個(gè)對(duì)用戶行為建立的模型。我們假想一個(gè)“隨機(jī)上網(wǎng)者”；隨機(jī)地給他一個(gè)網(wǎng)頁；他漫無目的地點(diǎn)擊網(wǎng)頁的鏈接，而從來不點(diǎn)“返回鍵”；最終他覺得煩了，又從另一個(gè)隨機(jī)的網(wǎng)頁從新開始。在上述模型中，“隨機(jī)上網(wǎng)者”訪問一個(gè)頁面的概率就是這個(gè)頁面的PageRank。而阻尼系數(shù)d，則是我們的“隨機(jī)上網(wǎng)者”在訪問了一個(gè)頁面后，覺得煩了，開始訪問一個(gè)新的頁面的概率。上述模型的一個(gè)重要變形是把阻尼系數(shù)d加到一個(gè)網(wǎng)頁上，還是加到一組網(wǎng)頁上。這個(gè)變形使得故意欺騙系統(tǒng)獲得高排名的企圖幾乎變成不可能的。我們對(duì)PageRank有若干延伸，詳見這里[Page 98]。

另一個(gè)直觀的解釋是如果有很多其他網(wǎng)頁指向一個(gè)頁面，或者其他有很高PageRank的網(wǎng)頁指向這個(gè)頁面，該頁面應(yīng)該有較高的PageRank。直覺告訴我們，如果一個(gè)網(wǎng)頁被互聯(lián)網(wǎng)上的很多其他網(wǎng)頁引用，它應(yīng)該是值得關(guān)注的。而那些只有一個(gè)引用的頁面，如果它來自象Yahoo!首頁，那大約這個(gè)網(wǎng)頁也值得看看。如果一個(gè)網(wǎng)頁質(zhì)量不高或根本就是一個(gè)死鏈接，Yahoo首頁多半不會(huì)鏈接它。PageRank　考慮了上述兩種以及之間的各種情況，它用遞歸方式把網(wǎng)頁的權(quán)重通過互聯(lián)網(wǎng)的鏈接結(jié)構(gòu)傳播出去。

2.2 錨鏈接（Anchor，是HTML的語法，即網(wǎng)頁鏈接）的文本

鏈接的文字在我們的搜索引擎中受到特殊處理。大多數(shù)搜索引擎把鏈接中的文本部分（比如keso這個(gè)鏈接中的keso）歸屬于這個(gè)鏈接所在的網(wǎng)頁。而我們除此之外，還把它歸屬于這個(gè)鏈接指向的頁面。這有幾個(gè)好處。第一，錨鏈接對(duì)被指向網(wǎng)頁的描述，通常比網(wǎng)頁本身的描述更準(zhǔn)確。第二，錨鏈接可能指向那些不能被建立文本索引的文檔，如圖片、程序、數(shù)據(jù)庫。這使得現(xiàn)在不能爬行搜索的頁面可以被搜索到了。注意，以前從未被爬行搜索過的頁面可能會(huì)產(chǎn)生問題，因?yàn)樗鼈兊挠行詮奈幢或?yàn)證過。比如搜索引擎甚至?xí)祷匾粋€(gè)有鏈接指向，但其實(shí)根本不存在的頁面。然而，由于我們可以對(duì)結(jié)果排序，這個(gè)問題很少會(huì)出現(xiàn)。

把錨鏈接中的文本傳播到被指向的頁面這個(gè)想法，在World Wide Web Worm [McBryan 94] 已經(jīng)被實(shí)施了。主要用于對(duì)非文本文件的搜索，和把搜索結(jié)果擴(kuò)展到更多下載文檔。而我們使用錨鏈接，主要是因?yàn)樗梢蕴峁└哔|(zhì)量的結(jié)果。有效使用錨鏈接在技術(shù)上是很難實(shí)現(xiàn)的，因?yàn)榇罅繑?shù)據(jù)需要處理。在我們現(xiàn)在爬行搜索過的2千4百萬網(wǎng)頁中，我們?yōu)?億5千9百萬錨鏈接建立了索引。

2.3 其他功能
除了使用PageRank和利用錨鏈接中的文本外，Google還有其他一些功能。第一，它有所有網(wǎng)頁的位置信息，因此在搜索過程中充分應(yīng)用了接近程度。第二，Google　記錄網(wǎng)頁的一些視覺表現(xiàn)，如單詞的字體大小。大字體的權(quán)重比小字體要高。第三，完整的原始HTML頁面被保存下來（即Google的網(wǎng)頁快照功能）。


[注一]　PageRank　可以譯為網(wǎng)頁排名，建議后面就用原文了。另外，Page　恰恰是Google創(chuàng)始人之一Larry Page的姓。




3相關(guān)工作
基于web的搜索研究有一段簡短的的歷史。萬維網(wǎng)蠕蟲( wwww )[ mcbryan 94 ]是第一個(gè)網(wǎng)上搜索引擎。但隨后,產(chǎn)生了幾個(gè)學(xué)院派的搜索引擎,其中有不少現(xiàn)在已經(jīng)是公開的上市公司了。相比Web的增長和搜索引擎的重要性,現(xiàn)在幾乎沒有關(guān)于當(dāng)前搜索引擎有價(jià)值的研究材料 [Pinkerton 94].。據(jù)邁克爾.茂丁( lycos公司首席科學(xué)家)[Mauldin] "各種服務(wù)(包括lycos )緊密的守衛(wèi)著這些數(shù)據(jù)庫" 。
不過,在搜索引擎的具體的特點(diǎn)上已進(jìn)行了相當(dāng)?shù)墓ぷ鳌?duì)現(xiàn)有商業(yè)搜索引擎產(chǎn)生的搜索結(jié)果的后處理已經(jīng)取得了卓有成效的成果,或是產(chǎn)生小規(guī)模的“個(gè)性化的“搜索引擎。最終,有過不少針對(duì)信息檢索系統(tǒng)的研究,尤其是對(duì)受控制的結(jié)果集的研究。在隨后兩節(jié)中,我們將討論一些必須擴(kuò)大研究的領(lǐng)域,以便更好地在Web上工作。


3.1信息檢索
信息檢索系統(tǒng)的研究,已經(jīng)有很多年了,并且成果顯著[Witten 94] 。 然而,大多數(shù)信息檢索系統(tǒng) 的 研究 針對(duì)的是 受控制的同質(zhì)集合 ，例如,主題相關(guān)的科學(xué)論文或新聞故事。的確,信息檢索的主要的基準(zhǔn),文本檢索會(huì)議[TREC 96] ,用了一個(gè)相當(dāng)小的，并且受控制的集合 作為其基準(zhǔn)。“非常大的語料庫“; 基準(zhǔn)只有20gb 大小， 相較于我們搜索過的 2千4百萬網(wǎng)頁，有147gb 的數(shù)據(jù)量 。在TREC 上工作很好的搜索引擎，拿到Web上來往往效果不佳。舉例來說,標(biāo)準(zhǔn)向量空間模型試圖返回和搜索條件最為近似的文件,假定搜索和文件都是各自文字定義的向量。對(duì)Web 而言,這種策略只會(huì)返回非常簡短的文件，包含查詢本身和幾句話。舉例來說,我們已經(jīng)看到了一個(gè)主要的搜索引擎返回的一個(gè)頁面僅僅含有“比爾.克林頓真糟“;和從“比爾.克林頓“搜索來的圖片。 有人爭論到 ,在Web上用戶應(yīng)該更具體,更準(zhǔn)確地指出他們要什么,并且在搜索查詢中增添更多詞。我們堅(jiān)決反對(duì)這種立場。如果用戶發(fā)出對(duì)“比爾克林頓“的搜索查詢 ,他們應(yīng)得到合理的結(jié)果,因?yàn)榫瓦@個(gè)話題存在著大量的高品質(zhì)的資料。鑒于這一類的例子,我們認(rèn)為標(biāo)準(zhǔn)的信息檢索工作需要擴(kuò)大范圍，從而有效處理 Web。

3.2 Web和受控集合的不同

互聯(lián)網(wǎng) Web是一個(gè)廣闊的充滿完全不受控制的異構(gòu)文件的集合。Web 上的文件,不但內(nèi)部格式極其不同,而且外部元信息也未必可用。例如,文件內(nèi)部的不同,有各自的語言(包括自然語言和編程語言),各自的詞匯(電子郵件地址,鏈接,郵編,電話號(hào)碼,產(chǎn)品號(hào)碼)，文件格式的不同(文本格式, html格式, pdf格式,圖像格式,聲音格式),并且甚至可能是機(jī)器產(chǎn)生的(日志文件或者數(shù)據(jù)庫的輸出文件) 。在另一方面,我們定義文件的外部元信息，從這些信息就可以推斷出一個(gè)文件的大概,但是元信息并不包含在文件中。文件外部元信息的例子,包括這樣一些信息： 來源的聲譽(yù),更新頻率,質(zhì)量,受歡迎程度 和 用法 , 和引用。不僅是外部元信息的可能來源千差萬別,而且衡量的方式也存在很多不同數(shù)量級(jí)的差異。舉例來說,比較從一個(gè)大型網(wǎng)站的主頁得到的使用信息,如，雅虎，目前每天獲得幾百萬的頁面瀏覽量， 而一個(gè)晦澀的歷史文章,可能每10年才能被瀏覽一次。顯而易見,搜索引擎必須嚴(yán)重區(qū)別對(duì)待這兩個(gè)條目。

另一個(gè)Web 和受控集合的較大差異是,幾乎沒有限制控制人們?cè)诰W(wǎng)上可以放什么。把這種靈活性的內(nèi)容發(fā)布和產(chǎn)生巨大影響的搜索引擎結(jié)合起來 ，去吸引訪問瀏覽量。 并且很多公司通過故意操縱搜索引擎來贏利，日益成為一個(gè)嚴(yán)重問題。這個(gè)問題在傳統(tǒng)的封閉的信息檢索系統(tǒng)中一直沒有發(fā)現(xiàn) 。另外,有趣的是我們注意到web搜索引擎使得想通過元數(shù)據(jù)操縱搜索引擎的努力基本上失敗了,因?yàn)榫W(wǎng)頁上的任何文字如果不是用來呈現(xiàn)給用戶的， 就是被濫用來操縱搜索引擎。甚至有許多公司專門操縱搜索引擎以達(dá)到贏利的目的。





（斷斷續(xù)續(xù)地把它翻完了。第4部分是Google搜索引擎最核心的一塊，有一些設(shè)計(jì)細(xì)節(jié)還不是很懂，希望能和大家一起探討。翻譯不當(dāng)之處還請(qǐng)各位指出，謝謝。）
4 系統(tǒng)剖析（System Anatomy）
首先，我們對(duì)架構(gòu)做一個(gè)高層的討論。接著，對(duì)重要的數(shù)據(jù)結(jié)構(gòu)有一個(gè)深入的描述。最后，我們將深入分析主要的應(yīng)用程序：爬蟲，索引和搜索。
4.1 Google架構(gòu)概述
[img]http://infolab.stanford.edu/~backrub/over.gif[/img]

圖1. Google高層架構(gòu)
在這一部分，我們將對(duì)圖1中整個(gè)系統(tǒng)是怎么運(yùn)行的有一個(gè)高層的概述。這一部分沒有提到應(yīng)用程序和數(shù)據(jù)結(jié)構(gòu)，這些會(huì)在接下來的幾部分里討論。考慮到效率，Google的大部分是用C或C++實(shí)現(xiàn)，可以在Solaris或者Linux下運(yùn)行。
在Google中，網(wǎng)頁抓取（下載web頁面）的工作由分布式的爬蟲（crawlers）完成。有一個(gè)URL服務(wù)器（圖1中的URL Server）把需要抓取的URL列表發(fā)送給爬蟲。網(wǎng)頁抓取好之后被發(fā)送到存儲(chǔ)服務(wù)器（圖1中的Store Server）。接著存儲(chǔ)服務(wù)器將抓取來的網(wǎng)頁壓縮并存放在倉庫(repository)里。每一個(gè)網(wǎng)頁都有一個(gè)與之相關(guān)的ID，叫docID。在一個(gè)網(wǎng)頁里每發(fā)現(xiàn)一個(gè)新的URL，就會(huì)賦予它一個(gè)ID。索引功能由索引器（圖1中的indexer）和排序器（圖1中的sorter）完成。索引器有很多功能。它從倉庫中讀取，解壓并分析文檔。每個(gè)文檔都被轉(zhuǎn)化成一個(gè)詞的集合，詞出現(xiàn)一次叫做一個(gè)命中（hits）。每條命中記錄了一個(gè)詞，這個(gè)詞在文檔中的位置，字體大小的近似值以及大小寫信息。索引器將這些命中分布到一系列“桶”（barrels）里面，建立一個(gè)半排序(partially sorted)的正排索引(forward index)。索引器還有一個(gè)重要的功能。它解析出每張網(wǎng)頁里面的所有鏈接，并把這些鏈接的相關(guān)重要信息存放在一個(gè)錨(anchors)文件里。這個(gè)文件包含了足夠的信息，以顯示每個(gè)鏈接從哪里連接過來，鏈到哪里和鏈接的描述。
URL分解器（URLresolver）讀取錨文件，將相對(duì)URL轉(zhuǎn)化為絕對(duì)URL，再轉(zhuǎn)化成docID。它為錨文本建立一個(gè)正排索引，并與錨指向的docID關(guān)聯(lián)起來。它還產(chǎn)生一個(gè)有docID對(duì)組成的鏈接數(shù)據(jù)庫。這個(gè)鏈接數(shù)據(jù)庫喲功能來計(jì)算所有文件的PageRank值。
排序器(sorter)對(duì)按照docID排序的(這里做了簡化，詳情見4.2.5小節(jié))“桶”(barrels)重新按照wordID排序，用于產(chǎn)生倒排索引(inverted index)。這個(gè)操作在恰當(dāng)?shù)臅r(shí)候進(jìn)行，所以需要很少的暫存空間。排序器還在倒排索引中建立一個(gè)wordID和偏移量的列表。一個(gè)叫DumpLexicon的程序把這個(gè)列表與由索引器產(chǎn)生的詞典結(jié)合起來，生成一個(gè)新的詞典，供搜索器（searcher）使用。搜索器由一個(gè)Web服務(wù)器運(yùn)行，根據(jù)DumpLexicon產(chǎn)生的詞典，倒排索引和PageRank值來回答查詢。
4.2 主要的數(shù)據(jù)結(jié)構(gòu)
Google的數(shù)據(jù)結(jié)構(gòu)經(jīng)過了優(yōu)化，這樣大量的文檔能夠在較低的成本下被抓取，索引和搜索。盡管CPU和I/O速率這些年以驚人的速度增長，但是每一個(gè)磁盤查找操作仍需要大概10微秒才能完成。Google在設(shè)計(jì)時(shí)盡量避免磁盤查找，這一設(shè)計(jì)也大大影響了數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。
4.2.1 BigFiles
BigFiles是分布在不同文件系統(tǒng)下面的虛擬文件，通過64位整數(shù)尋址。虛擬文件被自動(dòng)分配到不同文件系統(tǒng)。BigFiles的包還負(fù)責(zé)分配和釋放文件描述符（譯者注：牽涉到操作系統(tǒng)底層），因?yàn)椴僮飨到y(tǒng)提供的功能并不能滿足我們的要求。BigFiles還支持基本的壓縮選項(xiàng)。
4.2.2 數(shù)據(jù)倉庫（Repository）
[img]http://infolab.stanford.edu/~backrub/repos.gif[/img]

圖2. 數(shù)據(jù)倉庫的結(jié)構(gòu)
數(shù)據(jù)倉庫包括了每個(gè)web頁面的整個(gè)HTML代碼。每個(gè)頁面用zlib（參見RFC1950）壓縮。壓縮技術(shù)的選擇是速度和壓縮比的一個(gè)權(quán)衡。我們選擇zlib是因?yàn)樗膲嚎s速度要比bzip快很多。在數(shù)據(jù)倉庫上，bzip的壓縮比是4：1，而zlib的是3：1。在數(shù)據(jù)倉庫中，文檔一個(gè)一個(gè)連接存放，每個(gè)文檔有一個(gè)前綴，包括docID，長度和URL（如圖2）。要訪問這些文檔，數(shù)據(jù)倉庫不再需要其他的數(shù)據(jù)結(jié)構(gòu)。這使得保持?jǐn)?shù)據(jù)一致性和開發(fā)都更簡單；我們可以僅僅通過數(shù)據(jù)倉庫和一個(gè)記錄爬蟲錯(cuò)誤信息的文件來重建其他所有的數(shù)據(jù)結(jié)構(gòu)。
4.2.3 文檔索引（Document Index）
文檔索引保存了每個(gè)文檔的信息。它是一個(gè)根據(jù)docID排序的定長(fixed width)ISAM（索引順序訪問模式Index sequential access mode）索引。這些信息被存放在每個(gè)條目(entry)里面，包括當(dāng)前文檔狀態(tài)，指向數(shù)據(jù)倉庫的指針，文檔校驗(yàn)和(checksum)和各種統(tǒng)計(jì)數(shù)據(jù)。如果文檔已經(jīng)被抓取了，它還會(huì)包括一個(gè)指針，這個(gè)指針指向一個(gè)叫docinfo的變長(variable width)文件，里面記錄了文檔的URL和標(biāo)題。否則，這個(gè)指針將指向一個(gè)URL列表，里面只有URL。這樣設(shè)計(jì)的目的是為了有一個(gè)相對(duì)緊湊的數(shù)據(jù)結(jié)構(gòu)，在一次搜索操作中只需要一次磁盤查找就能取出一條記錄。
另外，還有一個(gè)文件用來將URL轉(zhuǎn)化成docID。這個(gè)文件是一個(gè)列表，包括URL校驗(yàn)和(checksum)和對(duì)應(yīng)的docID，根據(jù)校驗(yàn)和排序。為了找到某一個(gè)URL的docID，首先計(jì)算URL的校驗(yàn)和，然后在校驗(yàn)和文件里做一次二分查找，找到它的docID。URL轉(zhuǎn)化成docID是通過文件合并批量操作的。這個(gè)技術(shù)是在URL分解器（URL resolver）把URL轉(zhuǎn)化成docID時(shí)使用的。這種批量更新的模式很關(guān)鍵，因?yàn)槿绻覀優(yōu)槊總€(gè)鏈接做一次磁盤查找，一個(gè)磁盤需要1個(gè)月的時(shí)間才能為我們的3.22億條鏈接的數(shù)據(jù)集完成更新。
4.2.4 詞典（Lexicon）
詞典多種不同格式。與早前的系統(tǒng)相比，一個(gè)重要的變化是現(xiàn)在的詞典可以以合理的成本全部放在內(nèi)存里面。目前的實(shí)現(xiàn)中，我們把詞典放在一個(gè)256M的主存里面。現(xiàn)在的詞典有1.4千萬單詞（盡管一些非常用詞沒有被包含進(jìn)來）。它由兩部分實(shí)現(xiàn)——一個(gè)單詞列表（連接在一起，但是通過空白nulls分開）和一個(gè)指針的哈希表(hash table)。單詞列表還有一些附加信息，但是這些不在本篇文章的討論范圍。
4.2.5 命中列表（Hit Lists）
一個(gè)命中列表對(duì)應(yīng)著一個(gè)單詞在一個(gè)文檔中出現(xiàn)的位置、字體和大小寫信息的列表。命中列表占用了正排索引和倒排索引的大部分空間，所以怎樣盡可能有效的表示是很重要的。我們考慮了對(duì)位置，字體和大小寫信息的多種編碼方式——簡單編碼（3個(gè)整數(shù)），壓縮編碼（手工優(yōu)化分配比特）和霍夫曼編碼（Huffman coding）。命中（hit）的詳情見圖3。
[img]http://infolab.stanford.edu/~backrub/barrels.gif[/img]

圖3. 正、倒排索引和詞典
我們的壓縮編碼每個(gè)命中用到兩個(gè)字節(jié)(byte)。有兩種命中：特殊命中（fancy hit）和普通命中（plain hit）。特殊命中包括在URL，標(biāo)題，錨文本和meta標(biāo)簽上的命中。其他的都是普通命中。一個(gè)普通的命中包括一個(gè)表示大小寫的比特(bit)，字體大小，和12個(gè)bit表示的單詞在文件中的位置（所有比4095大的位置都被標(biāo)示為4096）。字體在文檔中的相對(duì)大小用3個(gè)比特表示（實(shí)際上只用到7個(gè)值，因?yàn)?11標(biāo)示一個(gè)特殊命中）。一個(gè)特殊命中包含一個(gè)大小寫比特，字體大小設(shè)置為7用來表示它是一個(gè)特殊命中，4個(gè)比特用來表示特殊命中的類型，8個(gè)比特表示位置。對(duì)于錨命中，表示位置的8個(gè)比特被分成兩部分，4個(gè)比特表示在錨文本中的位置，4個(gè)比特為錨文本所在docID的哈希（hash）值。由于一個(gè)詞并沒有那么多的錨文本，所以短語搜索受到一些限制。我們期望能更新錨命中的存儲(chǔ)方式能讓位置和docID哈希值能有更大的范圍。我們使用在一個(gè)文檔中的相對(duì)字體大小是因?yàn)樵谒阉鲿r(shí)，你并不希望對(duì)于內(nèi)容相同的不同文檔，僅僅因?yàn)橐粋€(gè)文檔字體比較大而有更高的評(píng)級(jí)（rank）。
命中列表的長度存在命中的前面。為了節(jié)省空間，命中列表的長度在正排索引中與wordID結(jié)合，在倒排索引中與docID結(jié)合。這樣就將長度分別限制在8個(gè)比特和5個(gè)比特（有一些技巧可以從wordID中借用8個(gè)比特）。如果長度超過了這個(gè)范圍，會(huì)在這些比特中使用轉(zhuǎn)義碼，在接下來的兩個(gè)字節(jié)(byte)里才存放真正的長度。
4.2.6 正排索引（Forward Index）
正排索引實(shí)際上已經(jīng)部分排序（partially sorted）。它被存放在一系列的桶（barrels）里面（我們用了64個(gè)）。每個(gè)桶保存了一定范圍內(nèi)的wordID。如果一個(gè)文檔包含了屬于某個(gè)桶的單詞，它的docID將被記錄在桶里面，后面接著一個(gè)wordID的列表和相應(yīng)的命中列表。這種結(jié)構(gòu)需要一點(diǎn)多余空間，因?yàn)榇鎯?chǔ)了重復(fù)的docID，由于桶的數(shù)量很小，所以存儲(chǔ)空間的差別很小，但是它能在排序器（sorter）建立最終索引的時(shí)候大大節(jié)省時(shí)間并降低了程序復(fù)雜度。更進(jìn)一步，我們并沒有存儲(chǔ)完整的wordID，而是存儲(chǔ)每個(gè)wordID相對(duì)于其對(duì)應(yīng)的桶里面最小wordID的差距。這樣我們只用到了24個(gè)比特，從而為命中列表長度（hit list length）留出了8個(gè)比特。
4.2.7 倒排索引（Inverted Index）
倒排索引與正排索引有著相同的桶，但是它們是先經(jīng)過排序器處理過的。對(duì)每一個(gè)合法的wordID，詞典包含了一個(gè)指向?qū)?yīng)的桶的指針。它指向一個(gè)docID的列表和相應(yīng)的命中列表。這個(gè)文檔列表顯示了有這個(gè)單詞出現(xiàn)的所有文檔。
一個(gè)重要的事情是如何對(duì)這個(gè)文檔列表排序。一個(gè)簡單的方法是按照docID排序。在多個(gè)單詞的查詢中，這種方法可以快速地完成兩個(gè)文檔列表的歸并。另一種方案是按照這個(gè)詞在文檔中出現(xiàn)的評(píng)分(ranking)排序。這種方式使得單個(gè)詞的查詢相當(dāng)簡單，并且多詞查詢的返回結(jié)果也很可能接近開頭（譯者注：這句不是很理解）。但是，歸并要困難得多。而且，開發(fā)也會(huì)困難得多，因?yàn)槊看卧u(píng)分函數(shù)變動(dòng)就需要重新建立整個(gè)索引。我們綜合了兩種方案，設(shè)計(jì)了兩個(gè)倒排桶集合——一個(gè)集合只包括標(biāo)題和錨命中（譯者注：后面簡稱短桶），另一個(gè)集合包含所有的命中（譯者注：后面簡稱全桶）。這樣我們首先檢查第一個(gè)桶集合，如果沒有足夠的匹配再檢查那個(gè)大一點(diǎn)的。
4.3 網(wǎng)頁抓取（Crawling the Web）
運(yùn)行網(wǎng)絡(luò)爬蟲是一項(xiàng)很有挑戰(zhàn)性的任務(wù)。這里不光涉及到巧妙的性能和可靠性問題，更重要的，還有社會(huì)問題。抓取是一個(gè)很脆弱的應(yīng)用，因?yàn)樗枰c成百上千各種各樣的web服務(wù)器和域名服務(wù)器交互，這些都不在系統(tǒng)的控制范圍之內(nèi)。
為了抓取幾億網(wǎng)頁，Google有一個(gè)快速的分布式爬蟲系統(tǒng)。一個(gè)單獨(dú)的URL服務(wù)器（URLserver）為多個(gè)爬蟲(crawler,一般是3個(gè))提供URL列表。URL服務(wù)器和爬蟲都用Python實(shí)現(xiàn)。每個(gè)爬蟲同時(shí)打開大概300個(gè)連接(connecton)。這樣才能保證足夠快地抓取速度。在高峰時(shí)期，系統(tǒng)通過4個(gè)爬蟲每秒鐘爬取100個(gè)網(wǎng)頁。這大概有600K每秒的數(shù)據(jù)傳輸。一個(gè)主要的性能壓力在DNS查詢(lookup)。每個(gè)爬蟲都維護(hù)一個(gè)自己的DNS緩存，這樣在它抓取網(wǎng)頁之前就不再需要每次都做DNS查詢。幾百個(gè)連接可能處于不同的狀態(tài)：查詢DNS，連接主機(jī)，發(fā)送請(qǐng)求，接受響應(yīng)。這些因素使得爬蟲成為系統(tǒng)里一個(gè)復(fù)雜的模塊。它用異步IO來管理事件，用一些隊(duì)列來管理頁面抓取的狀態(tài)。
事實(shí)證明，爬蟲連接了50多萬個(gè)服務(wù)器，產(chǎn)生了幾千萬條日志信息，會(huì)帶來大量的電子郵件和電話。因?yàn)楹芏嗳嗽诰W(wǎng)上，他們并不知道爬蟲是什么，因?yàn)檫@是他們第一次見到。幾乎每天，我們都會(huì)收到這樣的電子郵件：“哇，你看了好多我站上的頁面，你覺得怎么樣？”也有很多人并不知道爬蟲禁用協(xié)議（robots exclusion protocol），他們認(rèn)為可以通過在頁面上聲明“本頁面受版權(quán)保護(hù)，拒絕索引”就可以保護(hù)頁面，不用說，網(wǎng)絡(luò)爬蟲很難理解這樣的話。而且，由于涉及到大量的數(shù)據(jù)，一些意想不到的事情總會(huì)發(fā)生。比如，我們的系統(tǒng)試圖去抓取一個(gè)在線游戲。這導(dǎo)致了游戲中出現(xiàn)大量的垃圾消息！這個(gè)問題被證實(shí)是很容易解決的。但是往往我們?cè)谙螺d了幾千萬個(gè)頁面之后這個(gè)問題才被發(fā)現(xiàn)。因?yàn)榫W(wǎng)絡(luò)頁面和服務(wù)器總是在變化中，在爬蟲正式運(yùn)行在大部分的互聯(lián)網(wǎng)站點(diǎn)之前是不可能進(jìn)行測試的。不變的是，總有一些奇怪的錯(cuò)誤只會(huì)在一個(gè)頁面里面出現(xiàn)，并且導(dǎo)致爬蟲崩潰，或者更壞，導(dǎo)致不可預(yù)測的或者錯(cuò)誤的行為。需要訪問大量互聯(lián)網(wǎng)站點(diǎn)的系統(tǒng)需要設(shè)計(jì)得很健壯并且小心地測試。因?yàn)榇罅肯衽老x這樣的系統(tǒng)持續(xù)導(dǎo)致問題，所以需要大量的人力專門閱讀電子郵件，處理新出現(xiàn)遇到的問題。
4.4 網(wǎng)站索引（Indexing the Web）
解析——任何被設(shè)計(jì)來解析整個(gè)互聯(lián)網(wǎng)的解析器都必須處理大量可能的錯(cuò)誤。從HTML標(biāo)簽里面的錯(cuò)別字到一個(gè)標(biāo)簽里面上千字節(jié)的0，非ASCII字符，嵌套了幾百層的HTML標(biāo)簽，還有大量超乎人想象的錯(cuò)誤和“創(chuàng)意”。為了達(dá)到最快的速度，我們沒有使用YACC產(chǎn)生CFG（context free gramma，上下文無關(guān)文法）解析器，而是用flex配合它自己的棧生成了一個(gè)詞法分析器。開發(fā)這樣一個(gè)解析器需要大量的工作才能保證它的速度和健壯。
為文檔建立桶索引——每一個(gè)文檔解析過后，編碼存入桶里面。每一個(gè)單詞被內(nèi)存里的哈希表——詞典轉(zhuǎn)化成一個(gè)wordID。詞典哈希表新加的內(nèi)容都被記錄在一個(gè)文件里。單詞在被轉(zhuǎn)化成我wordID的時(shí)候，他們?cè)诋?dāng)前文檔中的出現(xiàn)會(huì)被翻譯成命中列表，并寫入正排桶(forward barrels)中。建立索引階段的并行操作主要的困難在于詞典需要共享。我們并沒有共享整個(gè)詞典，而是在內(nèi)存里保存一份基本詞典，固定的1千4百萬個(gè)單詞，多余的詞寫入一個(gè)日志文件。這樣，多個(gè)索引器就可以同時(shí)運(yùn)行，最后由一個(gè)索引器來處理這個(gè)記錄著多余單詞的小日志文件。
排序——為了產(chǎn)生倒排索引，排序器取出各個(gè)正排的桶，然后根據(jù)wordID排序來產(chǎn)生一個(gè)標(biāo)題和錨命中的倒排桶，和一個(gè)全文的倒排桶。每次處理一個(gè)桶，所以需要的暫存空間很少。而且，我們簡單地通過用盡可能多的機(jī)器運(yùn)行多個(gè)排序器做到排序的并行化，不同的排序器可以同時(shí)處理不同的桶。因?yàn)橥安⒉荒苋糠旁谥鞔胬锩?#xff0c;排序器會(huì)根據(jù)wordID和docID將它們進(jìn)一步分割成可以放在內(nèi)存里面的桶(basket)。接著，排序器將每個(gè)桶載入內(nèi)存，排好序，把內(nèi)容寫入短的倒排桶和完整的倒排桶。
4.5 搜索（Searching）
搜索的目標(biāo)是高效地返回高質(zhì)量的結(jié)果。很多大型的商業(yè)搜索引擎在效率方面看起來都有很大的進(jìn)步。所以我們更專注于搜索結(jié)果的質(zhì)量，但是我們相信我們的解決方案只要花一點(diǎn)精力就可以很好的應(yīng)用到商業(yè)的數(shù)據(jù)上。Google的查詢?cè)u(píng)估流程如圖4。
為了限制響應(yīng)時(shí)間，一旦某個(gè)數(shù)量(現(xiàn)在是40,000)的匹配文檔被找到，搜索器自動(dòng)跳到圖4中的第8步。這意味著有可能返回次優(yōu)的結(jié)果。我們現(xiàn)在在研究新的方法來解決這個(gè)問題。在過去，我們根據(jù)PageRank值排序，有較好的效果。
解析查詢（Query）。
把單詞轉(zhuǎn)化成wordID。
從每個(gè)單詞的短桶文檔列表開始查找。
掃描文檔列表直到有一個(gè)文檔匹配了所有的搜索詞語。
計(jì)算這個(gè)文檔對(duì)應(yīng)于查詢的評(píng)分。
如果我們到達(dá)短桶的文檔列表結(jié)尾，從每個(gè)單詞的全桶(full barrel)文檔列表開始查找，跳到第4步。
如果我們沒有到達(dá)任何文檔列表的結(jié)尾，跳到第4步。
根據(jù)評(píng)分對(duì)匹配的文檔排序，然后返回評(píng)分最高的k個(gè)。
圖4 Google查詢?cè)u(píng)估
4.5.1 評(píng)分系統(tǒng)（The Ranking System）
Google比典型的搜索引擎維護(hù)了根多的web文檔的信息。每一個(gè)命中列表（hitlist）包含了位置，字體和大小寫信息。而且，我們綜合考慮了錨文本命中和頁面的PageRank值。把所有的信息綜合成一個(gè)評(píng)分是很困難的。我們?cè)O(shè)計(jì)了評(píng)分函數(shù)保證沒有一個(gè)因素有太大的影響。首先，考慮簡單的情況——一個(gè)單詞的查詢。為了對(duì)一個(gè)單詞的查詢計(jì)算文檔的分值，Google首先為這個(gè)單詞查看這個(gè)文檔的命中列表。Google將命中分為不同類型（標(biāo)題，錨，URL，普通文本大字體，普通文本小字體，……），每一種類型都有自己的類型權(quán)重值（type-weight）。類型權(quán)重值構(gòu)成一個(gè)由類型尋址（indexed）的向量。Google數(shù)出命中列表中每種類型命中的數(shù)量。每個(gè)數(shù)量轉(zhuǎn)化成一個(gè)數(shù)量權(quán)重（count-weight）。數(shù)量權(quán)重開始隨著數(shù)量線性增長，但是很快停止增長，以保證單詞命中數(shù)多于某個(gè)數(shù)量之后對(duì)權(quán)重不再有影響。我們通過數(shù)量權(quán)重向量和類型權(quán)重向量的點(diǎn)乘為一個(gè)文檔算出一個(gè)IR分?jǐn)?shù)。最后這個(gè)IR分?jǐn)?shù)與PageRank綜合產(chǎn)生這個(gè)文檔最終的評(píng)分。
對(duì)于一個(gè)多詞搜索，情況要更復(fù)雜。現(xiàn)在，多個(gè)命中列表必須一次掃描完，這樣一個(gè)文檔中較近的命中才能比相距較遠(yuǎn)的命中有更高的評(píng)分。多個(gè)命中列表里的命中結(jié)合起來才能匹配出相鄰的命中。對(duì)每一個(gè)命中的匹配集(matched set)，會(huì)計(jì)算出一個(gè)接近度。接近度是基于兩個(gè)命中在文檔（或錨文本）中相隔多遠(yuǎn)計(jì)算的，但是被分為10個(gè)等級(jí)從短語匹配到“一點(diǎn)都不近”。不光要為每一種類型的命中計(jì)數(shù)，還要為每一種類型和接近度都計(jì)數(shù)。每一個(gè)類型和接近度的組有一個(gè)類型-接近度權(quán)重（type-prox-weight）。數(shù)量被轉(zhuǎn)化成數(shù)量權(quán)重。我們通過對(duì)數(shù)量權(quán)重和類型-接近度權(quán)重做點(diǎn)乘計(jì)算出IR分值。所有這些數(shù)字和矩陣都會(huì)在特殊的調(diào)試模式下與搜索結(jié)果一起顯示出來。這些顯示結(jié)果在開發(fā)評(píng)分系統(tǒng)的時(shí)候很有幫助。
4.5.2 反饋（Feedback）
評(píng)分函數(shù)有很多參數(shù)比如類型權(quán)重和類型-接近度權(quán)重。找出這些參數(shù)的權(quán)重值簡直就跟妖術(shù)一樣。為了調(diào)整這些參數(shù)，我們?cè)谒阉饕胬镉幸粋€(gè)用戶反饋機(jī)制。一個(gè)被信任的用戶可以選擇性地評(píng)價(jià)所有的返回結(jié)果。這個(gè)反饋被記錄下來。然后在我們改變?cè)u(píng)分系統(tǒng)的時(shí)候，我們能看到修改對(duì)之前評(píng)價(jià)過的搜索結(jié)果的影響。盡管這樣并不完美，但是這也給我們一些改變?cè)u(píng)分函數(shù)來影響搜索結(jié)果的想法。


5 結(jié)果與表現(xiàn)
衡量一個(gè)搜索引擎最重要的標(biāo)準(zhǔn)是其搜索結(jié)果的質(zhì)量。雖然如何做一個(gè)完整的用戶評(píng)估超越了本文的范圍，但是我們?cè)贕oogle身上得到的經(jīng)驗(yàn)，表明它提供結(jié)果，比主要商用搜索引擎對(duì)絕大多數(shù)搜索提供的結(jié)果更好。圖表4 表示的 Google對(duì)于搜索“比爾.克林頓”的結(jié)果，作為一個(gè)例子可以說明，對(duì)PageRank, anchor text （關(guān)鍵詞）,和proximity（相似度）的使用。這樣的搜索結(jié)果顯示了Google的特色。搜索結(jié)果被服務(wù)器串聯(lián)在一起。這樣的方法當(dāng)在需要對(duì)結(jié)果集篩選時(shí)非常有用。很大數(shù)量的結(jié)果會(huì)來自域名whitehouse.gov，有理由相信這個(gè)來源含有本次該搜索中被期望找到的結(jié)果。當(dāng)前，絕大多數(shù)主要的商用搜索引擎不會(huì)返回任何來自whitehouse.gov的結(jié)果，更不用說正確的結(jié)果。注意，第一個(gè)搜索到的連接沒有標(biāo)題，是因?yàn)樗皇亲ト〉媒Y(jié)果，而是Google 基于anchor text 決定這個(gè)結(jié)果是查詢所期望得到的好結(jié)果。同樣的，第15號(hào)結(jié)果是一個(gè)電子郵件地址，當(dāng)然這也是基于anchor text的結(jié)果，而非可抓取得結(jié)果。
所有結(jié)果都是合理的高質(zhì)量頁面，而且最后檢查，沒有壞連接。這主要?dú)w功于他們有很高的PageRank。PageRank的百分比使用紅色條形圖表示。最后，這里的結(jié)果中，沒有只有Bill沒有Clinton 或只有 Clinton 沒有Bill 的，這是因?yàn)槲覀冊(cè)陉P(guān)鍵詞出現(xiàn)時(shí)使用了非常重要的proximity。當(dāng)然對(duì)一個(gè)實(shí)際的對(duì)搜索引擎的質(zhì)量測試應(yīng)該包括廣泛的對(duì)用戶研究或者對(duì)搜索結(jié)果的分析，但是我們沒有時(shí)間做以上析。但是我們邀請(qǐng)讀者在 [url]http://google.stanford.edu/flp[/url] 自己測試Google。
5.1 存儲(chǔ)需求
除搜索質(zhì)量外，Gooogle被設(shè)計(jì)為能夠消化互聯(lián)網(wǎng)規(guī)模不斷增長帶來的效能問題。一方面，使用高效存儲(chǔ)。表一是對(duì)Google的統(tǒng)計(jì)與存儲(chǔ)需求的詳細(xì)分類，由于壓縮后的存儲(chǔ)體積為53GB，為源數(shù)據(jù)的三分之一多一點(diǎn)。就當(dāng)前的硬盤價(jià)格來說可以為有用資源提供廉價(jià)的相關(guān)存儲(chǔ)設(shè)備。更重要的是，搜索引擎使用的所有數(shù)據(jù)的總合需要相應(yīng)的存儲(chǔ)大約為55GB。此外，大多數(shù)查詢能被要求充分使用短反向索引 [short inverted index]，在更好的編碼與壓縮文檔索引后，一個(gè)高質(zhì)量的網(wǎng)絡(luò)搜索引擎可能只需要一臺(tái)有7GB存儲(chǔ)空間的新電腦。
5.2 系統(tǒng)性能
這對(duì)搜索引擎的抓取與索引來說很重要。這樣信息被轉(zhuǎn)化為數(shù)據(jù)的速度以及系統(tǒng)主要部分改變后被測試的速度都相對(duì)更快。就Google來說，主要操作包括：抓取，索引和排序。一旦硬盤被填滿、或命名服務(wù)器崩潰，或者其它問題導(dǎo)致系統(tǒng)停止，都很難度量抓取所需要化費(fèi)的時(shí)間。全部花費(fèi)在下載2千6百萬個(gè)頁面[包括錯(cuò)誤頁面]的時(shí)間大概是9天。但是如果系統(tǒng)運(yùn)行更為流暢，這個(gè)過程還可以更快，最后的1千1百個(gè)頁面只使用了63個(gè)小時(shí)，平均4百萬每天，每秒48.5頁。索引的運(yùn)行速度快于抓取速度的重要原因是我們花費(fèi)了足夠的時(shí)間來優(yōu)化索引程序，使它不要成為瓶頸。優(yōu)化包括對(duì)本地硬盤上的文檔的索引進(jìn)行大規(guī)模的升級(jí)和替換關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)。索引的速度達(dá)到大概54頁每秒。排序可以完全平行作業(yè)，使用四臺(tái)機(jī)器，整個(gè)處理時(shí)間花費(fèi)近24個(gè)小時(shí)。
5.3 搜索性能
提高搜索性能并不是本次我們研究的重點(diǎn)。當(dāng)前版本的Google返回多數(shù)查詢結(jié)果的時(shí)間是1到10秒。這個(gè)時(shí)間主要受到硬盤IO以及NFS[網(wǎng)絡(luò)文件系統(tǒng)，當(dāng)硬盤安置到許多機(jī)器上時(shí)使用] 的限制。進(jìn)一步說，Google沒有做任何優(yōu)化，例如查詢緩沖區(qū)，常用詞匯子索引，和其它常用的優(yōu)化技術(shù)。我們傾向于通過分布式，硬件，軟件，和算法的改進(jìn)來提高Google的速度。我們的目標(biāo)是每秒能處理幾百個(gè)請(qǐng)求。表2有幾個(gè)現(xiàn)在版本Google響應(yīng)查詢時(shí)間的例子。它們說明IO緩沖區(qū)對(duì)再次搜索速度的影響。

另外一篇參考譯文：[url]http://blog.csdn.net/fxy_2002/archive/2004/12/23/226604.aspx[/url]

總結(jié)

以上是生活随笔為你收集整理的Google的开始－－剖析大规模超文本网络搜索引擎的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。