【正文】 。結果常常是好笑的，并且超出用戶的眼界，他們常?；倚膯蕷饫速M了寶貴的時間。例如，一個最流行的商業(yè)搜索引擎搜索“Bill Clillton”的結果是the Bill Clinton Joke of the Day: April 14, 1997。Google的 設計目標是隨著Web的快速發(fā)展提供高質量的搜索結果，容易找到信息。為此，Google大量應用超文本信息包括鏈接結構和鏈接文本。Google還用到了相鄰性和字號信息。評價搜索引擎是困難的，我們主觀地發(fā)現(xiàn)Google的搜索質量比當今商業(yè)搜索引擎高。通過PageRank分析鏈接結構使Google能夠評價網頁的質量。用鏈接文本描述鏈接所指向的網頁有助于搜索引擎返回相關的結果（某種程度上提高了質量）。最后，利用相鄰性信息大大提高了很多搜索的相關性。 ，Google設計成可升級的?？臻g和時間必須高效，處理整個Web時固定的幾個因素非常重要。實現(xiàn)Google系統(tǒng)，CPU、訪存、內存容量、磁盤尋道時間、磁盤吞吐量、磁盤容量、網絡IO都是瓶頸。在一些操作中，已經改進的Google克服了一些瓶頸。Google的主要數(shù)據結構能夠有效利用存儲空間。進一步，網頁爬行，索引，排序已經足夠建立大部分web索引，共24000000個網頁，用時不到一星期。我們希望能在一個月內建立100000000網頁的索引。 Google不僅是高質量的搜索引擎，它還是研究工具。Google搜集的數(shù)據已經用在許多其它論文中，提交給學術會議和許多其它方式。最近的研究，例如[Abiteboul 97]，提出了Web查詢的局限性，不需要網絡就可以回答。這說明Google不僅是重要的研究工具，而且必不可少，應用廣泛。我們希望Google是全世界研究者的資源，帶動搜索引擎技術的更新?lián)Q代。 7致謝 Scott Hassan and Alan Steremberg評價了Google的改進。他們的才智無可替代，作者由衷地感謝他們。感謝Hector GarciaMolina, Rajeev Motwani, Jeff Ullman, and Terry Winograd和全部WebBase開發(fā)組的支持和富有深刻見解的討論。最后感謝IBM，Intel，Sun和投資者的慷慨支持，為我們提供設備。這里所描述的研究是Stanford綜合數(shù)字圖書館計劃的一部分，由國家科學自然基金支持，合作協(xié)議號IRI9411306。DARPA ，NASA，Interva研究，Stanford數(shù)字圖書館計劃的工業(yè)合作伙伴也為這項合作協(xié)議提供了資金。參考文獻 ? Google的設計目標是可升級到10億網頁。我們的磁盤和機器大概能處理這么多網頁。系統(tǒng)各個部分耗費的總時間是并行的和線性的。包括網頁爬行機器人，索引器和排序器。擴展后我們認為大多數(shù)數(shù)據結構運行良好。然而10億網頁接近所有常用操作系統(tǒng)的極限（我們目前運行在Solaris和Linux上）。包括主存地址，開放文件描述符的數(shù)量，網絡socket和帶寬，以及其它因素。我們認為當網頁數(shù)量大大超過10億網頁時，會大大增加系統(tǒng)復雜性。 ，海量文本索引的成本比較公平。當然帶寬需求高的其它應用如視頻，越來越普遍。但是，與多媒體例如視頻相比，文本產品的成本低，因此文本仍然普遍。 圖2 Google系統(tǒng)的工作流程圖 (注：原圖來自Sergey Brin and Lawrence Page, The Anatomy of a LargeScale Hypertextual. Web Search Engine, 1998. ) ①Google使用高速的分布式爬行器(Crawler)系統(tǒng)中的漫游遍歷器(Googlebot)定時地遍歷網頁，將遍歷到的網頁送到存儲服務器(Store Server)中。 ②存儲服務器使用zlib格式壓縮軟件將這些網頁進行無損壓縮處理后存入數(shù)據庫Repository中。Repository獲得了每個網頁的完全Html代碼后，對其壓縮后的網頁及URL進行分析，記錄下網頁長度、URL、URL長度和網頁內容，并賦予每個網頁一個文檔號(docID)，以便當系統(tǒng)出現(xiàn)故障的時候，可以及時完整地進行網頁的數(shù)據恢復。 ③索引器(Indexer)從Repository中讀取數(shù)據，以后做以下四步工作： ④(a)將讀取的數(shù)據解壓縮后進行分析，它將網頁中每個有意義的詞進行統(tǒng)計后，轉化為關鍵詞(wordID)的若干索引項(Hits)，生成索引項列表，該列表包括關鍵詞、關鍵詞的位置、關鍵詞的大小和大小寫狀態(tài)等。索引項列表被存入到數(shù)據桶(Barrels)中，并生成以文檔號(docID)部分排序的順排檔索引。 索引項根據其重要程度分為兩種：當索引項中的關鍵詞出現(xiàn)在URL、標題、錨文本(Anchor Text)和標簽中時，表示該索引項比較重要，稱為特殊索引項(Fancy Hits)；其余情況則稱為普通索引項(Plain Hits)。在系統(tǒng)中每個Hit用兩個字節(jié)(byte)存儲結構表示：特殊索引項用1位(bit)表示大小寫，用二進制代碼111(占3位)表示是特殊索引項，其余12位有4位表示特殊索引項的類型(即hit是出現(xiàn)在URL、標題、鏈接結點還是標簽中)，剩下8位表示hit在網頁中的具體位置；普通索引項是用1位表示大小寫，3位表示字體大小，其余12位表示在網頁中的具體位置。 順排檔索引和Hit的存儲結構如圖3所示。 圖3 順排檔索引和Hit的存儲結構 值得注意的是，當特殊索引項來自Anchor Text時，特殊索引項用來表示位置的信息（8位）將分為兩部分：4位表示Anchor Text出現(xiàn)的具體位置，另4位則用來與表示Anchor Text所鏈接網頁的docID相連接，這個docID是由URL Resolver經過轉化存入順排檔索引的。 (b)索引器除了對網頁中有意義的詞進行分析外，還分析網頁的所有超文本鏈接，將其Anchor Text、URL指向等關鍵信息存入到Anchor文檔庫中。 (c)索引器生成一個索引詞表(Lexicon)，它包括兩個部分：關鍵詞的列表和指針列表，用于倒排檔文檔相連接(如圖3所示)。 (d)索引器還將分析過的網頁編排成一個與Repository相連接的文檔索引(Document Index)，并記錄下網頁的URL和標題，以便可以準確查找出在Repository中存儲的原網頁內容。而且把沒有分析的網頁傳給URL Server，以便在下一次工作流程中進行索引分析。 ⑤URL分析器（URL Resolver）讀取Anchor文檔中的信息，然后做⑥中的工作。 ⑥(a)將其錨文本(Anchor Text)所指向的URL轉換成網頁的docID；(b)將該docID與原網頁的docID形成“鏈接對”，存入Link數(shù)據庫中；(c)將Anchor Text指向的網頁的docID與順排檔特殊索引項Anchor Hits相連接。 ⑦數(shù)據庫Link記錄了網頁的鏈接關系，用來計算網頁的PageRank值。 ⑧文檔索引(Document Index)把沒有進行索引分析的網頁傳遞給URL Server，URL Server則向Crawler提供待遍歷的URL，這樣，這些未被索引的網頁在下一次工作流程中將被索引分析。 ⑨排序器（Sorter）對數(shù)據桶(Barrels)的順排檔索引重新進行排序，生成以關鍵詞(wordID)為索引的倒排檔索引。倒排檔索引結構如圖4所示： 圖4 倒排檔索引結構 ⑩將生成的倒排檔索引與先前由索引器產生的索引詞表(Lexicon)相連接產生一個新的索引詞表供搜索器(Searcher)使用。搜索器的功能是由網頁服務器實現(xiàn)的，根據新產生的索引詞表結合上述的文檔索引(Document Index)和Link數(shù)據庫計算的網頁PageRank值來匹配檢索。 在執(zhí)行檢索時，Google通常遵循以下步驟（以下所指的是單個檢索詞的情況）： (1)將檢索詞轉化成相應的wordID； (2)利用Lexicon，檢索出包含該wordID的網頁的docID； (3)根據與Lexicon相連的倒排檔索引，分析各網頁中的相關索引項的情況，計算各網頁和檢索詞的匹配程度，必要時調用順排檔索引； (4)根據各網頁的匹配程度，結合根據Link產生的相應網頁的PageRank情況，對檢索結果進行排序； (5)調用Document Index中的docID及其相應的URL，將排序結果生成檢索結果的最終列表，提供給檢索用戶。 用戶檢索包含多個檢索詞的情況與以上單個檢索詞的情況類似：先做單個檢索詞的檢索，然后根據檢索式中檢索符號的要求進行必要的布爾操作或其他操作。