劉 業(yè)，吳建平

（蘇州市職業(yè)大學(xué)計算機工程學(xué)院，蘇州 215104）

0 引言

早期的搜索引擎如Yahoo等基于分類模式的開放式目錄搜索，是一種類似于黃頁的服務(wù)，它將搜索的內(nèi)容事先進(jìn)行分類，用戶通過選定不同的類別進(jìn)入相應(yīng)的網(wǎng)站，然后尋找自己想要的信息。嚴(yán)格地說，這不是一個真正意義上的搜索引擎，因為它并沒有最終給出用戶所需信息的頁面，而是提供一種索引方式，來減少用戶找到所需信息的時間。隨著時間的推移，使用Yahoo的基礎(chǔ)用戶大為減少。隨著Google、百度的相繼出現(xiàn)，真正意義上的全文搜索引擎被實現(xiàn)出來作為網(wǎng)絡(luò)服務(wù)放在互聯(lián)網(wǎng)上，通過這種服務(wù)，用戶可以定位到包含關(guān)鍵字的網(wǎng)頁上，真正實現(xiàn)了從源到目的地的連接。然而互聯(lián)網(wǎng)上的信息以指數(shù)級增長，如何提高搜索的準(zhǔn)確度，提高搜索的效率等諸多問題都成為了Google和Baidu等公司的技術(shù)問題，全文搜索引擎仍有很大的技術(shù)空間需要長時間的發(fā)展。

與在軟件開發(fā)領(lǐng)域應(yīng)用廣泛的UML語言相比，SDL語言主要是電信設(shè)備提供商廣泛使用的一門形式化語言。SDL由ITU-T（國際電信聯(lián)盟電信標(biāo)準(zhǔn)分局）制定，在ITU-T Z.100中給出了SDL的完整定義。它利用直觀的二維圖形將通訊協(xié)議高效簡潔地描述出來。但SDL不是諸如C、Java這樣的編程語言，用SDL形式化系統(tǒng)之后還是需要將它改寫成實際可運行的程序才有實際價值。本文借助于集成開發(fā)工具（Telelogic TAU）使用SDL對全文搜索引擎系統(tǒng)進(jìn)行形式化建模和分析。

1 搜索引擎系統(tǒng)的分層結(jié)構(gòu)

一般來說，搜索引擎主要分為三個部分，分別是網(wǎng)絡(luò)爬蟲、高效數(shù)據(jù)庫和前端應(yīng)用。

1.1 網(wǎng)絡(luò)爬蟲

網(wǎng)絡(luò)爬蟲也叫網(wǎng)絡(luò)蜘蛛，顧名思義，如同把一只蜘蛛放在一張網(wǎng)上，蜘蛛在網(wǎng)上以某種規(guī)則爬行，遍歷網(wǎng)上所有的覆蓋區(qū)域。Web可以抽象成一個圖（實際上通過它的名字我們就可以想象出來它是一張網(wǎng)），每一個網(wǎng)頁是圖上的一個節(jié)點，網(wǎng)頁之間的鏈接則是鏈接各個點之間的邊。網(wǎng)絡(luò)爬蟲是一個程序，它訪問互聯(lián)網(wǎng)上的各個網(wǎng)站，抓取網(wǎng)頁的內(nèi)容，通過對網(wǎng)頁之間超鏈接的分析，跳轉(zhuǎn)到另一個相鏈接的網(wǎng)頁，如此遍歷整個Internet。同時，每抓取一個網(wǎng)頁，把網(wǎng)頁全文存到數(shù)據(jù)庫當(dāng)中，并計算相應(yīng)需要的網(wǎng)頁信息（如網(wǎng)頁rank，meta信息，字符區(qū)域編碼等），也存入到數(shù)據(jù)庫當(dāng)中。

1.2 高效數(shù)據(jù)庫

由于網(wǎng)頁內(nèi)容的容量十分龐大，而且以字符流的形式儲存在數(shù)據(jù)庫中，因此查找信息的時間效率十分的低，對數(shù)據(jù)庫的要求很高。除了需要高效的數(shù)據(jù)庫之外，一些高級數(shù)據(jù)庫技術(shù)也用f來支持搜索引擎的使用，例如倒排索引等。因此，嚴(yán)格意義上來說，搜索引擎提供的搜索結(jié)果不等于網(wǎng)絡(luò)爬蟲所抓下來的內(nèi)容，而是建立好倒排索引的文檔。倒排索引的效率好壞和實現(xiàn)算法直接影響查找結(jié)果的時效性。此外，某些關(guān)于page rank等的算法，也需要在數(shù)據(jù)庫的基礎(chǔ)上進(jìn)行計算和分析。這一層也是搜索引擎的核心和決定一個搜索引擎好壞的關(guān)鍵部分。目前Google和Baidu等公司在這些領(lǐng)域都有自己獨有的技術(shù)，也是它們能夠有強大的市場競爭力的保證。

1.3 前端應(yīng)用

前端應(yīng)用是針對用戶提出的搜索條件進(jìn)行分析的程序。主要包括分詞、語義匹配、高級查詢等功能。英文分詞因為其語言特性，在國外發(fā)展已經(jīng)比較成熟。而中文分詞系統(tǒng)一直是我國的一項重大研究課題。由于漢字的字符數(shù)量非常龐大，加上語言規(guī)則復(fù)雜，擁有幾千年的發(fā)展歷史，因此中文分詞還需要很多研究工作來攻克各種技術(shù)問題。Baidu在中文市場的優(yōu)勢也在于它的中文分詞系統(tǒng)和相對應(yīng)的倒排索引技術(shù)。

語義匹配也是搜索引擎的一個關(guān)鍵技術(shù)。它來源于模糊查詢，例如一個用戶輸入“如何購買一輛汽車”，前端應(yīng)用程序不是簡單地去數(shù)據(jù)庫查找字面上出現(xiàn)類似關(guān)鍵字的結(jié)果，而是可以對這個搜索條件進(jìn)行分析，而返回真正的對購買汽車有幫助的頁面。

其他的諸如分類查詢、垂直查詢、手機查詢等，是搜索引擎所提供的一些擴展功能，這些功能主要也是由前端應(yīng)用來完成。針對不同的需求，前端可以分成若干子層，這里不做過多討論。

2 搜索引擎系統(tǒng)的形式化描述

一個SDL系統(tǒng)一般由系統(tǒng)system、功能塊block、進(jìn)程process、過程procedure四個層級構(gòu)成。系統(tǒng)以外的部分被視為當(dāng)前SDL系統(tǒng)的外部環(huán)境，外部環(huán)境也可以用另一個SDL系統(tǒng)來描述。SDL系統(tǒng)通過信道channel與外部環(huán)境env進(jìn)行通信。SDL描述系統(tǒng)行為的本質(zhì)是帶消息收發(fā)的有限狀態(tài)機。

Telelogic TAU是瑞典Telelogic公司推出的一款SDL語言的集成開發(fā)環(huán)境，目前由IBM公司收購并維護(hù)后續(xù)軟件版本，用于實現(xiàn)SDL系統(tǒng)形式化過程中的畫圖、仿真、測試、執(zhí)行、自動代碼生成、早期錯誤檢測等功能，其最大特點在于SDL和MSC的圖形化，為各種設(shè)計和開發(fā)任務(wù)提供自頂向下的工程設(shè)計輔助方法。其中，當(dāng)前自動代碼生成的是C++代碼，代碼中變量函數(shù)名全部都是自動生成，代碼可讀性及可維護(hù)性非常差，目前這個模塊并沒有得到實際的使用。本文所有的形式化SDL圖都是通過Telelogic TAU給出。

2.1 搜索引擎系統(tǒng)的系統(tǒng)結(jié)構(gòu)

搜索引擎系統(tǒng)的系統(tǒng)結(jié)構(gòu)細(xì)分為三大模塊，如圖1所示，分別為網(wǎng)絡(luò)爬蟲Spider，數(shù)據(jù)庫模塊Database和前端模塊FrontEnd。與外界通信的模塊是Spider和FrontEnd。幾個模塊之間通過三個信道進(jìn)行通信，分別針對Spider對Database的查詢和寫入操作，以及前端對Database的查詢操作。

圖1 搜索引擎系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖

2.2 網(wǎng)絡(luò)爬蟲模塊

網(wǎng)絡(luò)爬蟲模塊主要有兩個進(jìn)程，如圖2所示，WebGetter，是用來抓取Internet網(wǎng)頁上的內(nèi)容；WebParser，則用來解析抓取下的內(nèi)容。WebGetter進(jìn)程所抓取的網(wǎng)頁內(nèi)容作為輸入發(fā)送給WebParser。WebParser所解析出來的URL地址會添加到地址隊列中，作為WebGetter的查找目的地。同時，WebParser也會通過與Database的通信來判斷是否待解析的URL已經(jīng)被訪問過。

圖2 網(wǎng)絡(luò)爬蟲Spider模塊圖

WebGetter進(jìn)程是用來抓取網(wǎng)頁內(nèi)容的進(jìn)程。它通過一個UrlQueue來存放即將訪問的網(wǎng)頁地址。由于Web網(wǎng)的結(jié)構(gòu)是一個圖結(jié)構(gòu)，因此通過對圖的生成樹進(jìn)行一種類似層序遍歷的訪問方式，就可以訪問到該圖中的各個節(jié)點。實際應(yīng)用中，由于Internet上的網(wǎng)頁可以有數(shù)十億個，而且有很多網(wǎng)頁每天都在更新，因此理論上WebGetter是一個永不終止的進(jìn)程。在一個運算能力不是很高的服務(wù)器上，WebGetter的網(wǎng)頁抓取速度并不能超越Internet上的網(wǎng)頁更新速度。因此從圖3可以看到，此進(jìn)程沒有終止?fàn)顟B(tài)，它不停地等待即將抓取的網(wǎng)頁URL，除非人為終止它，即發(fā)送一個stop_signal。由于即將訪問的URL并不總是有效的，因此它會自行判斷此URL是否可以連接，如圖中的判斷語符號所示，如果不可以連接，則放棄抓取此URL，跳入下一個網(wǎng)頁繼續(xù)抓取。WebGetter把抓取的網(wǎng)頁內(nèi)容，以及一些相關(guān)信息送入Database存儲起來，通過消息content送至Database。

圖3 WebGetter進(jìn)程圖

WebParser進(jìn)程的主要作用是控制UrlQueue，進(jìn)程狀態(tài)圖如圖4所示，它通過對每個抓取網(wǎng)頁的分析，提取出其中的超鏈接地址，并加入到UrlQueue中去。由于其中的某些Url可能已經(jīng)訪問過，因此不必將此Url再加入到隊列中去。這里訪問過的意思是通過某種算法標(biāo)準(zhǔn)，在一個時間界定范圍內(nèi)被訪問過，例如一個新聞網(wǎng)站，雖然可能在數(shù)據(jù)庫中存在著此Url，但是經(jīng)過12或24小時之后，其中很多新聞已被更新，有必要重新抓取新的網(wǎng)頁內(nèi)容，因此將其定義為“未訪問過”，即isVisited信號為0。WebParser通過到數(shù)據(jù)庫中查詢Url和訪問時間來確定此條地址是否被訪問過。

圖4 WebParser進(jìn)程圖

2.3 數(shù)據(jù)庫模塊

數(shù)據(jù)庫模塊主要分為兩大部分，分別為倒排索引部分reverse_index和查詢處理部分handler，如圖5所示。由于SDL對于非通信的實體關(guān)系之間描述能力比較弱，數(shù)據(jù)庫部分雖然是搜索引擎的核心部分，用SDL描述卻比較簡單，因此涉及到消息傳遞的通信動作只有少數(shù)幾個。可以看到，reverse_index和handler部分之間在途中是沒有消息傳遞的，這是因為它們之間是通過數(shù)據(jù)庫內(nèi)所存儲的內(nèi)容間接交換信息，只有在添加新的網(wǎng)頁內(nèi)容時，系統(tǒng)通過reverse_index將同樣的內(nèi)容傳遞給handler一份用來將其存入數(shù)據(jù)庫中。這里的SDL并沒有描述如何建立倒排索引的算法，實際上關(guān)于建立倒排索引的算法一直是計算機領(lǐng)域所需要解決的研究問題之一，如今并沒有一個絕對最優(yōu)的倒排索引算法，而且Google和Baidu等公司的倒排索引算法也不對外公開，但是其基本思想都是一樣的。由于SDL本身對算法描述的能力較弱，因此此處不對建立倒排索引的方法過多研究，只關(guān)心它們的消息處理流程。

圖5 數(shù)據(jù)庫模塊圖

倒排索引是全文搜索引擎的核心部分，但是它的對外消息收發(fā)流程卻十分簡單，因此主要的工作都是內(nèi)部的算法實現(xiàn)問題。如圖6所示，建立倒排索引主要有兩種方式，一種是基于新的索引關(guān)鍵字，在數(shù)據(jù)內(nèi)已有的內(nèi)容中建立索引。另一種是由于不停地有網(wǎng)頁加入進(jìn)數(shù)據(jù)庫中，對網(wǎng)頁的內(nèi)容進(jìn)行分析處理加入到相應(yīng)的關(guān)鍵字索引中也是該進(jìn)程的主要工作。由于搜索引擎是一種web服務(wù)，因此該進(jìn)程也沒有結(jié)束狀態(tài)，只要服務(wù)正常提供，那么進(jìn)程將不停地處理下去。

圖6 倒排索引reverse_index進(jìn)程圖

數(shù)據(jù)庫的主要工作是處理查詢請求。不僅是來自用戶的關(guān)鍵子查詢，也有來自于系統(tǒng)內(nèi)部為了實現(xiàn)功能而需要的查詢請求。如圖7所示，該進(jìn)程主要處理三種消息。來自前端的keyword查詢，通過索引找到匹配的網(wǎng)頁內(nèi)容，然后發(fā)送回前端；來自WebParser的isVisited查詢，進(jìn)程先查找出該URL所在的內(nèi)容，然后通過某種時間標(biāo)準(zhǔn)判斷是否被Visit過，返回給Web-Parser一個0或者1作為結(jié)果；來自reserve_index的web content，進(jìn)程將網(wǎng)頁內(nèi)容和其他信息如訪問時間、pangeank等一并添加入數(shù)據(jù)庫中。不管哪種輸入，進(jìn)程處理完之后都將回到初始狀態(tài)，等待下一條輸入消息發(fā)送過來。

圖7 查詢處理handler進(jìn)程圖

2.4 用戶前端FrontEnd

用戶前端一般來說以一種Web方式提供搜索引擎服務(wù)。這里主要的技術(shù)難點是分詞處理系統(tǒng)。如前所述，由于本文的內(nèi)容集中在討論SDL描述消息處理流程問題，因此未對詳細(xì)算法進(jìn)行分析。這里前端主要接收用戶的查詢輸入，并向數(shù)據(jù)庫提交查詢請求，然后將查詢結(jié)果顯示出來。如圖8所示，前端模塊有一個進(jìn)程，為user_interface，顧名思義，它的主要功能是提供給用戶一個應(yīng)用接口，讓用戶來調(diào)用自己的服務(wù)。一般來說，以Google和Baidu為主的搜索引擎廠商提供的是POST方式的服務(wù)調(diào)用方式，可以很好地支持HTTP協(xié)議，并且接收比較大的查詢請求。而顯示搜索結(jié)果采用的是HTML的網(wǎng)頁方式，用戶直接選擇相應(yīng)結(jié)果對應(yīng)的超鏈接即可找到搜索的網(wǎng)頁。

圖8 前端模塊FrontEnd

用戶接口進(jìn)程是一個順序處理流程，如圖9所示。它等待用戶的查詢輸入，并且通過對查詢請求的解析，來獲得可以讓數(shù)據(jù)接收的查詢關(guān)鍵字。這里的parseQuery過程主要包括分詞、語義匹配、布爾檢索翻譯等工作。然后將解析后的關(guān)鍵字送入數(shù)據(jù)庫獲得查詢結(jié)果。最后將查詢結(jié)果以特定的方式顯示在界面上，供用戶瀏覽。同樣，由于它是一種web服務(wù)，因此沒有終止?fàn)顟B(tài)，只要服務(wù)存在，此進(jìn)程將一直工作下去，這點和很多電信通信服務(wù)類似。

圖9 用戶接口流程

3 結(jié)語

包括搜索引擎在內(nèi)的很多WEB服務(wù)同通信系統(tǒng)設(shè)計一樣，是一種一旦部署好就一直存在著的服務(wù)。當(dāng)前已有的文獻(xiàn)基本都是使用UML對搜索引擎系統(tǒng)進(jìn)行描述和建模，本文通過對搜索引擎系統(tǒng)的分析，以信號傳輸為重點，研究了系統(tǒng)的各個模塊與進(jìn)程之間的消息傳輸關(guān)系。從一個宏觀的角度來觀察搜索引擎服務(wù)，自頂向下逐層細(xì)化。本文將SDL這種普遍用于描述通信系統(tǒng)的語言應(yīng)用于WEB服務(wù)上，是一種可以研究的新的嘗試。