基于SDL的網絡搜索引擎系統的形式化研究

劉 業，吳建平

（蘇州市職業大學計算機工程學院，蘇州 215104）

0 引言

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

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

1 搜索引擎系統的分層結構

一般來說，搜索引擎主要分為三個部分，分別是網絡爬蟲、高效數據庫和前端應用。

1.1 網絡爬蟲

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

1.2 高效數據庫

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

1.3 前端應用

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

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

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

2 搜索引擎系統的形式化描述

一個SDL系統一般由系統system、功能塊block、進程process、過程procedure四個層級構成。系統以外的部分被視為當前SDL系統的外部環境，外部環境也可以用另一個SDL系統來描述。SDL系統通過信道channel與外部環境env進行通信。SDL描述系統行為的本質是帶消息收發的有限狀態機。

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

2.1 搜索引擎系統的系統結構

搜索引擎系統的系統結構細分為三大模塊，如圖1所示，分別為網絡爬蟲Spider，數據庫模塊Database和前端模塊FrontEnd。與外界通信的模塊是Spider和FrontEnd。幾個模塊之間通過三個信道進行通信，分別針對Spider對Database的查詢和寫入操作，以及前端對Database的查詢操作。

圖1 搜索引擎系統的系統結構圖

2.2 網絡爬蟲模塊

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

圖2 網絡爬蟲Spider模塊圖

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

圖3 WebGetter進程圖

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

圖4 WebParser進程圖

2.3 數據庫模塊

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

圖5 數據庫模塊圖

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

圖6 倒排索引reverse_index進程圖

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

圖7 查詢處理handler進程圖

2.4 用戶前端FrontEnd

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

圖8 前端模塊FrontEnd

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

圖9 用戶接口流程

3 結語

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