大規(guī)模超文本網(wǎng)頁(yè)搜索引擎的分析

作為Google輝煌的起始，這篇文章非常有紀(jì)念價(jià)值，但是文中提到的內(nèi)容因年代久遠(yuǎn)，已經(jīng)和時(shí)下最新的技術(shù)有了不少差異。但是文中的思想還是有很多借鑒價(jià)值。因本人水平有限，對(duì)文中內(nèi)容可能會(huì)有理解不當(dāng)之處，請(qǐng)您查閱英文原版。大規(guī)模的超文本網(wǎng)頁(yè)搜索引擎的分析SergeyBrinandLawrencePage{sergey，page}@ComputerScienceDepartment，StanfordUniversity，Stanford，CA94305摘要在本文中我們討論Google，一個(gè)充分利用超文本文件結(jié)構(gòu)進(jìn)行搜索的大規(guī)模搜索引擎的原型。Google可以有效地對(duì)網(wǎng)絡(luò)資源進(jìn)行爬行搜索和索引，比目前已經(jīng)存在的系統(tǒng)有更令人滿(mǎn)意的搜索結(jié)果。該原型的數(shù)據(jù)庫(kù)包括2400萬(wàn)頁(yè)面的全文和之間的鏈接，可通過(guò)/訪(fǎng)問(wèn)。設(shè)計(jì)一個(gè)搜索引擎是一種具挑戰(zhàn)性的任務(wù)。搜索引擎索索引數(shù)以?xún)|計(jì)的不同類(lèi)型的網(wǎng)頁(yè)并每天給出過(guò)千萬(wàn)的查詢(xún)的答案。盡管大型搜索引擎對(duì)于網(wǎng)站非常重要，但是已完成的、對(duì)于大型搜索引擎的學(xué)術(shù)上的研究卻很少。此外，由于技術(shù)上的突飛猛進(jìn)和網(wǎng)頁(yè)的急劇增加，在當(dāng)前，創(chuàng)建一個(gè)搜索引擎和三年前已不可同日而語(yǔ)。本文提供了一種深入的描述，與Web增殖快速進(jìn)展今日創(chuàng)建Web搜索引擎是三年前很大不同。本文提供了到目前為止，對(duì)于我們大型的網(wǎng)頁(yè)所搜引擎的深入的描述，這是第一個(gè)這樣詳細(xì)的公共描述。除了如何把傳統(tǒng)的搜索技術(shù)擴(kuò)展到前所未有的海量數(shù)據(jù)，還有新的技術(shù)挑戰(zhàn)涉及到了使用超文本中存在的其他附加信息產(chǎn)生更好的搜索結(jié)果。本文解決這樣一個(gè)問(wèn)題，如何建立一個(gè)可以利用超文本中存在的其他附加信息的實(shí)用的大型系統(tǒng)，同時(shí)我們也研究一下如何有效處理任何人都能發(fā)布他們想發(fā)布的包含任何信息的大量自由鏈接的問(wèn)題。關(guān)鍵字：互聯(lián)網(wǎng)，搜索引擎，文獻(xiàn)檢索，PageRank，Google1.簡(jiǎn)介(注：本文由兩個(gè)版本--較長(zhǎng)的完整版本和一個(gè)較短的印刷的版本。完整版本提供在網(wǎng)絡(luò)上和會(huì)議的CD-ROM上)。Web給信息檢索帶來(lái)了新的挑戰(zhàn)。Web上的信息量快速增長(zhǎng)，同時(shí)不斷有毫無(wú)經(jīng)驗(yàn)的新用戶(hù)來(lái)體驗(yàn)Web這門(mén)藝術(shù)。人們喜歡用超級(jí)鏈接來(lái)網(wǎng)上沖浪，通常都以象Yahoo這樣重要的網(wǎng)頁(yè)或搜索引擎開(kāi)始。人工維護(hù)的網(wǎng)站列表能有效的覆蓋受歡迎的流行的站點(diǎn)，但是它具有主觀性，建立和維護(hù)的代價(jià)高，升級(jí)慢，不能包括所有深?yuàn)W的主題?；陉P(guān)鍵詞的自動(dòng)搜索引擎通常返回太多的低質(zhì)量的匹配。使問(wèn)題更遭的是，一些廣告為了贏得人們的關(guān)注想方設(shè)法誤導(dǎo)自動(dòng)搜索引擎。我們建立了一個(gè)大型搜索引擎解決了現(xiàn)有系統(tǒng)中的很多問(wèn)題。應(yīng)用超文本結(jié)構(gòu)，提供高質(zhì)量的查詢(xún)結(jié)果，我們的系統(tǒng)命名為google，取名自googol的通俗拼法，即10的100次方，這和我們的目標(biāo)建立一個(gè)大型搜索引擎較好的符合。1.1網(wǎng)絡(luò)搜索引擎—升級(jí)換代：1994-2000搜索引擎技術(shù)不得不快速升級(jí)跟上成倍增長(zhǎng)的網(wǎng)站數(shù)量。1994年，第一個(gè)Web搜索引擎，WorldWideWebWorm(WWWW)擁有110，000個(gè)網(wǎng)頁(yè)和網(wǎng)站可訪(fǎng)問(wèn)文檔的索引。到1994年11月，頂級(jí)的搜索引擎聲稱(chēng)可以檢索到2萬(wàn)(WebCrawler)100萬(wàn)個(gè)網(wǎng)絡(luò)文件(來(lái)自搜索引擎監(jiān)視)?？梢灶A(yù)見(jiàn)到2000年，可檢索到的網(wǎng)頁(yè)將超過(guò)10億。同時(shí)，搜索引擎的訪(fǎng)問(wèn)量也會(huì)以驚人的速度增長(zhǎng)。在1997年的三四月份，WorldWideWebWorm平均每天收到1500個(gè)查詢(xún)。在1997年11月，Altavista聲稱(chēng)它每天要處理大約20’百萬(wàn)個(gè)查詢(xún)。隨著網(wǎng)絡(luò)用戶(hù)的增長(zhǎng)，可以預(yù)見(jiàn)到到2000年，自動(dòng)搜索引擎每天將處理上億個(gè)查詢(xún)。我們系統(tǒng)的設(shè)計(jì)目標(biāo)要解決許多問(wèn)題，包括質(zhì)量和可升級(jí)性，引入升級(jí)搜索引擎技術(shù)，把它升級(jí)到如此大量的數(shù)據(jù)上。1.2Google：升級(jí)與網(wǎng)絡(luò)建立一個(gè)能夠和當(dāng)今web規(guī)模相適應(yīng)的搜索引擎會(huì)面臨許多挑戰(zhàn)。抓網(wǎng)頁(yè)技術(shù)必須足夠快并且保持是最新的版本。存儲(chǔ)空間必須高效的存儲(chǔ)索引和文檔。索引系統(tǒng)必須能夠高效地處理上百億GB的數(shù)據(jù)。處理查詢(xún)必須快，達(dá)到每秒能處理成百上千個(gè)查詢(xún)。隨著Web的不斷增長(zhǎng)，這些任務(wù)變得越來(lái)越艱巨。然而硬件的性能和成本也在快速增長(zhǎng)，可以部分抵消這些困難。然而，還有幾個(gè)值得例外，如磁盤(pán)的尋道時(shí)間，操作系統(tǒng)的效率。在設(shè)計(jì)Google的過(guò)程中，我們既考慮了網(wǎng)絡(luò)的增長(zhǎng)速度，又考慮了技術(shù)的更新。Google的設(shè)計(jì)能夠很好的升級(jí)處理超大量數(shù)據(jù)集。它能夠高效地使用存儲(chǔ)空間來(lái)存儲(chǔ)索引。優(yōu)化的數(shù)據(jù)結(jié)構(gòu)能夠快速有效地存取(請(qǐng)參見(jiàn)4.2節(jié))。進(jìn)一步，我們希望，相對(duì)于所抓取的文本文件和HTML網(wǎng)頁(yè)的數(shù)量而言，存儲(chǔ)和建立索引的代價(jià)盡可能的小(請(qǐng)參閱附錄B)。對(duì)于象Google這樣的集中式系統(tǒng)，采取這些措施得到了良好的系統(tǒng)可升級(jí)性。1.3設(shè)計(jì)目標(biāo)1.3.1改進(jìn)搜索質(zhì)量。我們的主要目標(biāo)是提高Web搜索引擎的質(zhì)量。1994年，有人認(rèn)為建立全搜索索引就有可能很容易找到任何東西。根據(jù)BestoftheWeb1994--Navigators，“最佳導(dǎo)航服務(wù)應(yīng)更容易找到幾乎任何在網(wǎng)絡(luò)上(已經(jīng)輸入的所有數(shù)據(jù))?！?。然而1997年的Web就迥然不同。任何最近使用搜索引擎的用戶(hù)很容易證實(shí)索索引的完整性并不是唯一影響搜索引擎結(jié)果的因素。用戶(hù)感興趣的搜索結(jié)果往往被“垃圾結(jié)果”淹沒(méi)。實(shí)際上，到1997年11月為止，四大商業(yè)搜索引擎中只有一個(gè)能夠找到它自己(使用自己的搜索自己的名字時(shí)返回的前十個(gè)結(jié)果中有它自己)。導(dǎo)致這一問(wèn)題的主要原因是文檔的索引數(shù)目增加了好幾個(gè)數(shù)量級(jí)，但是用戶(hù)能夠看的文檔數(shù)卻沒(méi)有增加。人們?nèi)匀恢幌Ｍ辞懊娴膸资畟€(gè)搜索結(jié)果。因此，當(dāng)集合增大時(shí)，我們就需要高精確度的工具(在返回的前幾十個(gè)結(jié)果中，相關(guān)文檔的數(shù)量)。由于是從成千上萬(wàn)個(gè)有點(diǎn)相關(guān)的文檔中選出幾十個(gè)，實(shí)際上，我們希望相關(guān)的概念就是指最好的文檔。高精確非常重要，甚至以響應(yīng)(系統(tǒng)能夠返回的有關(guān)文檔的總數(shù))為代價(jià)。令人十分樂(lè)觀的的是利用超文本鏈接提供的信息有助于改進(jìn)搜索和其它應(yīng)用[Marchiori97][Spertus97][Weiss96][Kleinberg98]。尤其是鏈接結(jié)構(gòu)和鏈接文本，為相關(guān)性的判斷和高質(zhì)量篩選提供了大量的信息。Google既利用了鏈接結(jié)構(gòu)又用到了鏈接文本(請(qǐng)參見(jiàn)2.1和2.2節(jié))。1.3.2搜索引擎的學(xué)術(shù)研究除了發(fā)展迅速，Web越來(lái)越商業(yè)化。到1993年，只有1.5%的網(wǎng)絡(luò)服務(wù)是來(lái)自.com域名。到1997年，增長(zhǎng)超過(guò)了60%。同時(shí)，搜索引擎從學(xué)術(shù)領(lǐng)域走進(jìn)商業(yè)。到現(xiàn)在大多數(shù)搜索引擎被公司所有，很少發(fā)布技術(shù)細(xì)節(jié)。這就導(dǎo)致搜索引擎技術(shù)很大程度上仍然是暗箱操作，并傾向做廣告(請(qǐng)參閱附錄A)。對(duì)于Google來(lái)講我們有一個(gè)的主要目標(biāo)是推動(dòng)學(xué)術(shù)領(lǐng)域在此方面的發(fā)展和了解。另一個(gè)設(shè)計(jì)目標(biāo)是給適合數(shù)目的人們一個(gè)實(shí)用的系統(tǒng)。對(duì)我們來(lái)說(shuō)應(yīng)用十分重要，因?yàn)橐恍┭芯勘砻鳎F(xiàn)代網(wǎng)絡(luò)系統(tǒng)中存在大量的有用數(shù)據(jù)。例如，每天有數(shù)千萬(wàn)個(gè)查詢(xún)被執(zhí)行。然而，獲得這些數(shù)據(jù)卻非常困難，主要因?yàn)樗鼈儽徽J(rèn)為有商業(yè)價(jià)值。我們的最終設(shè)計(jì)目標(biāo)是構(gòu)建一個(gè)體系結(jié)構(gòu)，可以支持大型Web數(shù)據(jù)上的一種新的研究活動(dòng)。為了支持新研究，Google以壓縮的形式保存了實(shí)際所抓到所有的文檔。我們?cè)O(shè)計(jì)Google的主要目標(biāo)之一就是要建立一個(gè)環(huán)境使其他研究者能夠很快進(jìn)入這個(gè)領(lǐng)域，處理海量網(wǎng)絡(luò)數(shù)據(jù)，得到滿(mǎn)意的結(jié)果，而通過(guò)其它方法卻很難得到。系統(tǒng)在短時(shí)間內(nèi)被建立起來(lái)，已經(jīng)有幾篇論文用到了Google建立的數(shù)據(jù)庫(kù)，更多的在起步中。我們的另一個(gè)目標(biāo)是建立一個(gè)宇宙空間實(shí)驗(yàn)室似的環(huán)境，在這里研究人員甚至學(xué)生都可以對(duì)我們的海量網(wǎng)絡(luò)數(shù)據(jù)設(shè)計(jì)或做有趣的實(shí)驗(yàn)。2.系統(tǒng)功能Google搜索引擎有兩個(gè)重要功能，幫助它產(chǎn)生高精度的搜索結(jié)果。首先，應(yīng)用Web的鏈接結(jié)構(gòu)計(jì)算每個(gè)網(wǎng)頁(yè)的質(zhì)量等級(jí)值，這個(gè)等級(jí)稱(chēng)為PageRank，將在98頁(yè)詳細(xì)描述它。第二點(diǎn)，Google利用超鏈接改進(jìn)搜索結(jié)果。2.1PageRank：帶來(lái)網(wǎng)頁(yè)排序網(wǎng)絡(luò)的引用(鏈接)圖形是重要的資源，卻沒(méi)有被現(xiàn)有的大多搜索引擎使用。我們建立了一個(gè)包含518百萬(wàn)個(gè)超鏈接的圖，它是一個(gè)具有重要意義的樣本。這些圖能夠快速地計(jì)算網(wǎng)頁(yè)的PageRank值，它是一個(gè)客觀的標(biāo)準(zhǔn)，較好的符合人們主觀的對(duì)一個(gè)網(wǎng)頁(yè)重要程度的評(píng)價(jià)，由此對(duì)應(yīng)的是，PageRank值是一個(gè)較好的區(qū)分通過(guò)網(wǎng)絡(luò)搜索關(guān)鍵字獲得的結(jié)果的方法。建立的基礎(chǔ)是通過(guò)引用判斷重要性。對(duì)于大多數(shù)的主題，一個(gè)簡(jiǎn)單的被限制為網(wǎng)頁(yè)標(biāo)題的文本匹配搜索當(dāng)使用PageRank區(qū)分時(shí)得到了極好的結(jié)果(從可以得到演示)。對(duì)于Google主系統(tǒng)中的全文搜索，PageRank也有很大的幫助。2.1.1PageRank計(jì)算的描述：文獻(xiàn)引用理論應(yīng)用到Web中，主要由引用或反向鏈接到給定頁(yè)來(lái)計(jì)數(shù)。這會(huì)反映了該網(wǎng)頁(yè)的重要性和質(zhì)量的近似值。PageRank擴(kuò)展了這種思想，不平等的計(jì)算所有頁(yè)面上的鏈接并且通過(guò)一個(gè)頁(yè)面上的所有鏈接。PageRank定義如下:我們假設(shè)頁(yè)面T1…Tn指向網(wǎng)頁(yè)A(例如，被引用)。參數(shù)d是一個(gè)設(shè)定在0，1之間的制動(dòng)因子。我們通常設(shè)置d為0.85。在下一節(jié)有更多關(guān)于d的詳情，C(A)定義為網(wǎng)頁(yè)A指向其它網(wǎng)頁(yè)的鏈接數(shù)，網(wǎng)頁(yè)A的PageRank值由下式給出：PR(A)=(1-d)+d(PR(T1)/C(T1)+...+PR(Tn)/C(Tn))請(qǐng)注意PageRank涵蓋所有網(wǎng)頁(yè)的一個(gè)概率分布得來(lái)，因此所有網(wǎng)頁(yè)P(yáng)ageRank和是1。PageRank或PR(A)可使用一個(gè)簡(jiǎn)單的迭代算法來(lái)計(jì)算，相應(yīng)對(duì)應(yīng)月網(wǎng)頁(yè)鏈接矩陣的主特征向量。中等規(guī)模的網(wǎng)站計(jì)算26萬(wàn)網(wǎng)頁(yè)的PageRank值要花費(fèi)幾小時(shí)。還有一些技術(shù)細(xì)節(jié)超出了本文論述的范圍。2.1.2直覺(jué)的解釋PageRank被看作用戶(hù)行為的模型。我們假想一個(gè)“隨機(jī)上網(wǎng)者”；隨機(jī)地給他一個(gè)網(wǎng)頁(yè)；他漫無(wú)目的地命中網(wǎng)頁(yè)的鏈接，而從來(lái)不點(diǎn)“返回鍵”；最終他覺(jué)得煩了，又從另一個(gè)隨機(jī)的網(wǎng)頁(yè)從新開(kāi)始。隨機(jī)訪(fǎng)問(wèn)一個(gè)網(wǎng)頁(yè)的可能性就是它的PageRank值。制動(dòng)因子d是隨機(jī)訪(fǎng)問(wèn)一個(gè)網(wǎng)頁(yè)煩了的可能性，隨機(jī)另選一個(gè)網(wǎng)頁(yè)。對(duì)單個(gè)網(wǎng)頁(yè)或一組網(wǎng)頁(yè)，一個(gè)重要的變量加入到制動(dòng)因子d中。這允許個(gè)人可以故意地誤導(dǎo)系統(tǒng)，以得到較高的PageRank值幾乎變成不可能的。我們還有其它的PageRank算法，見(jiàn)98頁(yè)。另外的直覺(jué)判斷是一個(gè)網(wǎng)頁(yè)有很多網(wǎng)頁(yè)指向它，或者一些PageRank值高的網(wǎng)頁(yè)指向它，則這個(gè)網(wǎng)頁(yè)很重要。直覺(jué)地，在Web中，一個(gè)網(wǎng)頁(yè)被很多網(wǎng)頁(yè)引用，那么這個(gè)網(wǎng)頁(yè)值得一看。一個(gè)網(wǎng)頁(yè)被象Yahoo這樣重要的主頁(yè)引用即使一次，也值得一看。如果一個(gè)網(wǎng)頁(yè)的質(zhì)量不高，或者是死鏈接，象Yahoo這樣的主頁(yè)不會(huì)鏈向它。PageRank處理了這兩方面因素，并通過(guò)網(wǎng)絡(luò)鏈接遞歸地傳遞。2.2鏈接描述文字我們的搜索引擎對(duì)鏈接文本進(jìn)行了特殊的處理。大多數(shù)搜索引擎把鏈接文字和它所鏈向的網(wǎng)頁(yè)聯(lián)系起來(lái)。另外，把它和鏈接所指向的網(wǎng)頁(yè)聯(lián)系起來(lái)。這有幾點(diǎn)好處。第一，通常鏈接描述文字比網(wǎng)頁(yè)本身更精確地描述該網(wǎng)頁(yè)。第二，鏈接描述文字可能鏈向的文檔不能被文本搜索引擎檢索到，例如圖像，程序和數(shù)據(jù)庫(kù)。有可能使返回的網(wǎng)頁(yè)不能被抓到。注意那抓不到的網(wǎng)頁(yè)將會(huì)帶來(lái)一些問(wèn)題。在返回給用戶(hù)前檢測(cè)不了它們的有效性。這種情況搜索引擎可能返回一個(gè)根本不存在的網(wǎng)頁(yè)，但是有超級(jí)鏈接指向它。然而這種結(jié)果可以被挑出來(lái)的，所以此類(lèi)的問(wèn)題很少發(fā)生。鏈接描述文字是對(duì)被引用網(wǎng)頁(yè)的描述這個(gè)思想被用在WorldWideWebWorm中，主要因?yàn)樗兄谒阉鞣俏谋拘畔ⅲ軌蛴蒙倭康囊严螺d文檔擴(kuò)大搜索范圍。我們大量應(yīng)用鏈接描述文字，因?yàn)樗兄谔岣咚阉鹘Y(jié)果的質(zhì)量。有效地利用鏈接描述文字技術(shù)上存在一些困難，因?yàn)楸仨毺幚泶罅康臄?shù)據(jù)?，F(xiàn)在我們能抓到24萬(wàn)個(gè)網(wǎng)頁(yè)，已經(jīng)檢索到259萬(wàn)多個(gè)鏈接描述文字。2.3其它功能除了PageRank和應(yīng)用鏈接描述文字外，Google還有其他幾個(gè)功能。一，它有所有命中數(shù)的位置信息，所以它可以在搜索中廣泛應(yīng)用鄰近性。第二，Google跟蹤一些可視化外表細(xì)節(jié)，例如字的字體大小。更大的字的權(quán)重要高于其他的。第三，知識(shí)庫(kù)存儲(chǔ)了原始的全文html網(wǎng)頁(yè)。3相關(guān)的工作網(wǎng)絡(luò)檢索研究的歷史簡(jiǎn)短。WorldWideWebWorm(WWWW)是最早的搜索引擎之一。后來(lái)出現(xiàn)了一些用于學(xué)術(shù)性的搜索引擎，現(xiàn)在它們中的大多數(shù)被上市公司擁有。與Web的增長(zhǎng)和搜索引擎的重要性相比，有關(guān)當(dāng)今搜索引擎技術(shù)的優(yōu)秀論文相當(dāng)少。根據(jù)MichaelMauldin(LycosInc的首席科學(xué)家))，“各種各樣的服務(wù)(包括Lycos)非常關(guān)注這些數(shù)據(jù)庫(kù)的信息?！彪m然在搜索引擎的某些特點(diǎn)上做了大量工作。具有代表性的工作有，對(duì)現(xiàn)有商業(yè)搜索引擎的結(jié)果進(jìn)行傳遞，或建立小型的個(gè)性化的搜索引擎。最后有關(guān)信息檢索系統(tǒng)的研究很多，尤其在有組織機(jī)構(gòu)集合方面。在下面兩節(jié)，我們將討論在信息檢索系統(tǒng)中的哪些領(lǐng)域需要改進(jìn)以便更好的工作在Web上。3.1信息檢索信息檢索系統(tǒng)誕生在幾年前，并發(fā)展很好。然而，大多數(shù)信息檢索系統(tǒng)的研究針對(duì)的是受控制的同質(zhì)集合，例如，主題相關(guān)的科學(xué)論文或新聞故事。實(shí)際上，信息檢索的主要基準(zhǔn)，用小規(guī)模的、有組織結(jié)構(gòu)的集合作為它們的基準(zhǔn)。大型文集基準(zhǔn)只有20GB，相比之下，我們抓到的24萬(wàn)個(gè)網(wǎng)頁(yè)占147GB。在TREC上工作良好的系統(tǒng)，在Web上卻不一定產(chǎn)生好的結(jié)果。例如，標(biāo)準(zhǔn)向量空間模型企圖返回和查詢(xún)請(qǐng)求最相近的文檔，把查詢(xún)請(qǐng)求和文檔都看作由出現(xiàn)在它們中的詞匯組成的向量。在Web環(huán)境下，這種策略常常返回非常短的文檔，這