【正文】 S. Rajagopalan. Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text. Seventh International Web Conference (WWW 98).Delphi,NASA，Interva研究，Stanford數(shù)字圖書館計劃的工業(yè)合作伙伴也為這項合作協(xié)議提供了資金。所描述的研究是Stanford綜合數(shù)字圖書館計劃的一部分，由國家科學(xué)自然基金支持，合作協(xié)議號IRI9411306。最后感謝IBM，Intel，Sun和投資者的慷慨支持，為我們提供設(shè)備。他們的才智無可替代，作者由衷地感謝他們。我們希望Google是全世界研究者的資源，帶動搜索引擎技術(shù)的更新?lián)Q代。Web查詢的局限性，不需要網(wǎng)絡(luò)就可以回答。Google搜集的數(shù)據(jù)已經(jīng)用在許多其它論文中，提交給學(xué)術(shù)會議和許多其它方式。Google一億網(wǎng)頁的索引。進(jìn)一步，網(wǎng)頁爬行，索引，排序已經(jīng)足夠建立大部分web索引，共2千四百萬個網(wǎng)頁，用時不到一星期。在一些操作中，已經(jīng)改進(jìn)的Google克服了一些瓶頸。實現(xiàn)Google系統(tǒng)，CPU、訪存、內(nèi)存容了搜索質(zhì)量，Google設(shè)計成可升級的。最后，利用相鄰性信息大大提高了很多搜索的相關(guān)性。通過PageRank分析鏈接結(jié)構(gòu)使Google能夠評價網(wǎng)頁的質(zhì)量。Google還用到了相鄰性和字號信息。為此，Google大量應(yīng)用超文本信息包括鏈接結(jié)構(gòu)和鏈接例如，一個最流行的商業(yè)搜索引擎搜索“Bill Clillton”的結(jié)果是the Bill Clinton Joke of the Day: April 14, 1997。今Web搜索引擎用戶所面臨的最大問題是搜索結(jié)果的質(zhì)量。高質(zhì)量搜索Web搜索引擎提供了豐富的研究課題。對于鏈我們正在擴(kuò)大鏈接結(jié)構(gòu)和鏈接文本的應(yīng)用。我們還計劃支持用戶上下文算術(shù)符號，否定，填充。受需求驅(qū)動，用代理cache創(chuàng)建搜索數(shù)據(jù)庫是一個有前途的研究領(lǐng)域。這另一個需要研究的領(lǐng)域是更新。一些簡單的改進(jìn)提高了效率包括請型Web搜索引擎是個復(fù)雜的系統(tǒng)，還有很多事情要做。進(jìn)一步說，Google是一個收集網(wǎng)頁，建立索引，執(zhí)行搜索請求的完整的體系結(jié)構(gòu)。主要目標(biāo)是在快速發(fā)展的World Wide Web上提供高質(zhì)量的搜索結(jié)果。它們說明IO緩沖區(qū)對再次搜索速度的影響。我們的目標(biāo)是每秒能處理幾百個請求。進(jìn)一步說，Google沒有做任何優(yōu)化，例如查詢緩沖區(qū)，常用詞匯子索引，和其它常用的優(yōu)化技術(shù)。這個時間主要受到硬盤IO以及NFS[網(wǎng)絡(luò)文件系統(tǒng)，當(dāng)硬盤安置到許多機(jī)器上時使用]提高搜索性能并不是本次我們研究的重點。索引的速度達(dá)到大概54頁每秒。索引的運(yùn)行速度快于抓取速度的重要原因是我們花費了足夠的時間來優(yōu)化索引程序，使它不要成為瓶頸。全部花費在下載2千6百萬個頁面[包括錯誤頁面]的時間大概是9天。就Google來說，主要操作包括：抓取，索引和排序。這對搜索引擎的抓取與索引來說很重要。此外，大多數(shù)查詢能被要求充分使用短反向索引就當(dāng)前的硬盤價格來說可以為有用資源提供廉價的相關(guān)存儲設(shè)備。一方面，使用高效存儲。自己測試Google。但是我們邀請讀者在的，這是因為我們在關(guān)鍵詞出現(xiàn)時使用了非常重要的proximity。Clinton最后，這里的結(jié)果中，沒有只有Bill沒有Clinton這主要歸功于他們有很高的PageRank。決定這個結(jié)果是查詢所期望得到的好結(jié)果。注意，第一個搜索到的連接沒有標(biāo)題，是因為它不是抓取得結(jié)果，而是Google有理由相信這個來源含有本次該搜索中被期望找到的結(jié)果。搜索結(jié)果被服務(wù)器串聯(lián)在一起。（關(guān)鍵詞）,和proximity（相似度）的使用。表示的雖然如何做一個完整的用戶評估超越了本文的范圍，但是我們在Google身上得到的經(jīng)驗，表明它提供結(jié)果，比主要商用搜索引擎對絕大多數(shù)搜索提供的結(jié)果更好。盡管這樣并不完美，但是這也給我們一些改變評分函數(shù)來影響搜索結(jié)果的想法。這個反饋被記錄下來。為了調(diào)整這些參數(shù)，我們在搜索引擎里有一個用戶反饋機(jī)制。反饋評分函數(shù)有很多參數(shù)比如類型權(quán)重和類型接近度權(quán)重。這些顯示結(jié)果在開發(fā)評分系統(tǒng)的時候很有幫助我們通過對數(shù)量權(quán)重和類型接近度權(quán)重做點乘計算出IR分值。每一個類型和接近度的組有一個類型接近度權(quán)重（typeproxweight）。接近度是基于兩個命中在文檔（或錨文本）中相隔多遠(yuǎn)計算的，但是被分為10個等級從短語匹配到“一點都不近”。多個命中列表里的命中結(jié)合起來才能匹配出相鄰的命中。對于一個多詞搜索，情況要更復(fù)雜。最后這個IR分?jǐn)?shù)與PageRank綜合產(chǎn)生這個文檔最終的評分。數(shù)量權(quán)重開始隨著數(shù)量線性增長，但是很快停止增長，以保證單詞命中數(shù)多于某個數(shù)量之后對權(quán)重不再有影響。Google數(shù)出命中列表中每種類型命中的數(shù)量。Google將命中分為不同類型（標(biāo)題，錨，URL，普通文本大字體，普通文本小字體，……），每一種類型都有自己的類型權(quán)重值（typeweight）。首先，考慮簡單的情況——一個單詞的查詢。把所有的信息綜合成一個評分是很困難的。每一個命中列表（hitlist）包含了位置，字體和大小寫信息。圖4 Google查詢評估，跳到第4步。（Query）。在過去，我們根據(jù)PageRank值排序，有較好的效果。這意味著有可能返回次優(yōu)的結(jié)果。所以我們更專注于搜索結(jié)果的質(zhì)量，但是我們相信我們的解決方案只要花一點精力就可以很好的應(yīng)用到商業(yè)的數(shù)據(jù)上。搜索的目標(biāo)是高效地返回高質(zhì)量的結(jié)果。因為桶并不能全部放在主存里面，排序器會根據(jù)wordID和docID將它們進(jìn)一步分割成可以放在內(nèi)存里面的桶(basket)。每次處理一個桶，所以需要的暫存空間很少。這樣，多個索引器就可以同時運(yùn)行，最后由一個索引器來處理這個記錄著多余單詞的小日志文件。建立索引階段的并行操作主要的困難在于詞典需要共享。詞典哈希表新加的內(nèi)容都被記錄在一個文件里。為文檔建立桶索引——每一個文檔解析過后，編碼存入桶里面。為了達(dá)到最快的速度，我們沒有使用YACC產(chǎn)生CFG（context free gramma，上下文無關(guān)文法）解析器，而是用flex配合它自己的棧生成了一個詞法分析器。解析——任何被設(shè)計來解析整個互聯(lián)網(wǎng)的解析器都必須處理大量可能的錯誤。因為大量像爬蟲這樣的系統(tǒng)持續(xù)導(dǎo)致問題，所以需要大量的人力專門閱讀電子郵件，處理新出現(xiàn)遇到的問題。不變的是，總有一些奇怪的錯誤只會在一個頁面里面出現(xiàn)，并且導(dǎo)致爬蟲崩潰，或者更壞，導(dǎo)致不可預(yù)測的或者錯誤的行為。但是往往我們在下載了幾千萬個頁面之后這個問題才被發(fā)現(xiàn)。比如，我們的系統(tǒng)試圖去抓取一個在線游戲。幾乎每天，我們都會收到這樣的電子郵件：“哇，你看了好多我站上的頁面，你覺得怎么樣？”也有很多人并不知道爬蟲禁用協(xié)議（robots exclusion protocol），他們認(rèn)為可以通過在頁面上聲明“本頁面受版權(quán)保護(hù)，拒絕索引”就可以保護(hù)頁面，不用說，網(wǎng)絡(luò)爬蟲很難理解這樣的話。事實證明，爬蟲連接了50多萬個服務(wù)器，產(chǎn)生了幾千萬條日志信息，會帶來大量的電子郵件和電話。它用異步IO來管理事件，用一些隊列來管理頁面抓取的狀態(tài)。幾百個連接可能處于不同的狀態(tài)：查詢DNS，連接主機(jī)，發(fā)送請求，接受響應(yīng)。一個主要的性能壓力在DNS查詢。在高峰時期，系統(tǒng)通過4個爬蟲每秒鐘爬取100個網(wǎng)頁。每個爬蟲同時打開大概300個連接。一個單獨的URL服務(wù)器（URLserver）為多個爬蟲(crawler,一般是3個)提供URL列表。這里不光涉及到巧妙的性能和可靠性問題，更重要的，還有社會問題。抓取網(wǎng)頁我們綜合了兩種方案，設(shè)計了兩個倒排桶集合——一個集合只包括標(biāo)題和錨命中，另一個集合包含所有的命中。但是，歸并要困難得多。另一種方案是按照這個詞在文檔中出現(xiàn)的評分(ranking)排序。一個簡單的方法是按照docID排序。它指向一個docID的列表和相應(yīng)的命中列表。反向索引反向索引與正向索引有著相同的桶，但是它們是先經(jīng)過排序器處理過的。這樣我們只用到了24個比特，從而為命中列表長度（hit list length）留出了8個比特。這種結(jié)構(gòu)需要一點多余空間，因為存儲了重復(fù)的docID，由于桶的數(shù)量很小，所以存儲空間的差別很小，但是它能在排序器（sorter）建立最終索引的時候大大節(jié)省時間并降低了程序復(fù)雜度。每個桶保存了一定范圍內(nèi)的wordID。正向索引正向索引實際上已經(jīng)部分排序。如果長度超過了這個范圍，會在這些比特中使用轉(zhuǎn)義碼，在接下來的兩個字節(jié)(byte)里才存放真正的長度。為了節(jié)省空間，命中列表的長度在正向索引中與wordID結(jié)合，在反向索引中與docID結(jié)合。我們使用在一個文檔中的相對字體大小是因為在搜索時，你并不希望對于內(nèi)容相同的不同文檔，僅僅因為一個文檔字體比較大而有更高的評級（rank）。由于一個詞并沒有那么多的錨文本，所以短語搜索受到一些限制。一個特殊命中包含一個大小寫比特，字體大小設(shè)置為7用來表示它是一個特殊命中，4個比特用來表示特殊命中的類型，8個比特表示位置。一個普通的命中包括一個表示大小寫的比特(bit)，字體大小，和12個bit表示的單詞在文件中的位置（所有比4095大的位置都被標(biāo)示為4096）。特殊命中包括在URL，標(biāo)題，錨文本和meta標(biāo)簽上的命中。正、倒排索引和詞典我們的壓縮編碼每個命中用到兩個字節(jié)(byte)。命中（hit）的詳情見圖3。命中列表占用了正向索引和反向索引的大部分空間，所以怎樣盡可能有效的表示是很重要的。不同的函數(shù)詞列表有一些輔助的信息，超出了本文以詳細(xì)解釋的范圍。現(xiàn)在的詞典包含14萬詞匯（雖然一些很少用的詞匯沒有加入到詞典中）。和以前系統(tǒng)的重要改進(jìn)是，詞典對內(nèi)存的要求可以在合理的價格內(nèi)。這種成批更新的模式是至關(guān)重要的，否則每個鏈接都需要一次查詢，假如用一塊磁盤，322百萬個鏈接的數(shù)據(jù)集合將URL分析器用這項技要想知道某個URL的docID，需要計算URL的校驗和，然后在校驗和文件中執(zhí)行二進(jìn)制查找，找到它的docID。還有一個文件用于把URL轉(zhuǎn)換成docID。否則指針指向包含這個URL的URL列表。每條記錄包括當(dāng)前文件狀態(tài)，一個指向知識庫的指針，文件校驗和，各種統(tǒng)計表。ISAM (索引順序訪問模式)這有助于數(shù)據(jù)一致性和升級。文檔一個挨著一個的存儲在知識庫中，前綴是docID，長度，URL，見圖2。而用zlib的壓我們選擇zlib的速度而不是壓縮率很高的bzip。知識庫知識庫包含每個網(wǎng)頁的全部HTML。由于操縱系統(tǒng)不能滿足我們的需要，BigFiles也支持基本的壓縮選項。多文件系統(tǒng)之間的空間分配是自動完成的。任何時候Google系統(tǒng)的設(shè)計都盡可能地避免磁盤尋道。雖然近幾年CPU和輸入輸出速率迅速提高。個列表和由索引器產(chǎn)生的字典結(jié)合在一起，建立一個新的字典，供搜索器使用。排序器還給出docID和偏移量列表，建立反向索引。排序器sorter，再根據(jù)wordID進(jìn)行分類，建立反向索引inverted index。用于計算所有文檔的PageRank值。指向的docID關(guān)聯(lián)起來。URL分解器resolver閱讀鏈接描述anchors文件，并把相對URL轉(zhuǎn)換成絕對URL，再轉(zhuǎn)換成docID。該文件包含了足夠的信息，可以用來判斷每個鏈接鏈出鏈入節(jié)點的信息，和鏈接文本。索引器把這些hits分配到一組桶barrel中，產(chǎn)生經(jīng)過部分排序后的索引。Hits索引器從知識庫中讀取文檔，對其解壓縮和分析。每個網(wǎng)頁都有一個ID，稱作docID，當(dāng)新URL從網(wǎng)頁中分析出時，就被分配一個docID。storeserver。一個URL服務(wù)器負(fù)責(zé)向crawlers提供URL列表。Google本節(jié)不討論應(yīng)用和數(shù)據(jù)結(jié)構(gòu)，在后幾節(jié)中討論。高層次Google體系結(jié)構(gòu)圖最后，主要應(yīng)用：抓網(wǎng)頁，索引，搜索將會深度探討。系統(tǒng)分析首先，我們提供高層次的有關(guān)體系結(jié)構(gòu)的討論。它關(guān)心的是元數(shù)據(jù)的努力，這在Web搜索引擎中卻不適用，因為網(wǎng)頁中的任何文本都不會向用戶聲稱企圖操縱搜索引擎。這些問題還沒有被傳統(tǒng)的封閉的信息檢索系統(tǒng)所提出來。靈活利用這點可以發(fā)布任何每天瀏覽數(shù)達(dá)到上百萬次，于此相比無名的歷史文章可能十年才被訪問一次。可能來源各種各樣，而且被檢測的信息也大不相同，相差可達(dá)好幾個數(shù)量級。隱含信息包括來源的信譽(yù)，更新頻率，質(zhì)量，訪問量和引用?？梢詮奈臋n中推斷出例如，文檔內(nèi)部就用了不同的語言（既有人類語言又有程序），詞匯（地址，鏈接，郵政編Web像所給的例子，我們認(rèn)為信息檢索標(biāo)準(zhǔn)需要發(fā)展，以便有效地處理Web數(shù)據(jù)。我們強(qiáng)烈反對這種觀點。例如，查詢“Bill Clinton”，返回的網(wǎng)頁只包含“Bill Clinton Sucks”，這是我們從一個主要搜索引擎中看到的。例如，標(biāo)準(zhǔn)向量空間模型企圖返回和查詢請求最相近的文檔，把查詢請求和文檔都看作由出現(xiàn)在它們中的詞匯組成的向量。大型文集基準(zhǔn)只有20GB，相比之下，我們抓到的24萬個網(wǎng)頁占147GB。例如,主題相關(guān)的科學(xué)論文或新聞故事。信息檢索系統(tǒng)誕生在幾年前，并發(fā)展很好。在下面兩節(jié)，我們將討論在信息檢索系統(tǒng)中的哪些領(lǐng)域需要改進(jìn)以便更好的工作在Web上。結(jié)果進(jìn)行傳遞，或建立小型的個性化的搜索引擎?！彪m然在搜索引擎的某些特點上做了大量工作。根據(jù)Michael Mauldin（Lycos Inc的首席科學(xué)家）)與Web的增長和搜索引擎的重要性相比，World Wide Web Worm（WWWW）是最早的搜索引擎之一。3更大的字的權(quán)重要高于其他的。一,它有所有命中數(shù)的位置信息，所以它可以在搜索中廣泛應(yīng)用鄰近性?，F(xiàn)在我們能抓到24萬個網(wǎng)頁，已經(jīng)檢索到259萬多個鏈接描述文字。我們大量應(yīng)用鏈接描述文字，因為它有助于提高搜索結(jié)果的質(zhì)量。鏈接描述文字是對被引用網(wǎng)頁的描述這個思想被用在World Wide Web Worm這種情況搜索引擎可能返回一個根本不存在的網(wǎng)頁，但是有超級鏈接指向它。注意那抓不到的網(wǎng)頁將會帶來一些問題。例如圖像，程序和數(shù)據(jù)庫。第一，通常鏈接描述文字比網(wǎng)頁本身更精確地描述該網(wǎng)頁。另外，把它和鏈接所指向的網(wǎng)頁聯(lián)系起來。