搜索引擎是為妳提供信息“檢索”服務的網站。它利用壹些程序對互聯網上的所有信息進行分類，幫助人們在浩瀚的網絡中找到自己需要的信息。
早期的搜索引擎在互聯網上收集資源服務器的地址，將它們提供的資源劃分到不同的目錄中，然後逐層分類。
想要找到自己想要的信息的人，可以按照自己的分類壹層壹層的進入，然後最終可以到達目的地，找到自己想要的信息。
這其實是最原始的方式，只有在網上信息不多的情況下才適用。
隨著互聯網信息的幾何級增長，出現了真正的搜索引擎。這些搜索引擎知道網站上每個頁面的開頭，然後搜索互聯網上所有的超鏈接，並將所有代表超鏈接的單詞放入壹個數據庫中。
這就是現在搜索引擎的雛形。
用雅虎！隨著互聯網的出現，搜索引擎的發展也進入了壹個黃金時代，性能比以前更加優越。
今天的搜索引擎不僅僅是在網頁上搜索信息，它們變得更加全面和完善。
憑借搜索引擎雅虎的權威！例如，從1995年3月開始，雅虎由美籍華人楊致遠等人創立！從開始，到現在，它們從單壹的搜索引擎發展到電子商務、新聞信息服務、個人免費電子郵件服務等多種網絡服務，充分說明了搜索引擎從單壹到綜合發展的過程。
然而，由於搜索引擎的工作模式和互聯網的快速發展，搜索結果越來越不盡如人意。
例如，搜索單詞“計算機”可能會出現數百萬個頁面。
這是因為搜索引擎通過與網站的相關性來優化搜索結果，而網站的相關性是由關鍵詞在網站中的位置、網站名稱、標簽等公式決定的。
這就是為什麽搜索引擎的搜索結果多而雜的原因。
由於互聯網的發展和變化，搜索引擎中的數據庫必然包含死鏈接。
在本文中，我們介紹google，它是壹個大型搜索引擎的原型。搜索引擎廣泛應用於超文本。
谷歌的設計可以高效地抓取網頁並建立索引，其查詢結果優於現有的其他系統。
這個原型的全文和超鏈接數據庫包含至少24，000，000個網頁。
我們可以從://google.stanford.edu/下載
設計搜索引擎是壹項具有挑戰性的工作。
搜索引擎對數以億計的網頁進行索引，這些網頁包含大量非常不同的單詞。
每天回答成千上萬的問題。
在網絡中，大型搜索引擎雖然很重要，但是學術界很少研究。
此外，由於技術的快速發展和大量的網頁，現在構建壹個搜索引擎與三年前完全不同。
本文詳細介紹了我們的大型搜索引擎。據我們所知，這是第壹篇發表的論文如此詳細地描述了它。
除了在將傳統數據搜索技術應用於如此大量的網頁時遇到的問題之外，還有許多新的技術挑戰，包括在超文本中應用附加信息來改進搜索結果。
本文將解決這個問題，並描述如何使用超文本中的附加信息來構建壹個大型實用系統。
任何人都可以在網上隨意發布信息，如何有效處理這些無組織的超文本也是本文要註意的問題。
萬維網，搜索引擎，信息檢索，PageRank，Google 1引言Web給信息檢索帶來了新的挑戰。
網絡上的信息量在迅速增加，同時，也有新的沒有經驗的用戶來體驗網絡的藝術。
人們喜歡用超鏈接上網，通常從重要的網頁或雅虎這樣的搜索引擎開始。
大家都認為List有效地包含了大家感興趣的話題，但它主觀性強，建立和維護成本高，升級慢，不能包含所有深刻的話題。
基於關鍵詞的自動搜索引擎通常會返回太多低質量的匹配。
更糟糕的是，壹些廣告為了贏得人們的註意，竭力誤導自動搜索引擎。
我們建立了壹個大型搜索引擎來解決現有系統中的許多問題。
超文本結構的應用大大提高了查詢質量。
我們的系統命名為google，以googol的流行拼法命名，即100的100次方，與我們打造大型搜索引擎的目標不謀而合。
1.1網絡搜索引擎-擴大規模:1994-2000搜索引擎技術必須大幅擴大規模，以跟上呈指數增長的網頁數量。
1994年，第壹個網絡搜索引擎萬維網蠕蟲(WWWW)可以檢索110000個網頁和網頁文件。
到6月1994，11，頂級搜索引擎聲稱可以檢索2' 000' 000個網頁文件(從搜索引擎手表)到100' 000' 000。
可以預測，在2000年，將會有1' 000' 000' 000' 000以上。
同時，搜索引擎的流量也會以驚人的速度增長。
1997三四月份，萬維網蠕蟲平均每天收到1500次查詢。
在6月1997 165438+10月，Altavista聲稱每天處理大約20，000，000個查詢。
隨著網絡用戶的增長，到2000年，自動搜索引擎每天將處理上億次查詢。
我們系統的設計目標是解決很多問題，包括質量和可擴展性，並引入縮放搜索引擎技術，將其升級到如此大的數據量。
1.2 Google:與web壹起伸縮構建壹個能夠適應當今Web規模的搜索引擎將面臨諸多挑戰。
抓取網頁的速度必須足夠快，以保證它們是最新的。
存儲索引和文檔的空間必須足夠大。
索引系統必須能夠有效地處理數千億的數據。
處理查詢必須很快，達到每秒數百個查詢。
隨著Web的不斷增長，這些任務變得越來越艱巨。
但是硬件的執行效率和成本也在快速增加，可以部分抵消這些困難。
還有幾個值得註意的因素，如磁盤尋道時間和操作系統健壯性。
在設計Google的過程中，我們不僅考慮了Web的增長率，還考慮了技術的更新。
谷歌的設計可以很好地升級和處理海量數據集。
它可以有效地利用存儲空間來存儲索引。
可以快速有效地訪問優化的數據結構(參見4.2節)。
此外，我們希望與捕獲的文本文件和HTML頁面的數量相比，存儲和索引的成本盡可能小(參見附錄B)。
對於像Google這樣的集中式系統，通過采取這些措施可以獲得令人滿意的系統伸縮性。
1.3設計目標1.3.1提高搜索質量我們的主要目標是提高網頁搜索引擎的質量。
在1994中，有人認為建立壹個完整的搜索索引可以很容易地找到任何數據。
根據Web 1994-Navigator的最佳說法，“最佳的導航服務可以很容易地搜索到Web上的任何信息(所有數據都可以在那時登錄)”。
但是1997的Web就很不壹樣了。
最近，搜索引擎的用戶已經證實，索引的完整性不是評價搜索質量的唯壹標準。
用戶感興趣的搜索結果往往迷失在“垃圾結果”中。
事實上，截至6月1997 11，四大商業搜索引擎中只有壹個能夠找到自己(在搜索其名稱時，它在返回的十大結果中)。
造成這個問題的主要原因是文檔的索引號增加了幾個數量級，但是用戶可以閱讀的文檔數量並沒有增加。
用戶仍然只想看到前幾十個搜索結果。
因此，當* * *增加時，我們需要工具使結果準確(返回的前幾十個結果中相關文檔的數量)。
由於幾十個文檔是從幾千個多少有些關聯的文檔中挑選出來的，所以實際上，關聯度的概念指的是最好的文檔。
高準確率非常重要，即使是以響應(系統可以返回的相關文檔總數)為代價。
令人高興的是，超文本鏈接提供的信息有助於改進搜索和其他應用程序。
尤其是鏈接結構和鏈接文本，為相關性的判斷和高質量的過濾提供了大量的信息。
谷歌同時使用鏈接結構和錨文本(見2.1和2.2節)。
1.3.2搜索引擎的學術研究隨著時間的推移，除了飛速發展，Web也越來越商業化。
在1993中，只有1.5%的Web服務來自域名。
到1997，已經超過60%。
與此同時，搜索引擎已經從學術領域走向商業領域。
到目前為止，大多數搜索引擎都是公司所有，很少披露技術細節。
因此，搜索引擎技術仍在閉門造車，傾向於打廣告(見附錄A)。
Google的主要目標是促進學術領域在這方面的發展和理解。
另壹個設計目標是給妳壹個實用的系統。
應用對我們來說非常重要，因為在現代網絡系統中有大量有用的數據(我們認為最有趣的研究將涉及現代網絡系統中可用的大量使用數據)。
比如每天有幾千萬的學習。
但是，要得到這些數據是非常困難的，主要是因為它們沒有商業價值。
我們最終的設計目標是構建壹個能夠支持對海量網絡數據進行新研究的架構。
為了支持新的研究，谷歌以壓縮形式保存了實際捕獲的文檔。
設計google的目標之壹就是建立壹個環境，讓其他研究人員快速進入這個領域，處理海量的Web數據，得到滿意的結果，但是用其他方法很難得到結果。
系統建立時間很短，Google搭建的數據庫中已經使用了幾篇論文，更多的是在初級階段。
我們的另壹個目標是建立壹個類似太空實驗室的環境，在那裏研究人員甚至學生可以設計或在我們的海量網絡數據上做壹些實驗。
2.系統特性谷歌搜索引擎有兩個重要特性，有助於獲得高精度的搜索結果。
首先利用Web的鏈接結構計算每個頁面的排名值，這個結構叫做PageRank，在98頁會有詳細的描述。
第二，谷歌使用超鏈接來改善搜索結果。
2.1 PageRank:網頁排名參考(鏈接)圖是壹個重要的資源，但它在很大程度上被當今的搜索引擎所忽略。
我們建立了壹個有518' 000' 000個超鏈接的圖，這是壹個重要的樣本。
這些圖可以快速計算出壹個網頁的PageRank值，這是壹個客觀標準，符合人們心目中對壹個網頁重要性的評價。基礎是通過引用來判斷重要性。
因此，在web中，PageRank可以優化關鍵字查詢的結果。
對於大多數主題，我們在網頁標題查詢中使用PageRank優化簡單的文本匹配，得到了驚人的結果(可以從google.stanford.edu得到演示)。
PageRank在谷歌主系統的全文搜索方面也幫了不少忙。
2.1.1計算PageRank文獻檢索中的引用理論應用到網頁上，網頁中鏈接被引用的次數在壹定程度上反映了網頁的重要性和質量。
PageRank發展了這個思想，網頁之間的鏈接是不對等的。
PageRank的定義是這樣的:我們假設T1…Tn指向A頁(比如，它被引用了)。
參數d是制動系數，使得結果在0，1之間。
通常d等於0.85。
d將在下壹節詳細介紹。
C(A)定義為網頁A到其他網頁的鏈接數，網頁A的PageRank值由下式給出:PR(A)=(1-D)+D(PR(t 1)/C(t 1)+...+PR (TN)/C()。
PageRank或PR(A)可以通過簡單的叠代算法計算，網頁鏈接矩陣的主特征向量可以相應地歸壹化。
壹個中等規模的網站計算26000000頁的PageRank值需要幾個小時。
有些技術細節超出了本文的範圍。
2.1.2直覺判斷PageRank被視為用戶行為的模型。
我們假設上網是隨機的，我們不停的點鏈接，從不回，最後無聊了。另外，我們隨機選擇壹個網頁重新開始沖浪。
隨機訪問壹個網頁的可能性就是它的PageRank值。
剎車因素d是隨機訪問壹個網頁很無聊，隨機選擇另壹個網頁的可能性。
對於單個網頁或壹組網頁，制動系數d增加了壹個重要的變量。
這使得個人可以故意誤導系統以獲得更高的PageRank值。
我們還有其他的PageRank算法，見98頁。
另壹個直觀的判斷是，壹個網頁有很多頁面指向它，或者有壹些PageRank值高的頁面指向它，那麽這個網頁就很重要。
直觀來說，在Web中，壹個網頁被很多網頁引用，所以這個網頁值得壹看。
壹個網頁被雅虎這樣的重要主頁引用哪怕壹次，也是值得壹看的。
如果壹個網頁質量很低或者是死鏈接，雅虎這樣的主頁是不會鏈接到它的。
PageRank處理這兩個因素，通過網絡鏈接遞歸傳輸。
& ampnbsp2.2錨文本我們的搜索引擎對鏈接文本做了特殊處理。
大多數搜索引擎將鏈接文本與鏈接所在的頁面相關聯。
此外，將它與鏈接指向的網頁相關聯。
這有幾個好處。
首先，通常鏈接描述文本比網頁本身更準確地描述了網頁。
第二，鏈接描述詞可能鏈接到的文檔是文本搜索引擎無法檢索到的，比如圖像、程序、數據庫等。
有可能無法捕捉到返回的網頁。
註意哪些頁面抓不住會帶來壹些問題。
在將它們返回給用戶之前，無法檢測它們的有效性。
在這種情況下，搜索引擎可能會返回壹個根本不存在的網頁，但有壹個超鏈接指向它。
不過這個結果可以單列出來，所以很少出現這樣的問題。
鏈接描述文字是被鏈接到壹個網頁的宣傳。萬維網蠕蟲使用這種思想，主要是因為它有助於搜索非文本信息，可以用少量的下載文檔擴大搜索範圍。
我們廣泛使用鏈接描述，因為它有助於提高搜索結果的質量。
因為必須處理大量數據，所以有效地使用鏈接描述字存在壹些困難。
現在，我們可以捕獲24，000，000個網頁，並檢索超過259，000，000個鏈接描述。
2.3其他功能除了PageRank和應用鏈接描述，Google還有壹些其他功能。
第壹，所有的命中都有位置信息，因此它可以廣泛地用於搜索鄰近性。
第二，谷歌追蹤壹些視覺外觀細節，比如字體大小。
粗體大字母比其他單詞更重要。
第三，知識庫存儲原始全文網頁。
3工作網檢索的研究歷史較短。
萬維網蠕蟲()是最早的搜索引擎之壹。
後來出現了壹些學術研究的搜索引擎，現在大部分都是上市公司的。
相對於Web的成長和搜索引擎的重要性，如今關於搜索引擎技術的優秀論文少之又少。
據Michael maul din(Lycos Inc .首席科學家)稱:“各種服務(包括Lycos)都非常關註這些數據庫的細節。
雖然在搜索引擎的壹些功能上已經做了很多工作。
代表性工作包括交付現有商業搜索引擎的結果或建立小型個性化搜索引擎。
最後，有許多關於信息檢索系統的研究，特別是在良好控制的集合中。
在接下來的兩節中，我們將討論信息檢索系統中的哪些方面需要改進，以便在Web上更好地工作。
3.1信息檢索信息檢索系統誕生於幾年前，發展迅速。
然而，大多數信息檢索系統的研究對象是小規模的單壹組織結構，如科學論文或相關主題的新聞故事。
事實上，信息檢索的主要基準，文本檢索會議()，使用小規模和有組織的* * *作為他們的基準。
大規模語料庫的基準只有20GB，相比之下，我們抓取的2400萬個網頁占了147GB。
壹個在TREC運行良好的系統在網絡上可能不會產生好的結果。
例如，標準向量空間模型試圖返回最接近查詢請求的文檔，並將查詢請求和文檔都視為由出現在其中的單詞組成的向量。
在Web環境中，這種策略通常返回非常短的文檔，這些文檔通常是查詢詞加上幾個詞。
比如妳查詢“比爾·克林頓”，返回的網頁只包含“比爾·克林頓很爛”，這是我們從某大搜索引擎上看到的。
網上有壹些爭議。用戶應該更準確地表達他們想要查詢的內容，並在查詢請求中使用更多的詞。
我們強烈反對這種觀點。
如果用戶提出壹個類似“比爾·克林頓”的查詢請求，應該會得到理想的查詢結果，因為這個話題有很多高質量的信息。
就像給出的例子壹樣，我們認為為了有效地處理Web數據，需要開發信息檢索標準。
3.2具有有組織的結構的***(良好控制的集合)和Web之間的區別在於大量文檔的* * *是完全無組織的和異構的。
無論是內在信息還是隱含信息，Web上的文檔都存在著大量的異構性。
例如，文檔中使用不同的語言(人類語言和程序)、詞匯([電子郵件]地址、鏈接、郵政編碼、電話號碼、產品號)、類型(文本、HTML、PDF、圖像、聲音)，甚至壹些機器創建的文件(日誌文件或數據庫輸出)。
可以從文檔中推斷出來但沒有包含在文檔中的信息稱為隱含信息。
隱性信息包括來源的聲譽、更新頻率、質量、訪問和引用。
不僅隱含信息的可能來源多種多樣，而且探測到的信息差異也很大，差異可達幾個數量級。
例如，壹個重要的主頁，如雅虎，每天被訪問數百萬次，而匿名的歷史文章可能每十年才被訪問壹次。
顯然，搜索引擎處理這兩種信息的方式不同。
網絡和組織結構的另壹個明顯區別是，事實上，上傳信息到網絡上是沒有限制的。
靈活利用這壹點，可以發布任何對搜索引擎有重大影響的信息，封鎖路線，故意操縱搜索引擎牟利，已經成為壹個嚴重的問題。
傳統的封閉式信息檢索系統沒有提出這些問題。
它關註的是元數據的努力，而這在網絡搜索引擎中是不適用的，因為網頁中的任何文本都不會向用戶聲稱它試圖操縱搜索引擎。
甚至有些公司專門操縱搜索引擎牟利。
4系統分析首先，我們提供壹個關於架構的高層討論。
然後，詳細描述了重要的數據結構。
最後，主要應用:抓取網頁、索引和搜索都會被嚴格檢查。
圖1 .高層谷歌架構4.1谷歌架構概述在這壹節中，我們將看看整個系統是如何工作的(給出壹個高層)，如圖1所示。
本節不討論應用程序和數據結構，但將在以下幾節中討論。
出於效率考慮，Google大部分都是用C或c++實現的，可以在Solaris和Linux上運行。
在Google系統中，抓取網頁(下載網頁)是由幾個分布式爬蟲完成的。
URL服務器負責向爬蟲提供URL列表。
所捕獲的網頁被移交給存儲服務器storeserver。
然後，網頁被存儲服務器壓縮並存儲在存儲庫中。
每個網頁都有壹個名為docID的ID，當壹個新的URL從網頁中分離出來時，它會被分配壹個docID。
索引器和排序器負責建立索引index函數。
索引器從知識庫中讀取文檔，對其進行解壓縮和分析。
每個文檔被轉換成壹組單詞的情況稱為命中命中。
Hits記錄了單詞、單詞在文檔中的位置、最接近的字體大小和大小寫。
索引器將這些命中分配給壹組桶，以生成部分排序的索引。
索引器的另壹個重要功能是分析網頁中的所有鏈接，並將相關的重要信息存儲在鏈接描述錨文件中。
這個文件包含了足夠的信息，可以用來判斷每個鏈接的傳出和傳入節點的信息，以及鏈接文本。
URL解析器讀取鏈接描述錨文件，並將相對URL轉換為絕對URL，然後轉換為docID。
將鏈接描述文本編入索引，並將其與指向的docID相關聯。
同時建立由docID對組成的鏈接庫。
用於計算所有文檔的PageRank值。
按docID分類的桶被送到分類器，然後按wordID分類，建立倒排索引。
這個操作應該恰到好處，這樣幾乎不需要臨時存儲空間。
排序器還給出docID和offset的列表，並建立倒排索引。
壹個名為DumpLexicon的程序將這個列表與索引器生成的詞典結合起來，創建壹個新的詞典供搜索者使用。
這個搜索器使用Web服務器，使用DumpLexicon生成的詞典，使用上面提到的倒排索引和PageRank PageRank來回答用戶的問題。
4.2優化了主數據結構的Google數據結構，能夠以較小的成本抓取大量文檔，建立索引和查詢。
雖然近幾年CPU和輸入/輸出速率增長很快。
磁盤尋道仍然需要10毫秒。
在任何時候，谷歌系統的設計都是為了盡可能避免磁盤尋道。
這對數據結構的設計影響很大。
4.2.1大文件BigFiles是指由虛擬文件生成的多文件系統，由長度為64位的整數數據尋址。
多個文件系統之間的空間分配是自動完成的。
BigFiles包還處理已分配和未分配的文件描述符。
因為控制系統不能滿足我們的需求，BigFiles也支持基本的壓縮選項。
4.2.2知識庫圖2。知識庫數據結構知識庫包含每個網頁的所有HTML。
每個網頁都由zlib壓縮(參見RFC1950)。
壓縮技術的選擇應該同時考慮速度和壓縮率。
我們選擇zlib的速度，而不是壓縮率高的bzip。
bzip對於知識庫的壓縮比接近4: 1。
與zlib的壓縮比為3: 1。
文檔逐個存儲在知識庫中，以docID、長度和URL為前綴，如圖2所示。
訪問知識庫不需要其他數據結構。
這有助於數據的壹致性和升級。
要用其他數據結構重構系統，只需要修改知識庫和爬蟲錯誤列表文件。
4.2.3文件索引文件索引保存了文檔的壹些信息。
索引按照docID的順序排列，具有固定寬度的ISAM(索引順序訪問模式)。
每個記錄包括當前文件狀態、知識庫指針、文件校驗和以及各種統計表。
如果壹個文檔被捕獲，指針指向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命中列表命中列表是文檔中出現的單詞列表，包括位置、字號和大小寫。
命中列表占用大量空間，用於前向和反向索引。
因此，它的表示越有效越好。
我們考慮幾種方案來編碼位置、字體大小、簡單大小寫編碼(3個整數)、緊湊編碼(支持比特的最佳分配)和霍夫曼編碼。
有關Hit的詳細信息，請參見圖3。
我們的壓縮編碼每次點擊使用2個字節。
有兩種類型的擊球，特殊擊球和普通擊球。
特殊命中包含網址，標題，鏈接描述文本和元標簽。
普通命中包含其他壹切。
它包括大小寫特征位、字體大小和12位來描述單詞在文檔中的位置(所有超過4095的位置都標記為4096)。
字體大小用相對於文檔其他部分的相對大小來表示，占3位(實際上只用了7個值，因為111標誌是特殊命中)。
特殊命中由case特征位組成，字體大小為7表示是特殊命中，4位表示特殊命中的類型，8位表示位置。
對於anchor hit八位字節，4位被劃分以指示anchor中的位置，4位被用於指示anchor出現的docID的哈希表hash。
短語查詢是有限的，有些詞沒有足夠的錨。
我們希望更新anchor hit的存儲方式，解決地址位和docIDhash字段位不足的問題。