| Google搜索引擎技術(shù)實(shí)現探究 |
| Google搜索引擎技術(shù)實(shí)現探究 化柏林 (中國科學(xué)技術(shù)信息研究所 北京 100038) 【摘要】 本文從技術(shù)的角度剖析了Google搜索引擎的體系結構與工作過(guò)程，詳細介紹了基于Robot的網(wǎng)頁(yè)搜索、標引入庫和檢索引擎三大模塊，統計了Google的技術(shù)數據，并分析了Google的技術(shù)實(shí)現特點(diǎn)，解釋了Google檢索的種種現象。 【關(guān)鍵詞】 Google 搜索引擎 技術(shù)實(shí)現 【分類(lèi)號】 G354 Anatomy of Google Search Engine Viewed on Technical Implementation Hua Bolin (Institute of Scientific and Technical Information of China, Beijing 100038) 【Abstract】 This paper anatomized architecture and procedure of Google viewed on Technical Implementation. It introduced three functional modules, which is Web crawler, index and create database, search engine. Then do a statistic of technical data about Google, and analyzed technical feature, explained a variety of phenomena when using Google to retrieval. 【Keywords】 Google, Search Engines, Technical Implementation 1 Google技術(shù)總況與體系結構 Google擁有10億個(gè)網(wǎng)址，30億個(gè)網(wǎng)頁(yè)，3.9 億張圖像，Google 支持66種語(yǔ)言接口，16種文件格式，面對如此海量的數據和如此異構的信息，google是如何實(shí)現半秒內搜索的呢？ Google擁有1600臺服務(wù)器，大部分代碼用C或C++實(shí)現，有很好的執行效率，運行在Solaris 或Linux 上。Google用了64個(gè)桶(barrels)，有293M詞典（lexicon）、43G的順排檔文件、41G的倒排檔文件,構造了一個(gè)5.18億個(gè)超鏈接的網(wǎng)絡(luò )關(guān)聯(lián)圖。 Google搜索引擎有兩個(gè)特征來(lái)提高查準率：利用網(wǎng)頁(yè)間的鏈接關(guān)系來(lái)計算每一個(gè)網(wǎng)頁(yè)的等級；利用鏈接關(guān)系來(lái)改善檢索結果。除此之外，Google還對所有的點(diǎn)擊都有定位信息，廣泛利用搜索的親近度。第二，Google 記錄詳細的可視化表達諸如詞的字體大小，大或粗體的詞的權重就高。第三，整個(gè)頁(yè)面的HTML源文件在知識庫中是可用的。 Google搜索引擎從功能上同樣分為三大部分：網(wǎng)頁(yè)爬行、標引入庫和用戶(hù)查詢(xún)。網(wǎng)頁(yè)爬行主要負責網(wǎng)頁(yè)的抓取，由URL服務(wù)器、爬行器、存儲器、分析器和URL解析器組成, 爬行器是該部分的核心；標引入庫主要負責對網(wǎng)頁(yè)內容進(jìn)行分析，對文檔進(jìn)行標引并存儲到數據庫里，由標引器和分類(lèi)器組成，該模塊涉及許多文件和數據，有關(guān)于桶的操作是該部分的核心；用戶(hù)查詢(xún)主要負責分析用戶(hù)輸入的檢索表達式，匹配相關(guān)文檔，把檢索結果返回給用戶(hù)，由查詢(xún)器和網(wǎng)頁(yè)級別評定器組成，其中網(wǎng)頁(yè)等級的計算是該部分的核心。其總體系統結構如圖1所示。  2 基于Robot的搜索過(guò)程 Robot使用多線(xiàn)程并發(fā)搜索技術(shù)，主要完成文檔訪(fǎng)問(wèn)代理、路徑選擇引擎和訪(fǎng)問(wèn)控制引擎?；赗obot的Web頁(yè)搜索模塊主要由URL服務(wù)器、爬行器、存儲器、URL解析器四大功能部件和資源庫、錨庫、鏈接庫三大數據資源構成，另外還要借助標引器的一個(gè)輔助功能。具體過(guò)程是,有個(gè)URL服務(wù)器發(fā)送要去抓取的URL，爬行器根據URL抓取WEB頁(yè)并送給存儲器，存儲器壓縮Web頁(yè)并存入數據資源庫，然后由標引器分析每個(gè)WEB頁(yè)的所有鏈接并把相關(guān)的重要信息存儲在anchors 文件中。URL解析器讀anchors文件并解析URL，然后依次轉成docID。再把anchor文本變成順排索引，送入索引庫。具體過(guò)程如圖2所示。  2．1 URL服務(wù)器(URL Server) URL服務(wù)器是整個(gè)Web頁(yè)搜索模塊的開(kāi)始，主要用來(lái)管理和維護URL列表。首先由它發(fā)送一個(gè)新的URL給爬行器，讓爬行器去搜索。如果爬行器遇到了不可下載的網(wǎng)頁(yè)，就會(huì )給URL一個(gè)返回信息，然后取下一個(gè)URL。URL服務(wù)器會(huì )從文檔索引庫里不斷地取新的URL以供爬行器使用。 2．2 爬行器(crawler) 爬行器是整個(gè)搜索模塊中最關(guān)鍵的一部分，它由好幾個(gè)分布的爬行器組成，并協(xié)同工作。爬行器遇到HTML頁(yè)的頭有如下標記就不再抓取此頁(yè)，<head><meta name="robots" content="noindex, nofollow"></head>，返回一個(gè)空值，繼續向其他方向爬行，這就有效防止爬行器標引此頁(yè)及本頁(yè)的相關(guān)鏈接頁(yè)。如果網(wǎng)頁(yè)已經(jīng)標引過(guò)，就從將要爬行的網(wǎng)頁(yè)隊列中移除。Web頁(yè)文本的繁殖思想是由3W蠕蟲(chóng)來(lái)實(shí)現的，當它搜索非文本信息時(shí)，盡可能少的下載文檔，以擴展搜索度，因為非文本信息如圖片等沒(méi)有鏈接會(huì )造成爬行的中斷。這樣，Google就可以通過(guò)各種策略來(lái)解決排序沉沒(méi)（rank sink）和排序漏出(rank loak)等問(wèn)題。 2．3 存儲器(store server) 存儲器把爬行器抓來(lái)的Web頁(yè)進(jìn)行壓縮并存儲到數據資源庫中。數據資源庫包含每一個(gè)Web頁(yè)的全部HTML，所有的網(wǎng)頁(yè)用zlib進(jìn)行壓縮，Google更注重zlib的壓縮速度而不是壓縮率。bzip對數據庫的壓縮率接近4:1，而zlib為3:1。這樣，Google就能把147.8G的HTML文檔壓縮成53.5G的數據存儲在庫中。在數據資源庫中，對文檔進(jìn)行歸類(lèi)，加上docID前綴、文檔的長(cháng)度和URL。文檔索引記錄著(zhù)每一個(gè)文檔的信息，它是一個(gè)有固定長(cháng)度，經(jīng)docID排序的ISAM索引（Index sequential access mode）。存在每個(gè)條目中的信息包括當前文檔狀態(tài)，數據庫中的指針，文檔校驗和以及其它統計信息。如果文檔被爬行過(guò)，它也包含到可變長(cháng)文件的指針，這個(gè)稱(chēng)為docinfo的文件包含文檔的URL和標題。否則，指針指向僅包含URL的URL列表。 2．4 分析器(parser) 分析器可以看成是標引器的一部分，也可以說(shuō)是標引器的一個(gè)輔助功能部分。它分析每個(gè)WEB頁(yè)的所有鏈接并把相關(guān)的重要信息存儲在anchors 文件中，構成一個(gè)錨庫。每當從WEB頁(yè)分析出一個(gè)新的URL時(shí)，為每個(gè)WEB頁(yè)分配一個(gè)稱(chēng)為docID的關(guān)聯(lián)ID。這個(gè)文件包含足夠的信息來(lái)決定每個(gè)鏈接的何去何從。錨經(jīng)常提供比web頁(yè)本身更精確的頁(yè)描述。錨可以存在文檔，這些文檔不能被基于文本的搜索引擎所標引，如圖片、程序、數據庫。這就為返回那些不能精確爬行的Web頁(yè)提供了可能。 2．5 URL解析器(URL Resolver) URL解析器讀anchors文件并把相對URL轉成絕對URL，然后依次轉成docID。把anchor文本變成順排索引，存到文檔索引庫里，并用anchor所指向的docID進(jìn)行關(guān)聯(lián)。把URL轉換成docID的文件,是由URL校驗和及相應的docID兩列組成的一個(gè)列表，并以校驗和排序。為了找到一個(gè)特定URL的docID，首先計算URL的校驗和，在校驗和文件中進(jìn)行二元查找,以找到相應的docID。執行一次批處理，通過(guò)合并文件把URL 轉成docID。使用這種批處理模式很關(guān)鍵，要不然就得為每一個(gè)鏈接都作一次查找，假設一個(gè)磁盤(pán)上有322,000,000個(gè)鏈接記錄，那么這樣一個(gè)過(guò)程需要2個(gè)多月的時(shí)間。它還產(chǎn)生成對docID的鏈接數據庫，以用于計算所有文檔的PageRanks。 3 標引入庫 標引入庫模塊由分類(lèi)器和標引器組成。標引入庫模塊處理大量的文件和數據，用來(lái)構建龐大的數據庫，主要涉及數據資源庫、詞典庫、鏈接庫、桶等。桶的結構與內容非常復雜，有關(guān)桶的操作是本模塊的核心， 3.1 分類(lèi)器(sorter) 分類(lèi)器從桶中取出數據，按docID進(jìn)行一級分類(lèi)，然后按照wordID進(jìn)行二級分類(lèi)并產(chǎn)生倒排檔索引。分類(lèi)器產(chǎn)生wordID的列表并把其偏移量寫(xiě)到倒排檔索引中。一個(gè)稱(chēng)為DumpLexicon的程序把這個(gè)列表和由標引器產(chǎn)生的詞典揉和在一起并為檢索器產(chǎn)生一個(gè)新的詞典。 3．2 標引器(indexer) 標引器有許多函數，它讀數據庫，解壓縮文檔然后進(jìn)行分析。每個(gè)文檔都被轉成一套單詞出現頻率，稱(chēng)之為采樣數。采樣數記錄單詞及在文檔中出現的位置，字體的大小以及大寫(xiě)信息。標引器把這些采樣數分配到一套“桶”中，創(chuàng )建一個(gè)部分分類(lèi)的順排索引。對于中文，Google主要采用了二元切分法，也就是為什么我們輸入長(cháng)于兩個(gè)漢字的中文，如果不加雙引號，Google會(huì )自動(dòng)給以切分的原因。 3．3 桶(barrels) Google共有64個(gè)桶（barrels），每個(gè)桶都存著(zhù)wordID的歸類(lèi)，包括順排檔與倒排檔。如果一個(gè)文檔包含落在某個(gè)桶里的詞，docID和wordID的列表以及相應的命中列表就被記錄到桶里。Google存儲每一個(gè)wordID時(shí)，存儲的是與所在桶的最小wordID的相對差異，而不是存儲實(shí)際的wordID。這樣，在未排序的桶中用24位存儲wordID，留下8位用來(lái)存儲命中列表的長(cháng)度。 倒排檔索引就象順排檔一樣由系列的桶組成，唯一的不同是被分類(lèi)器處理過(guò)。有個(gè)重要的問(wèn)題是docID應當在doclist中如何排序。一個(gè)簡(jiǎn)單的解決辦法是用docID進(jìn)行分類(lèi)，這允許多詞查詢(xún)而帶來(lái)的不同doclist的合并。另外一個(gè)辦法是按詞在每個(gè)文檔中出現的頻率等級進(jìn)行分類(lèi)存儲，盡管這使得處理單個(gè)詞的查詢(xún)變得繁瑣，但為多詞查詢(xún)提供了可能。Google在這兩個(gè)方案中選擇了折衷，使用兩套倒排的桶，一套為包括標題和anchor hits的命中列表，我們稱(chēng)之為短桶，另一套為所有的命中列表，我們稱(chēng)之為長(cháng)桶。 在順排檔索引和倒排檔索引中，命中列表占據了大量的空間。命中列表是指詞在一篇文檔中的出現頻率，包括位置、字體和大寫(xiě)信息。Google為編碼位置、字體和大寫(xiě)考慮了多種編碼方案——簡(jiǎn)單編碼、優(yōu)化壓縮編碼和哈夫曼編碼。由于優(yōu)化壓縮編碼對空間的要求比簡(jiǎn)單編碼低，操作過(guò)程比哈夫曼編碼簡(jiǎn)單，因此，Google最終選擇了優(yōu)化壓縮編碼。 Google用兩個(gè)字節的壓縮編碼來(lái)記錄每次命中，命中類(lèi)型有兩種：特殊命中與普通命中。特殊命中包括URL的命中率、標題、鏈接文本和關(guān)鍵標記。普通命中含有所有的信息，包括大寫(xiě)位、字體大小和12位標記詞在文檔中出現的位置信息等。字體大小用3位來(lái)表達文檔的其它內容的相對值（僅有7個(gè)值可用，因為111是特殊命中的標記）。特殊標記由大寫(xiě)位，字體設成7來(lái)表明是一個(gè)特殊命中，有4位表示類(lèi)型，用8位標記位置。為了節省空間，命中列表的長(cháng)度由順排檔中的wordID和倒排檔中的docID決定。分別需要8位與5位。如果長(cháng)度更長(cháng)的話(huà)，在相應的位里就存著(zhù)一個(gè)溢出編碼，接下來(lái)的兩個(gè)字節存儲命中列表的實(shí)際長(cháng)度。  3．4 詞典(lexicon) 詞典有幾種不同的形式。對早期系統的一個(gè)重要改變是根據合理的代價(jià)分配內存。該詞典包含1400萬(wàn)個(gè)詞條（有些生僻詞沒(méi)加），由兩部分實(shí)現，詞表和指針的哈希表。詞表還有一些輔助信息用以實(shí)現其它功能。對于每個(gè)有效的wordID，詞典包含指向wordID所在桶的指針。它指向docID和相應的命中列表的doclist。Doclist表明該詞在所有文檔中出現的所有情況。 4 檢索過(guò)程與網(wǎng)頁(yè)級別 Google用戶(hù)查詢(xún)模塊主要由網(wǎng)頁(yè)級別評定器和查詢(xún)器組成。 4．1 查詢(xún)器(searcher) 查詢(xún)器運行在Web服務(wù)器上，并用DumpLexicon產(chǎn)生的詞典、倒排檔索引和PageRanks一起來(lái)響應查詢(xún)。首先接受用戶(hù)輸入的檢索表達式，進(jìn)行分析得出各項檢索要求，提取檢索詞并轉成wordID,接著(zhù)到短桶文檔列表里進(jìn)行查詞，遍歷文檔列表直到匹配所有的詞條，找到一篇就計算網(wǎng)頁(yè)等級，短桶查完了，如果沒(méi)有足夠的匹配記錄，就去查長(cháng)桶。查完了所有的文檔列表，就對檢索結果進(jìn)行排序并返回前K項。  4.2 網(wǎng)頁(yè)級別評定器(PageRanker) 網(wǎng)頁(yè)級別評定器借用了圖書(shū)文獻里的參考文獻與引用文獻的評價(jià)思想，利用鏈接網(wǎng)頁(yè)的數量及重要性進(jìn)行等級評定，而鏈接網(wǎng)頁(yè)的重要性由它的鏈接網(wǎng)頁(yè)的數量及重要性決定，因此是一種迭代計算。評級函數有許多參數，如類(lèi)型權重和相關(guān)類(lèi)型權重等。 如果有許多網(wǎng)頁(yè)指向網(wǎng)頁(yè)P，那么P就是一個(gè)好的網(wǎng)頁(yè)。IR‘(P)，從不同域的鏈接要比同一個(gè)域內的鏈接重要。自然鏈接可以表明相關(guān)重要性。當從網(wǎng)頁(yè) A 鏈接到網(wǎng)頁(yè) B 時(shí)，Google 就認為“網(wǎng)頁(yè) A 投了網(wǎng)頁(yè) B 一票”。Google 根據網(wǎng)頁(yè)的得票數評定其重要性。除了考慮網(wǎng)頁(yè)得票數（即鏈接）的純數量之外，Google 還要分析投票的網(wǎng)頁(yè)。“重要”的網(wǎng)頁(yè)所投出的票就會(huì )有更高的權重，也有助于提高其它網(wǎng)頁(yè)的“重要性”。 被引率高就說(shuō)明該頁(yè)值得看，PageRank通過(guò)web鏈接架構來(lái)處理靠遞歸繁殖提高權重的情況。 假定網(wǎng)頁(yè)A有指向A的網(wǎng)頁(yè)T1...Tn（也叫引用網(wǎng)頁(yè)）。參數d是一個(gè)設定于0、1之間的遞減因子，通常定為0.85。C(A)為從網(wǎng)頁(yè)A鏈出去的鏈接數，因此，網(wǎng)頁(yè)A的PageRank就可以求出： PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) PageRank 或者PR(A)用迭代算法來(lái)計算，相當于一個(gè)規范化的Web鏈接矩陣的特征向量。有26,000,000個(gè)網(wǎng)頁(yè)在一臺中型工作站上用幾個(gè)小時(shí)就能算完。PageRanks形成了web頁(yè)的概率分布，所有web頁(yè)的PageRanks和為1。  重要的、高質(zhì)量的網(wǎng)頁(yè)會(huì )獲得較高的網(wǎng)頁(yè)級別。Google 在排列其搜索結果時(shí)，總會(huì )考慮每個(gè)網(wǎng)頁(yè)的級別。當然，如果不能滿(mǎn)足用戶(hù)的查詢(xún)要求，網(wǎng)頁(yè)級別再高對用戶(hù)來(lái)說(shuō)也毫無(wú)意義。因此，Google 將網(wǎng)頁(yè)級別與完善的文本匹配技術(shù)結合在一起，為用戶(hù)找到最重要、最有用的網(wǎng)頁(yè)。Google 所關(guān)注的遠不只是關(guān)鍵詞在網(wǎng)頁(yè)上出現的次數，它還對該網(wǎng)頁(yè)的內容以及該網(wǎng)頁(yè)所鏈接的內容進(jìn)行全面檢查，從而確定該網(wǎng)頁(yè)是否滿(mǎn)足用戶(hù)的查詢(xún)要求。Google在檢索引擎里用一個(gè)用戶(hù)反饋機，對信任用戶(hù)可有選擇地評估所有的返回結果，這種反饋被存到數據庫里，當修改評級函數時(shí)，就能發(fā)現對以前評過(guò)級的檢索所產(chǎn)生的影響。 5 功能檢索的實(shí)現 對于Google的檢索實(shí)現，筆者對檢索做了大量的測試，而對技術(shù)僅作了有限的部分測試，其理解如下： 5.1 邏輯表達式 Google支持的邏輯運算有與、或、非，其形式分別為“ ”、“or”、“-”，對應Google高級檢索里的“包含全部字詞”、“包含任何一個(gè)字詞” 、“不包含以下字詞”。Google不支持截詞檢索，因為截詞檢索會(huì )極大地降低計算機的檢索速度。當然Google對詞的切分技術(shù)也并不理想，對西文比較有效，對亞洲語(yǔ)言作得不好。 5．2 指定文件類(lèi)型 Google可以指定查找的文件格式，如pdf、doc、ppt等格式文件。如果某個(gè)搜索結果是 PDF 文件而不是網(wǎng)頁(yè)，它的標題前面會(huì )出現以藍色字體標明的 [PDF]。用戶(hù)只想查一般網(wǎng)頁(yè)，而不要 PDF 文件，只需在搜索關(guān)鍵詞后加上 -filetype:pdf 就可以了，而如果只想查pdf文件，則用filetype:pdf就可以指定pdf文件了。每一個(gè)文檔在數據庫里都有其文件類(lèi)型，因此，實(shí)現它并不困難。 5．3 指定范圍 Google可以指定網(wǎng)頁(yè)的范圍，如(all)intitle,(all)intext ，(all)inurl，(all)inanchor等。網(wǎng)頁(yè)標題只是對HTML的<title></title>里的內容進(jìn)行檢索，如果title的內容與文章真正的標題不一致，則Google沒(méi)有能力檢索出來(lái)。在  5．4 語(yǔ)言問(wèn)題 Google支持66種語(yǔ)言接口，35種語(yǔ)言指定檢索，Google對語(yǔ)種的判別不是通過(guò)URL信息（域名中的國別），主要通過(guò)HTML中的charset，和對網(wǎng)頁(yè)內容部分識別的統計信息來(lái)聯(lián)合判斷。其實(shí),好多人還把Google當詞典來(lái)用，我們輸入“"層次分析法" analysis”指定中文網(wǎng)頁(yè)就可以檢索出層次分析法的英文翻譯。 5．5 同義詞檢索 選擇“搜索所有網(wǎng)站或搜索所有中文網(wǎng)頁(yè)”，輸入“計算機”，則會(huì )把含有“電腦”的網(wǎng)頁(yè)（不論有沒(méi)有“計算機”）搜索出來(lái)，而在簡(jiǎn)體中文網(wǎng)頁(yè)里就不會(huì )實(shí)現這樣的功能，因為Google采用Basis Technology的中文簡(jiǎn)繁體轉換技術(shù)。 5．6網(wǎng)頁(yè)目錄 Google按內容把網(wǎng)頁(yè)信息分為15個(gè)大類(lèi)，主要是通過(guò)詞頻分布與統計技術(shù)，對內容進(jìn)行識別并用分類(lèi)器（sorter）進(jìn)行歸類(lèi)。 5．7 圖像搜索 Google搜集了3.9 億張圖像，對圖像的描述信息建了一個(gè)很大的數據庫。圖像檢索使用的主要是文件名、圖片附近的文本、圖片的標題以及從圖片中提取的部分內容。 5．8 相似結果 google 會(huì )省略相似的結果，尤其是來(lái)自不同站點(diǎn)頁(yè)內容相同的文章，有時(shí)我們在Google顯示的結果中不能下載相應的文章時(shí)，而省略的結果中可能允許下載，這時(shí)google的省略功能就帶來(lái)了不便。判斷內容相似主要可能是根據文章題目、文章大小和部分詞語(yǔ)統計信息等。當然還有許多特點(diǎn)與使用技巧,那不是本文討論的重點(diǎn)。 當我們了解了Google的技術(shù)實(shí)現，就可以理解檢索過(guò)程中出現的種種現象。針對這些特點(diǎn)再去調整檢索策略，這樣它返回的結果就不再成千上萬(wàn)了。正常情況下，把檢索結果控制在百條左右，是一個(gè)專(zhuān)業(yè)檢索水平的標志，這樣的結果對我們也才真正的有意義。 參考文獻 [1] [2] [3] Junghoo Cho, Hector Garcia-Molina and Lawrence Page. Efficient crawling through URL ordering [4] Sergey Brin and Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. [5] The Google Pagerank Algorithm and How It works. pagerank/ |
聯(lián)系客服
