索引擎（search engines）是對互聯網上的信息資源進行搜集整理，然後供妳查詢的系統，它包括信息搜集、信息整理和用戶查詢三部分。
搜索引擎是壹個為妳提供信息“檢索”服務的網站，它使用某些程序把因特網上的所有信息歸類以幫助人們在茫茫網海中搜尋到所需要的信息。
早期的搜索引擎是把因特網中的資源服務器的地址收集起來，由其提供的資源的類型不同而分成不同的目錄，再壹層層地進行分類。
人們要找自己想要的信息可按他們的分類壹層層進入，就能最後到達目的地，找到自己想要的信息。
這其實是最原始的方式，只適用於因特網信息並不多的時候。
隨著因特網信息按幾何式增長，出現了真正意義上的搜索引擎，這些搜索引擎知道網站上每壹頁的開始，隨後搜索因特網上的所有超級鏈接，把代表超級鏈接的所有詞匯放入壹個數據庫。
這就是現在搜索引擎的原型。
隨著yahoo!的出現，搜索引擎的發展也進入了黃金時代，相比以前其性能更加優越。
現在的搜索引擎已經不只是單純的搜索網頁的信息了，它們已經變得更加綜合化，完美化了。
以搜索引擎權威yahoo!為例，從1995年3月由美籍華裔楊致遠等人創辦yahoo!開始，到現在，他們從壹個單壹的搜索引擎發展到現在有電子商務、新聞信息服務、個人免費電子信箱服務等多種網絡服務，充分說明了搜索引擎的發展從單壹到綜合的過程。
然而由於搜索引擎的工作方式和因特網的快速發展，使其搜索的結果讓人越來越不滿意。
例如，搜索“電腦”這個詞匯，就可能有數百萬頁的結果。
這是由於搜索引擎通過對網站的相關性來優化搜索結果，這種相關性又是由關鍵字在網站的位置、網站的名稱、 標簽等公式來決定的。
這就是使搜索引擎搜索結果多而雜的原因。
而搜索引擎中的數據庫因為因特網的發展變化也必然包含了死鏈接。
這篇文章中，我們介紹了google，它是壹個大型的搜索引擎（of a large-scale search engine）的原型，搜索引擎在超文本中應用廣泛。
Google的設計能夠高效地抓網頁並建立索引，它的查詢結果比其它現有系統都高明。
這個原型的全文和超連接的數據庫至少包含24‘000‘000個網頁。
我們可以從://google.stanford.edu/ 下載。
設計搜索引擎是壹項富有挑戰性的工作。
搜索引擎為上億個網頁建立索引，其中包含大量迥然不同的詞匯。
而且每天要回答成千上萬個查詢。
在網絡中，盡管大型搜索引擎非常重要，但是學術界卻很少研究它。
此外由於技術的快速發展和網頁的大量增加，現在建立壹個搜索引擎和三年前完全不同。
本文詳細介紹了我們的大型搜索引擎，據我們所知，在公開發表的論文中，這是第壹篇描述地如此詳細。
除了把傳統數據搜索技術應用到如此大量級網頁中所遇到的問題，還有許多新的技術挑戰，包括應用超文本中的附加信息改進搜索結果。
本文將解決這個問題，描述如何運用超文本中的附加信息，建立壹個大型實用系統。
任何人都可以在網上隨意發布信息，如何有效地處理這些無組織的超文本 *** ，也是本文要關註的問題。
關鍵詞 World Wide Web，搜索引擎，信息檢索，PageRank, Google 1 緒論 Web 給信息檢索帶來了新的挑戰。
Web上的信息量快速增長，同時不斷有毫無經驗的新用戶來體驗Web這門藝術。
人們喜歡用超級鏈接來網上沖浪，通常都以象Yahoo這樣重要的網頁或搜索引擎開始。
大家認為List(目錄)有效地包含了大家感興趣的主題，但是它具有主觀性，建立和維護的代價高，升級慢，不能包括所有深奧的主題。
基於關鍵詞的自動搜索引擎通常返回太多的低質量的匹配。
使問題更遭的是，壹些廣告為了贏得人們的關註想方設法誤導自動搜索引擎。
我們建立了壹個大型搜索引擎解決了現有系統中的很多問題。
應用超文本結構，大大提高了查詢質量。
我們的系統命名為google，取名自googol的通俗拼法，即10的100次方，這和我們的目標建立壹個大型搜索引擎不謀而合。
1.1網絡搜索引擎—升級換代（scaling up）：1994-2000 搜索引擎技術不得不快速升級（scale dramatically）跟上成倍增長的web數量。
1994年，第壹個Web搜索引擎，World Wide Web Worm(WWWW)可以檢索到110，000個網頁和Web的文件。
到1994年11月，頂級的搜索引擎聲稱可以檢索到2‘000’000（WebCrawler）至100‘000’000個網絡文件（來自 Search Engine Watch）。
可以預見到2000年，可檢索到的網頁將超過1‘000’000‘000。
同時，搜索引擎的訪問量也會以驚人的速度增長。
在1997年的三四月份，World Wide Web Worm 平均每天收到1500個查詢。
在1997年11月，Altavista 聲稱它每天要處理大約20’000’000個查詢。
隨著網絡用戶的增長，到2000年，自動搜索引擎每天將處理上億個查詢。
我們系統的設計目標要解決許多問題，包括質量和可升級性，引入升級搜索引擎技術（scaling search engine technology），把它升級到如此大量的數據上。
1.2 Google：跟上Web的步伐（Scaling with the Web）建立壹個能夠和當今web規模相適應的搜索引擎會面臨許多挑戰。
抓網頁技術必須足夠快，才能跟上網頁變化的速度（keep them up to date）。
存儲索引和文檔的空間必須足夠大。
索引系統必須能夠有效地處理上千億的數據。
處理查詢必須快，達到每秒能處理成百上千個查詢（hundreds to thousands per second.）。
隨著Web的不斷增長，這些任務變得越來越艱巨。
然而硬件的執行效率和成本也在快速增長，可以部分抵消這些困難。
還有幾個值得註意的因素，如磁盤的尋道時間（disk seek time），操作系統的效率（operating system robustness）。
在設計Google的過程中，我們既考慮了Web的增長速度，又考慮了技術的更新。
Google的設計能夠很好的升級處理海量數據集。
它能夠有效地利用存儲空間來存儲索引。
優化的數據結構能夠快速有效地存取（參考4.2節）。
進壹步，我們希望，相對於所抓取的文本文件和HTML網頁的數量而言，存儲和建立索引的代價盡可能的小（參考附錄B）。
對於象Google這樣的集中式系統，采取這些措施得到了令人滿意的系統可升級性（scaling properties）。
1. 3設計目標 1.3.1提高搜索質量我們的主要目標是提高Web搜索引擎的質量。
1994年，有人認為建立全搜索索引（a plete search index）可以使查找任何數據都變得容易。
根據Best of the Web 1994 -- Navigators ，“最好的導航服務可以使在Web上搜索任何信息都很容易（當時所有的數據都可以被登錄）”。
然而1997年的Web就迥然不同。
近來搜索引擎的用戶已經證實索引的完整性不是評價搜索質量的唯壹標準。
用戶感興趣的搜索結果往往湮沒在“垃圾結果Junk result”中。
實際上，到1997年11月為止，四大商業搜索引擎中只 有壹個能夠找到它自己（搜索自己名字時返回的前十個結果中有它自己）。
導致這壹問題的主要原因是文檔的索引數目增加了好幾個數量級，但是用戶能夠看的文檔數卻沒有增加。
用戶仍然只希望看前面幾十個搜索結果。
因此，當 *** 增大時，我們就需要工具使結果精確（在返回的前幾十個結果中，有關文檔的數量）。
由於是從成千上萬個有點相關的文檔中選出幾十個，實際上，相關的概念就是指最好的文檔。
高精確非常重要，甚至以響應（系統能夠返回的有關文檔的總數）為代價。
令人高興的是利用超文本鏈接提供的信息有助於改進搜索和其它應用 。
尤其是鏈接結構和鏈接文本，為相關性的判斷和高質量的過濾提供了大量的信息。
Google既利用了鏈接結構又用到了anchor文本（見2.1和2.2節）。
1.3.2搜索引擎的學術研究隨著時間的流逝，除了發展迅速，Web越來越商業化。
1993年，只有1.5%的Web服務是來自域名。
到1997年，超過了60%。
同時，搜索引擎從學術領域走進商業。
到現在大多數搜索引擎被公司所有，很少技公開術細節。
這就導致搜索引擎技術很大程度上仍然是暗箱操作，並傾向做廣告（見附錄A）。
Google的主要目標是推動學術領域在此方面的發展，和對它的了解。
另壹個設計目標是給大家壹個實用的系統。
應用對我們來說非常重要，因為現代網絡系統中存在大量的有用數據（us because we think some of the most interesting research will involve leveraging the vast amount of usage data that is available from modern web systems）。
例如，每天有幾千萬個研究。
然而，得到這些數據卻非常困難，主要因為它們沒有商業價值。
我們最後的設計目標是建立壹個體系結構能夠支持新的關於海量Web數據的研究。
為了支持新研究，Google以壓縮的形式保存了實際所抓到的文檔。
設計google的目標之壹就是要建立壹個環境使其他研究者能夠很快進入這個領域，處理海量Web數據，得到滿意的結果，而通過其它方法卻很難得到結果。
系統在短時間內被建立起來，已經有幾篇論文用到了Google建的數據庫，更多的在起步中。
我們的另壹個目標是建立壹個宇宙空間實驗室似的環境，在這裏研究者甚至學生都可以對我們的海量Web數據設計或做壹些實驗。
2. 系統特點 Google搜索引擎有兩個重要特點，有助於得到高精度的搜索結果。
第壹點，應用Web的鏈接結構計算每個網頁的Rank值，稱為PageRank，將在98頁詳細描述它。
第二點，Google利用超鏈接改進搜索結果。
2.1 PageRank:給網頁排序 Web的引用（鏈接）圖是重要的資源，卻被當今的搜索引擎很大程度上忽視了。
我們建立了壹個包含518‘000’000個超鏈接的圖，它是壹個具有重要意義的樣本。
這些圖能夠快速地計算網頁的PageRank值，它是壹個客觀的標準，較好的符合人們心目中對壹個網頁重要程度的評價，建立的基礎是通過引用判斷重要性。
因此在web中，PageRank能夠優化關鍵詞查詢的結果。
對於大多數的主題，在網頁標題查詢中用PageRank優化簡單文本匹配，我們得到了令人驚嘆的結果（從google.stanford.edu可以得到演示）。
對於Google主系統中的全文搜索，PageRank也幫了不少忙。
2.1.1計算PageRank 文獻檢索中的引用理論用到Web中，引用網頁的鏈接數，壹定程度上反映了該網頁的重要性和質量。
PageRank發展了這種思想，網頁間的鏈接是不平等的。
PageRank定義如下: 我們假設T1…Tn指向網頁A（例如，被引用）。
參數d是制動因子，使結果在0，1之間。
通常d等於0.85。
在下壹節將詳細介紹d。
C（A）定義為網頁A指向其它網頁的鏈接數，網頁A的PageRank值由下式給出： PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) 註意PageRank的形式，分布到各個網頁中，因此所有網頁的PageRank和是1。
PageRank或PR（A）可以用簡單的叠代算法計算，相應規格化Web鏈接矩陣的主特征向量。
中等規模的網站計算26‘000’000網頁的PageRank值要花費幾小時。
還有壹些技術細節超出了本文論述的範圍。
2.1.2直覺判斷 PageRank被看作用戶行為的模型。
我們假設網上沖浪是隨機的，不斷點擊鏈接，從不返回，最終煩了，另外隨機選壹個網頁重新開始沖浪。
隨機訪問壹個網頁的可能性就是它的PageRank值。
制動因子d是隨機訪問壹個網頁煩了的可能性，隨機另選壹個網頁。
對單個網頁或壹組網頁，壹個重要的變量加入到制動因子d中。
這允許個人可以故意地誤導系統，以得到較高的PageRank值。
我們還有其它的PageRank算法，見98頁。
另外的直覺判斷是壹個網頁有很多網頁指向它，或者壹些PageRank值高的網頁指向它，則這個網頁很重要。
直覺地，在Web中，壹個網頁被很多網頁引用，那麽這個網頁值得壹看。
壹個網頁被象Yahoo這樣重要的主頁引用即使壹次，也值得壹看。
如果壹個網頁的質量不高，或者是死鏈接，象Yahoo這樣的主頁不會鏈向它。
PageRank處理了這兩方面因素，並通過網絡鏈接遞歸地傳遞。
& nbsp; 2.2鏈接描述文字（Anchor Text）我們的搜索引擎對鏈接文本進行了特殊的處理。
大多數搜索引擎把鏈接文字和它所鏈向的網頁（the page that the link is on）聯系起來。
另外，把它和鏈接所指向的網頁聯系起來。
這有幾點好處。
第壹，通常鏈接描述文字比網頁本身更精確地描述該網頁。
第二，鏈接描述文字可能鏈向的文檔不能被文本搜索引擎檢索到，例如圖像，程序和數據庫。
有可能使返回的網頁不能被抓到。
註意哪些抓不到的網頁將會帶來壹些問題。
在返回給用戶前檢測不了它們的有效性。
這種情況搜索引擎可能返回壹個根本不存在的網頁，但是有超級鏈接指向它。
然而這種結果可以被挑出來的，所以此類的問題很少發生。
鏈接描述文字是對被鏈向網頁的宣傳，這個思想被用在World Wide Web Worm 中，主要因為它有助於搜索非文本信息，能夠用少量的已下載文檔擴大搜索範圍。
我們大量應用鏈接描述文字，因為它有助於提高搜索結果的質量。
有效地利用鏈接描述文字技術上存在壹些困難，因為必須處理大量的數據。
現在我們能抓到24‘000’000個網頁，已經檢索到259‘000’000多個鏈接描述文字。
2.3其它特點除了PageRank和應用鏈接描述文字外，Google還有壹些其它特點。
第壹,所有hit都有位置信息，所以它可以在搜索中廣泛應用鄰近性（proximity）。
第二，Google跟蹤壹些可視化外表細節，例如字號。
黑體大號字比其它文字更重要。
第三，知識庫存儲了原始的全文網頁。
3有關工作 Web檢索研究的歷史簡短。
World Wide Web Worm（）是最早的搜索引擎之壹。
後來出現了壹些用於學術研究的搜索引擎，現在它們中的大多數被上市公司擁有。
與Web的增長和搜索引擎的重要性相比，有關當今搜索引擎技術的優秀論文相當少。
根據Michael Mauldin（Lycos Inc的首席科學家）) ，“各種各樣的服務（包括Lycos）非常關註這些數據庫的細節。
”雖然在搜索引擎的某些特點上做了大量工作。
具有代表性的工作有，對現有商業搜索引擎的結果進行傳遞，或建立小型的個性化的搜索引擎。
最後有關信息檢索系統的研究很多，尤其在有組織機構 *** （well controlled collections）方面。
在下面兩節，我們將討論在信息檢索系統中的哪些領域需要改進以便更好的工作在Web上。
3.1信息檢索信息檢索系統誕生在幾年前，並發展迅速。
然而大多數信息檢索系統研究的對象是小規模的單壹的有組織結構的 *** ，例如科學論文集，或相關主題的新聞故事。
實際上，信息檢索的主要基準，the Text Retrieval Conference（），用小規模的、有組織結構的 *** 作為它們的基準。
大型文集基準只有20GB，相比之下，我們抓到的24000000個網頁占147GB。
在TREC上工作良好的系統，在Web上卻不壹定產生好的結果。
例如，標準向量空間模型企圖返回和查詢請求最相近的文檔，把查詢請求和文檔都看作由出現在它們中的詞匯組成的向量。
在Web環境下，這種策略常常返回非常短的文檔，這些文檔往往是查詢詞再加幾個字。
例如，查詢“Bill Clinton”，返回的網頁只包含“Bill Clinton Sucks”，這是我們從壹個主要搜索引擎中看到的。
網絡上有些爭議，用戶應該更準確地表達他們想查詢什麽，在他們的查詢請求中用更多的詞。
我們強烈反對這種觀點。
如果用戶提出象“Bill Clinton”這樣的查詢請求，應該得到理想的查詢結果，因為這個主題有許多高質量的信息。
象所給的例子，我們認為信息檢索標準需要發展，以便有效地處理Web數據。
3.2有組織結構的 *** （Well Controlled Collections）與Web的不同點 Web是完全無組織的異構的大量文檔的 *** 。
Web中的文檔無論內在信息還是隱含信息都存在大量的異構性。
例如，文檔內部就用了不同的語言（既有人類語言又有程序），詞匯（[email]地址，鏈接，郵政編碼，電話號碼，產品號），類型（文本，HTML，PDF，圖像，聲音），有些甚至是機器創建的文件（log文件，或數據庫的輸出）。
可以從文檔中推斷出來，但並不包含在文檔中的信息稱為隱含信息。
隱含信息包括來源的信譽，更新頻率，質量，訪問量和引用。
不但隱含信息的可能來源各種各樣，而且被檢測的信息也大不相同，相差可達好幾個數量級。
例如，壹個重要主頁的使用量，象Yahoo 每天瀏覽數達到上百萬次，於此相比無名的歷史文章可能十年才被訪問壹次。
很明顯，搜索引擎對這兩類信息的處理是不同的。
Web與有組織結構 *** 之間的另外壹個明顯區別是，事實上，向Web上傳信息沒有任何限制。
靈活利用這點可以發布任何對搜索引擎影響重大的信息，使路由阻塞，加上為牟利故意操縱搜索引擎，這些已經成為壹個嚴重的問題。
這些問題還沒有被傳統的封閉的信息檢索系統所提出來。
它關心的是元數據的努力，這在Web搜索引擎中卻不適用，因為網頁中的任何文本都不會向用戶聲稱企圖操縱搜索引擎。
甚至有些公司為牟利專門操縱搜索引擎。
4 系統分析（System Anatomy）首先，我們提供高水平的有關體系結構的討論。
然後 ，詳細描述重要的數據結構。
最後，主要應用：抓網頁，索引，搜索將被嚴格地檢查。
Figure 1. High Level Google Architecture 4.1Google體系結構概述這壹節，我們將看看整個系統是如何工作的（give a high level），見圖1。
本節不討論應用和數據結構，在後幾節中討論。
為了效率大部分Google是用c或c++實現的，既可以在Solaris也可以在Linux上運行。
Google系統中，抓網頁（下載網頁）是由幾個分布式crawlers完成的。
壹個URL服務器負責向crawlers提供URL列表。
抓來的網頁交給存儲服務器storeserver。
然後，由存儲服務器壓縮網頁並把它們存到知識庫repository中。
每個網頁都有壹個ID，稱作docID，當新URL從網頁中分析出時，就被分配壹個docID。
由索引器和排序器負責建立索引index function。
索引器從知識庫中讀取文檔，對其解壓縮和分析。
每個文檔被轉換成壹組詞的出現情況，稱作命中hits。
Hits紀錄了詞，詞在文檔中的位置，最接近的字號，大小寫。
索引器把這些hits分配到壹組桶barrel中，產生經過部分排序後的索引。
索引器的另壹個重要功能是分析網頁中所有的鏈接，將有關的重要信息存在鏈接描述anchors文件中。
該文件包含了足夠的信息，可以用來判斷每個鏈接鏈出鏈入節點的信息，和鏈接文本。
URL分解器resolver閱讀鏈接描述anchors文件，並把相對URL轉換成絕對URL，再轉換成docID。
為鏈接描述文本編制索引，並與它所指向的docID關聯起來。
同時建立由docID對組成的鏈接數據庫。
用於計算所有文檔的PageRank值。
用docID分類後的barrels，送給排序器sorter，再根據wordID進行分類，建立反向索引inverted index。
這個操作要恰到好處，以便幾乎不需要暫存空間。
排序器還給出docID和偏移量列表，建立反向索引。
壹個叫DumpLexicon的程序把這個列表和由索引器產生的字典結合在壹起，建立壹個新的字典，供搜索器使用。
這個搜索器就是利用壹個Web服務器，使用由DumpLexicon所生成的字典，利用上述反向索引以及頁面等級PageRank來回答用戶的提問。
4.2主要數據結構經過優化的Google數據結構，能夠用較小的代價抓取大量文檔，建立索引和查詢。
雖然近幾年CPU和輸入輸出速率迅速提高。
磁盤尋道仍然需要10ms。
任何時候Google系統的設計都盡可能地避免磁盤尋道。
這對數據結構的設計影響很大。
4.2.1大文件大文件BigFiles是指虛擬文件生成的多文件系統，用長度是64位的整型數據尋址。
多文件系統之間的空間分配是自動完成的。
BigFiles包也處理已分配和未分配文件描述符。
由於操縱系統不能滿足我們的需要，BigFiles也支持基本的壓縮選項。
4.2.2知識庫 Figure 2. Repository Data Structure 知識庫包含每個網頁的全部HTML。
每個網頁用zlib（見RFC1950）壓縮。
壓縮技術的選擇既要考慮速度又要考慮壓縮率。
我們選擇zlib的速度而不是壓縮率很高的bzip。
知識庫用bzip的壓縮率接近4：1。
而用zlib的壓縮率是3：1。
文檔壹個挨著壹個的存儲在知識庫中，前綴是docID，長度，URL，見圖2。
訪問知識庫不需要其它的數據結構。
這有助於數據壹致性和升級。
用其它數據結構重構系統，我們只需要修改知識庫和crawler錯誤列表文件。
4.2.3文件索引文件索引保存了有關文檔的壹些信息。
索引以docID的順序排列，定寬ISAM（Index sequential access mode）。
每條記錄包括當前文件狀態，壹個指向知識庫的指針，文件校驗和，各種統計表。
如果壹個文檔已經被抓到，指針指向docinfo文件，該文件的寬度可變，包含了URL和標題。
否則指針指向包含這個URL的URL列表。
這種設計考慮到簡潔的數據結構，以及在查詢中只需要壹個磁盤尋道時間就能夠訪問壹條記錄。
還有壹個文件用於把URL轉換成docID。
它是URL校驗和與相應docID的列表，按校驗和排序。
要想知道某個URL的docID，需要計算URL的校驗和，然後在校驗和文件中執行二進制查找，找到它的docID。
通過對這個文件進行合並，可以把壹批URL轉換成對應的docID。
URL分析器用這項技術把URL轉換成docID。
這種成批更新的模式是至關重要的，否則每個鏈接都需要壹次查詢，假如用壹塊磁盤，322‘000’000個鏈接的數據 *** 將花費壹個多月的時間。
4.2.4詞典詞典有幾種不同的形式。
和以前系統的重要不同是，詞典對內存的要求可以在合理的價格內。
現在實現的系統，壹臺256M內存的機器就可以把詞典裝入到內存中。
現在的詞典包含14000000詞匯（雖然壹些很少用的詞匯沒有加入到詞典中）。
它執行分兩部分—詞匯表（用null分隔的連續串）和指針的哈希表。
不同的函數，詞匯表有壹些輔助信息，這超出了本文論述的範圍。
4.2.5 hit list hit list是壹篇文檔中所出現的詞的列表，包括位置，字號，大小寫。
Hit list占很大空間，用在正向和反向索引中。
因此，它的表示形式越有效越好。
我們考慮了幾種方案來編碼位置，字號，大小寫—簡單編碼（3個整型數），緊湊編碼（支持優化分配比特位），哈夫曼編碼。
Hit的詳細信息見圖3。
我們的緊湊編碼每個hit用2字節。
有兩種類型hit，特殊hit和普通hit。
特殊hit包含URL，標題，鏈接描述文字，meta tag。
普通hit包含其它每件事。
它包括大小寫特征位，字號，12比特用於描述詞在文檔中的位置（所有超過4095的位置標記為4096）。
字號采用相對於文檔的其它部分的相對大小表示，占3比特(實際只用7個值，因為111標誌是特殊hit)。
特殊hit由大小寫特征位，字號位為7表示它是特殊hit，用4比特表示特殊hit的類型，8比特表示位置。
對於anchor hit八比特位置位分出4比特用來表示在anchor中的位置，4比特用於表明anchor出現的哈希表hash of the docID。
短語查詢是有限的，對某些詞沒有足夠多的anchor。
我們希望更新anchor hit的存儲方式，以便解決地址位和docIDhash域位數不足的問題。