搜索引擎的工作機制[圖]
圖1 搜索引擎的工作流程搜索引擎通過客戶端程序接收來自用戶的檢索請求，現在最常見的客戶端程序就是瀏覽器，實際上它也可以是一個用戶開發的簡單得多的網路應用程序。用戶輸入的檢索請求一般是關鍵詞或者是用邏輯符號連接的多個關鍵詞，搜索伺服器根據系統關鍵詞字典，把搜索關鍵詞轉化為wordID，然後在標引庫（倒排文件）中得到docID列表，對docID列表中的對象進行掃描並與wordID進行匹配，提取滿足條件的網頁，然後計算網頁和關鍵詞的相關度，並根據相關度的數值將前K篇結果(不同的搜索引擎每頁的搜索結果數不同)返回給用戶，其處理流程如圖1所示。圖2描述了一般搜索引擎的系統架構，其中包括頁面搜集器、索引器、檢索器、索引文件等部分，下面對其中的主要部分的功能實現進行了介紹。
圖2 搜索引擎各個組成部分的關係搜集器搜集器的功能是在互聯網中漫遊，發現並搜集信息，它搜集的信息類型多種多樣，包括HTML頁面、XML文檔、Newsgroup文章、FTP文件、字處理文檔、多媒體信息等。搜索器是一個計算機程序，其實現常常採用分散式和並行處理技術，以提高信息發現和更新的效率。商業搜索引擎的搜集器每天可以搜集幾百萬甚至更多的網頁。搜索器一般要不停地運行，要儘可能多、儘可能快地搜集互聯網上的各種類型的新信息。因為互聯網上的信息更新很快，所以還要定期更新已經搜集過的舊信息，以避免死鏈接和無效鏈接。另外，因為Web信息是動態變化的，因此搜集器、分析器和索引器要定期更新資料庫，更新周期通常約為幾周甚至幾個月。索引資料庫越大，更新也越困難。互聯網上的信息太多，即使功能強大的搜集器也不可能搜集互聯網上的全部信息。因此，搜集器採用一定的搜索策略對互聯網進行遍歷並下載文檔，例如，一般採用以寬度優先搜索策略為主、線性搜索策略為輔的搜索策略。在搜集器實現時，系統中維護一個超鏈隊列，或者堆棧，其中包含一些起始URL，搜集器從這些URL出發，下載相應的頁面，並從中抽取出新的超鏈加入到隊列或者堆棧中，上述過程不斷重複隊列直到堆棧為空。為提高效率，搜索引擎將Web空間按照域名、IP地址或國家域名進行劃分，使用多個搜集器並行工作，讓每個搜索器負責一個子空間的搜索。為了便於將來擴展服務，搜集器應能改變搜索範圍。1.線性搜集策略線形搜索策略的基本思想是從一個起始的IP地址出發，按IP地址遞增的方式搜索後續的每一個IP地址中的信息，完全不考慮各站點的HTML文件中指向其他Web站點的超鏈地址。此策略不適用於大規模的搜索（主要原因在於IP可能是動態的），但可以用於小範圍的全面搜索，利用此種策略的搜集器可以發現被引用較少或者還沒有被其他HTML文件引用的新HTML文件信息源。2. 深度優先搜集策略深度優先搜集策略是早期開發搜集器使用較多的一種方法，它的目的是要達到被搜索結構的葉結點。深度優先搜索順著HTML文件上的超鏈走到不能再深入為止，然後返回到上一個接點的HTML文件，再繼續選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時，說明搜索已經結束。深度優先搜索適宜遍歷一個指定的站點或者深層嵌套的HTML文件集，但對於大規模的搜索，由於Web結構相當深，也許永遠也出不來了。3. 寬度優先搜集策略寬度優先搜集策略是先搜索同一層中的內容，然後再繼續搜索下一層。假如一個HTML文件中有三個超鏈，選擇其中之一併處理相應的HTML文件，然後返回並選擇剛才第一個網頁的第二個超鏈，處理相應的HTML文件，再返回。一旦同一層上的所有超鏈都已被處理過，就可以開始在剛才處理過的HTML文件中搜索其餘的超鏈。這樣保證了對淺層的首先處理，當遇到一個無窮盡的深層分支時，也就不會再陷進去。寬度優先搜集策略容易實現並被廣泛採用，但是需要花費比較長的時間才能到達深層的HTML文件。4. 收錄搜集策略有些網頁可以通過用戶提交的方式進行搜集，例如某些商業網站向搜索引擎發出收錄申請，搜集器就可以定向搜集提交申請網站的網頁信息並加入到搜索引擎的索引資料庫中。分析器對搜集器搜集來的網頁信息或者下載的文檔一般要首先進行分析，以用於建立索引，文檔分析技術一般包括: 分詞（有些僅從文檔某些部分抽詞，如Altavista）、過濾（使用停用詞表stoplist）、轉換（有些對詞條進行單複數轉換、詞綴去除、同義詞轉換等工作），這些技術往往與具體的語言以及系統的索引模型密切相關。索引器索引器的功能是對搜索器所搜索的信息進行分析處理，從中抽取出索引項，用於表示文檔以及生成文檔庫的索引表。索引項有元數據索引項和內容索引項兩種: 元數據索引項與文檔的語意內容無關，如作者名、URL、更新時間、編碼、長度、鏈接流行度等等; 內容索引項是用來反映文檔內容的，如關鍵詞及其權重、短語、單字等等。內容索引項可以分為單索引項和多索引項（或稱短語索引項）兩種。單索引項對於英文來講是英語單詞，比較容易提取，因為單詞之間有天然的分隔符（空格）; 對於中文等連續書寫的語言，必須進行詞語的切分。在搜索引擎中，一般要給單索引項賦予一個權值，以表示該索引項對文檔的區分度，同時用來計算查詢結果的相關度。使用的方法一般有統計法、資訊理論法和概率法。短語索引項的提取方法有統計法、概率法和語言學法。為了快速查找到特定的信息，建立索引資料庫是一個常用的方法，即將文檔表示為一種便於檢索的方式並存儲在索引資料庫中。索引資料庫的格式是一種依賴於索引機制和演算法的特殊數據存儲格式。索引的質量是Web信息檢索系統成功的關鍵因素之一。一個好的索引模型應該易於實現和維護、檢索速度快、空間需求低。搜索引擎普遍借鑒了傳統信息檢索中的索引模型，包括倒排文檔、矢量空間模型、概率模型等。例如在矢量空間索引模型中，每個文檔d都表示為一個范化矢量V(d)=(t1,w1 (d)…ti,w1(d)…tn,wn(d))。其中ti為詞條項，wi(d)為ti在d中的權值，一般被定義為ti在d中出現頻率tfi(d)的函數。索引器的輸出是索引表，它一般使用倒排形式（Inversion List），即由索引項查找相應的文檔。索引表也可能記錄索引項在文檔中出現的位置，以便檢索器計算索引項之間的相鄰或接近關係（proximity）。索引器可以使用集中式索引演算法或分散式索引演算法。當數據量很大時，必須實現實時索引（Instant Indexing），否則就無法跟上信息量急劇增加的速度。索引演算法對索引器的性能（如大規模峰值查詢時的響應速度）有很大的影響。一個搜索引擎的有效性在很大程度上取決於索引的質量。檢索器檢索器的功能是根據用戶的查詢在索引庫中快速檢出文檔，進行文檔與查詢的相關度評價，對將要輸出的結果進行排序，並實現某種用戶相關性反饋機制。檢索器常用的信息檢索模型有集合理論模型、代數模型、概率模型和混合模型等多種，可以查詢到文本信息中的任意字詞，無論出現在標題還是正文中。檢索器從索引中找出與用戶查詢請求相關的文檔，採用與分析索引文檔相識的方法來處理用戶查詢請求。如在矢量空間索引模型中，用戶查詢q首先被表示為一個范化矢量V(q)=(t1,w1(q); …; ti,wi(q); …; tn,wn(q))，然後按照某種方法來計算用戶查詢與索引資料庫中每個文檔之間的相關度，而相關度可以表示為查詢矢量V(q)與文檔矢量V(d)之間的夾角餘弦，最後將相關度大於閥值的所有文檔按照相關度遞減的順序排列並返還給用戶。當然搜索引擎的相關度判斷並不一定與用戶的需求完全吻合。用戶介面用戶介面的作用是為用戶提供可視化的查詢輸入和結果輸出界面，方便用戶輸入查詢條件、顯示查詢結果、提供用戶相關性反饋機制等，其主要目的是方便用戶使用搜索引擎，高效率、多方式地從搜索引擎中得到有效的信息。用戶介面的設計和實現必須基於人機交互的理論和方法，以適應人類的思維和使用習慣。在查詢界面中，用戶按照搜索引擎的查詢語法制定待檢索詞條及各種簡單或高級檢索條件。簡單介面只提供用戶輸入查詢串的文本框，複雜介面可以讓用戶對查詢條件進行限制，如邏輯運算（與、或、非）、相近關係（相鄰、NEAR）、域名範圍（如edu、com）、出現位置（如標題、內容）、時間信息、長度信息等等。目前一些公司和機構正在考慮制定查詢選項的標準。在查詢輸出界面中，搜索引擎將檢索結果展現為一個線性的文檔列表，其中包含了文檔的標題、摘要、快照和超鏈等信息。由於檢索結果中相關文檔和不相關文檔相互混雜，用戶需要逐個瀏覽以找出所需文檔。搜索引擎的中文分詞技術中文自動分詞是網頁分析的基礎。在網頁分析的過程中，中文與英文的處理方式是不同的，這是因為中文信息與英文信息有一個明顯的差別: 英文單詞之間有空格，而中文文本中詞與詞之間沒有分割符。這就要求在對中文網頁進行分析之前，先要將網頁中的句子切割成一個個的詞的序列，這就是中文分詞。中文自動分詞涉及到許多自然語言處理技術和評價標準，在搜索引擎中，我們主要關心中文自動分詞的速度和準確度。分詞準確性對搜索引擎來說十分重要，但如果分詞速度太慢，即使準確性再高，對於搜索引擎來說也是不可用的，因為搜索引擎需要處理數以億計的網頁，如果分詞耗用的時間過長，會嚴重影響搜索引擎內容更新的速度。因此，搜索引擎對分詞的準確性和速度都提出了很高的要求。目前，中文自動分詞比較成熟的技術是基於分詞詞典的機械分詞方法。這種方法是按照一定的策略將要分析的漢字串與詞典中的詞條進行匹配。根據匹配策略的不同，機械分詞方法又有如下幾種演算法: 正向最大匹配演算法、逆向最大匹配演算法、最少分詞演算法等。這種方法的優點是分詞的速度快，準確度有一定的保證，但對未登錄詞的處理效果較差。實驗結果表明: 正向最大匹配的錯誤率為1/169左右，逆向最大匹配的錯誤率為1/245左右。另一種比較常用的中文自動分詞方法是基於統計的分詞方法，這種方法是對語料中的字組頻度進行統計，不需要切分詞典，因此也稱為無詞典分詞方法。但該方法經常把不是詞的常用字組當成詞，對常用詞的識別精度較差，時空開銷也比較大。在搜索引擎領域的實際應用中，一般將機械分詞方法與統計分詞方法相結合，先進行串匹配分詞，然後使用統計方法識別一些未登錄的新詞，這樣既發揮了匹配分詞速度快、效率高的優勢，又利用了統計分詞中新詞自動識別和自動消除分詞歧義的特點。分詞詞典是影響中文自動分詞的一個重要因素，其規模一般在6萬條詞左右，詞典太大或太小都是不合適的; 辭典太小，有些詞切分不出來，辭典太大，切分過程中起義現象將大大增加，同樣影響分詞的精度。因此，分詞詞典中詞條的選擇是非常嚴格的。對於不斷出現新詞的網路領域，僅僅使用6萬條詞左右的分詞詞典是不夠的，但隨意向分詞詞典中加入新詞將導致分詞精度下降，一般的解決方法是使用輔助詞典，其規模在50萬詞條左右。另外，中文自動分詞的難點在於分詞歧義的處理和未登錄詞的識別，如何處理這兩個問題一直是該領域研究的熱點。1. 歧義處理歧義是指可能有兩種或者更多的切分方法。例如: 「表面的」這個片語，因為「表面」和「面的」都是詞，那麼這個短語就可以分成「表面+的」和「表+面的」。這種稱為交叉歧義。像這種交叉歧義十分常見，「化妝和服裝」可以分成「化妝+和+服裝」或者「化妝+和服+裝」。由於沒有人的知識去理解，計算機很難知道到底哪個方案正確。交叉歧義相對組合歧義來說是還算比較容易處理，組合歧義就必須根據整個句子來判斷了。例如，在句子「這個門把手壞了」中，「把手」是個詞，但在句子「請把手拿開」中，「把手」就不是一個詞; 在句子「將軍任命了一名中將」中，「中將」是個詞，但在句子「產量三年中將增長兩倍」中，「中將」就不再是詞。這些詞計算機又如何去識別?即使交叉歧義和組合歧義計算機都能解決的話，在歧義中還有一個難題，是真歧義。真歧義意思是給出一句話，由人去判斷也不知道哪個應該是詞、哪個應該不是詞。例如: 「乒乓球拍賣完了」，可以切分成「乒乓+球拍+賣+完+了」、也可切分成「乒乓球+拍賣+完+了」，如果沒有上下文其他的句子，恐怕誰也不知道「拍賣」在這裡算不算一個詞。對歧義現象的處理方法一般採用類似於動態規劃的演算法將歧義問題的求解轉化為一個優化問題的求解。在求解過程中，一般使用詞頻或概率等輔助信息求得一個最大可能的分詞結果，這個結果在某種意義下是最佳的。2. 未登錄詞處理未登錄詞就是分詞詞典中沒有的詞，也稱為新詞。最典型的是人名、地名、專業術語等。例如，人可以很容易理解句子「王軍虎去廣州了」中，「王軍虎」是個詞，因為是一個人的名字，但要是讓計算機去識別就困難了。如果把「王軍虎」作為一個詞收錄到字典中去，全世界有那麼多名字，而且每時每刻都有新增的人名，收錄這些人名本身就是一項巨大的工程。即使這項工作可以完成，還是會存在問題，例如: 在句子「王軍虎頭虎腦」中的，「王軍虎」還能不能算詞？未登錄詞中除了人名以外，還有機構名、地名、產品名、商標名、簡稱、省略語等都是很難處理的問題，而且這些又正好是人們經常使用的詞，因此對於搜索引擎來說，分詞系統中的新詞識別十分重要。目前，對未登錄詞的處理一般採用統計的方法，首先從語料中統計出出現頻率較高的字組，然後按照某種規則把它們作為新詞添加到輔助詞典中。目前，中文自動分詞技術在搜索引擎中已經得到廣泛應用，分詞準確度已經達到96%以上，但是在對大規模網頁進行分析處理的時候，現有的中文自動分詞技術還存在許多不足，例如上面提到的歧義問題和未登錄詞的處理問題等。因此，國內外的科研院校，如北大、清華、中科院、北京語言學院、東北大學、IBM研究院、微軟中國研究院等都一直關注並研究中文自動分詞技術，這主要是因為網路上的中文信息越來越多，對網路上的中文信息的處理必將成為一個巨大的產業和廣闊的市場，存在無限的商機。但是，中文自動分詞技術要想更好地服務於網路中文信息的處理並形成產品，還要在基礎研究方面和系統的集成方面做許多工作。搜索引擎面臨的挑戰目前的搜索引擎不可能做到「博大精深」，這是因為它們是矛盾的兩個方面，不可兼得。隨著互聯網信息的急劇增長，關於搜索引擎的「博大」越來越難實現，從利用信息的角度也完全沒有必要，「精深」反而是人們越來越重視並追求的指標。另外，多層次的搜索服務體系遠遠沒有建立起來，傳統搜索重導航作用、輕精準信息服務，就像行人問路，行人需要的不僅僅是方向，還要知道具體的路標指示。現在人們經常談論下一代搜索引擎，那麼，下一代搜索引擎與第二代搜索引擎有什麼不同？又有什麼關係？它應該包括哪些功能？這些都是應該回答的問題，但答案是眾說紛紜。也許下一代搜索引擎融入了更強勁的智能化、人機交互等方法來改善相關度的計算，也許下一代搜索引擎不僅僅運行在大規模伺服器上，更有可能的是運行在共享計算資源的個人電腦集群上，或者植入「搜索晶元」中，也許其索引庫的邊界已經模糊、也許更加清晰，也許當下搜索巨頭通過資金、品牌等人為地不斷樹立的商業壁壘，終究抵擋不住創新搜索技術的顛覆，正如當初Google將Altavista無聲地瓦解一樣。——————————————————————————[相關鏈接]搜索引擎的技術流派搜索引擎的技術流派可以分為三類：第一類是利用計算機程序自動進行信息處理的自動化派，其典型代表是Google以及Ghunt等；第二類是以人工進行信息分類處理為主的人力加工派，這方面的典型代表是早期的Yahoo，正在興起的Web 2.0、網摘等社區化搜索是這一流派的新發展；第三類是強調智能化人機交互、協同的融合派，目前英文Yahoo的搜索引擎在發展這方面的技術，MSN Live也顯示出其更加重視融合性的技術，聯索IFACE專業搜索融入了用戶知識和機器學習方法，可以看做是融合派在中文搜索引擎方面的典型代表。如果按照網頁庫的容量、相關度計算技術、用戶搜索體驗以及商業模式等方面來劃分，到目前為止，搜索引擎的發展大約經歷了兩代。第一代搜索引擎(1994年～1997年)的索引網頁量一般都在數百萬量級左右，採用全文檢索技術和分散式並行運算技術，但極少重新搜集網頁並去刷新索引，而且其檢索速度較慢，一般都要等待10秒甚至更長的時間，同時承受的檢索請求也受到很大限制，商業模式處於探索期並且尚未成型。第二代搜索引擎(1998年至今)大多採用分散式協同處理方案，其網頁索引庫一般都在數千萬個網頁量級甚至更多，採用可伸縮的索引庫架構，每天能夠響應數千萬次甚至數以億計的用戶檢索請求。1997年11月，當時最先進的幾個搜索引擎宣稱能建立1億數量級的網頁索引。以Google為代表的第二代搜索引擎通過鏈接分析和點擊分析（網頁流行度）方法來計算（網頁權威性）相關度取得了巨大的成功。另外，以自然語言進行問題解答的搜索引擎在某種程度上改善了用戶體驗，更重要的是第二代搜索引擎奠定了目前搜索引擎普遍採用的成熟商業模式，如Google、Overture、百度等收費搜索服務均受益於此商業模式。相關名詞解釋全文搜索引擎 是由一個稱為蜘蛛(Spider)的機器人程序以某種策略自動地在互聯網中搜集和發現信息，由索引器為搜集到的信息建立網頁索引資料庫，由檢索器根據用戶輸入的查詢條件檢索索引庫，並將查詢結果返回給用戶。服務方式是面向網頁的全文檢索服務。目錄索引搜索引擎 主要以人工方式搜集信息，由編輯人員查看信息之後，人工形成信息摘要，並將信息置於事先確定的分類框架中。信息大多面向網站，提供目錄瀏覽服務和直接檢索服務。用戶完全可以不用關鍵詞（Keywords）進行查詢，僅靠分類目錄也可找到需要的信息。元搜索引擎 是指在統一的用戶查詢界面與信息反饋的形式下，共享多個搜索引擎的資源庫為用戶提供信息服務的系統。元搜索引擎是藉助於其他搜索引擎進行工作，沒有自己的索引庫，它是將用戶的查詢請求同時向多個搜索引擎遞交，將返回的結果進行重複排除、重新排序等處理後，作為自己的結果返回給用戶。自動分類技術 是計算機根據分類標準自動將文檔歸類到已經存在的類別體系（或者主題）下的某一個具體類別中。目前自動分類並不能完全代替人工所做的相關工作，只是提供了一個花費較少的可選擇方法。文本聚類技術 是利用計算機將已經存在的大量文本（很多文檔）進行分組的全自動處理過程。聚類可以提供對一個大的文本集內容的概況了解，可以識別隱藏的共同點，可以便捷地瀏覽相近或相關的文本。網文摘錄 又稱網摘，它具有對內容頁的收藏、分類、摘錄、加註標籤、保存到信息庫、信息庫共享等功能，主要是為了滿足用戶閱讀網路內容和信息知識積累的需要。（計算機世界報 2006年06月12日 第22期 B12、B13、B14）
推薦閱讀：
※新發現的搜索引擎列表之二
※引得市市什麼
※快速理解索引原理
※「松鼠的窩」專欄文章索引
※詩經研究論著索引（1991——2000年）