蒙古文信息檢索系統的設計與實現

溫子瀟，包飛龍，高光來，王勇和，蘇向東

(內蒙古大學 計算機學院，內蒙古 呼和浩特 010021)

0 引言

隨著科學技術的不斷發展，互聯網上的信息也在呈指數增長。目前，很多中英文信息檢索系統層出不窮，但針對蒙古文的信息檢索系統還不夠完善，且相對較少。

蒙古文是蒙古族使用的語言文字，主要分布在中國的內蒙古自治區和蒙古國。中國與蒙古國使用的蒙古文字具有一定的差異。“語同文不同”，即指語言相同，但文字不同。蒙古國使用的蒙古文稱為“西里爾蒙古文”(也稱為新蒙文[1])，中國使用的蒙古文稱為“傳統蒙古文”(也稱為舊蒙文或老蒙文)。隨著信息的日益增長，蒙古文也急需一種信息檢索系統，來滿足人們的信息檢索層次的需求[2]。

一些科研工作者對蒙古文信息檢索系統進行了很多相關研究工作。金威[3]通過對傳統蒙古文語法及構詞進行詳細分析后，解決了如何構建蒙古文索引詞的問題。同時，搭建了一個較為完善的蒙古文信息檢索平臺。李業榮[4]根據傳統蒙古文語言特點，利用信息檢索技術實現了一個相對完善的蒙古文搜索引擎原型系統。劉娜[5]在基于傳統蒙古文語義的基礎上，利用信息檢索模型，構建了蒙古文信息檢索系統。以上研究工作均是基于傳統蒙古文而言的，而基于西里爾蒙古文的信息檢索系統研究成果還相對較少。上述研究人員不僅為蒙古文信息檢索的發展起到了積極促進作用，還為本系統的構建提供了重要參考價值。

本文基于傳統蒙古文和西里爾蒙古文，構建了一個性能優良的信息檢索系統。該系統可以同時對傳統蒙古文和西里爾蒙古文進行關鍵詞檢索。本文結構如下: 第一部分介紹了系統的整體框架；第二部分介紹了對網絡爬蟲改進的MD5算法；第三部分介紹了對蒙古文編碼轉換、詞綴切分和編碼校正等預處理操作；第四部分介紹了蒙古文索引的構建方法；第五部分介紹了向量空間模型的檢索原理、搜索結果排序打分的算法原理；第六部分介紹了系統具體實現以及性能評價。

1 系統框架

系統整體框架如圖1所示。系統整體框架主要分為兩大模塊，即文檔獲取模塊和文檔檢索模塊。文檔獲取模塊，通過網絡爬蟲獲取傳統蒙古文和西里爾蒙古文文檔庫，對每篇文檔進行編碼轉換、詞綴切分以及編碼校正等預處理操作，最后對處理后的文檔建立索引。文檔檢索模塊，首先對輸入的關鍵詞進行詞綴切分，然后在索引庫中進行檢索，最后將檢索出的文檔根據與輸入關鍵詞的相關性排序輸出。此外，為了方便用戶對西里爾蒙古文的閱讀，在系統中加入了西里爾蒙古文到傳統蒙古文轉換以及網站更新統計等功能模塊，滿足用戶多樣化的需求。

圖1 檢索系統框架圖

2 網絡爬蟲

網絡爬蟲[6-8]是一個自動提取網頁的程序。它為搜索引擎從因特網上下載網頁，是搜索引擎的重要組成。抓取流程主要分為三個部分: 產生、解析和提取。傳統爬蟲從一個或若干初始網頁的URL開始，即種子URL。獲得初始網頁上的URL，在抓取網頁的過程中，不斷從當前頁面上抽取新的URL放入待抓取隊列。然后，采用廣度優先或者深度優先遍歷的方法，遍歷整個隊列，直到滿足系統的一定停止條件。例如，抓取的深度達到設定的閾值爬蟲則停止[9]。爬蟲的工作流程較為復雜。需要根據一定的網頁分析算法過濾與主題無關的鏈接，并對重復的URL進行去重操作。去重操作可以大大提高爬蟲的效率，最后保留有用的新產生的鏈接并將其放入等待抓取的URL隊列。

2.1 爬蟲優化改進

去重操作對爬蟲性能的改善有決定性作用。本文在爬蟲中使用MD5[10]去重算法，使爬蟲的性能得到了極大的提升。本文中爬蟲的去重操作并不是指對單個URL進行重復性判斷，而是對整個網頁html進行去重。使用單個鏈接去重的方法不僅要重新解析當前網頁中URL，還要對這些URL進行重復性判斷，嚴重影響了爬蟲的速度。使用MD5算法對整個網頁html文件進行去重操作，觀測整個網頁的內容是否發生變化。若網頁中的內容并沒有變化，將該網頁直接去掉即可。這樣會省去很多不必要的操作，最大限度降低時間和空間的復雜度，提升爬取效率。

MD5即Message Digest Algorithm 5(信息—摘要算法5)，用于確保信息傳輸完整一致。是計算機廣泛使用的雜湊算法之一(又譯摘要算法、哈希算法)。MD5算法具有以下特點。

(1) 壓縮性: 任意長度的數據，算出的MD5值長度都是固定的。

(2) 容易計算: 從原數據計算出MD5值很容易。

(3) 抗修改性: 對原數據進行任何改動，哪怕只修改1個字節，所得到的MD5值都有很大區別。

(4) 抗碰撞性: 已知原數據和其MD5值，想找到一個具有相同MD5值的數據(即偽造數據)是非常困難的。

通過簡單的計算，我們可以知道使用該算法理論上可以使空間的利用率提高60倍。同時經過試驗，我們對將近30萬條的URL進行去重實驗，并對不同的去重方法進行了比較，從表1中可以看出，爬蟲的效率提高了很多。

表1 去重方式對比

本文使用的測試環境為Inter Core i3-21003.10Ghz的內存大小為10GB。在30萬條URL中，進行了30次實驗，最終得出了每種去重算法耗時的平均時間。從表1中可以看出，使用MD5去重耗時最短。使用MD5算法進行去重時，去重時間跟URL的多少是沒有關系的。而其他兩種去重算法隨著URL數量的增大，去重時間也會隨之成正比例的增長。因此，在URL很大的情況下，MD5算法仍然可以保持高效的去重效率。當數據量相對較小時，MD5算法的性能并不一定優于其他兩種去重方法，該算法只在大數據量的情況下有較好的去重效率。

3 文本預處理

在實現蒙古文檢索時，考慮到蒙古文的特點及數據來源(均是從各大網站上抓取下來的)，故文本的格式、編碼均不統一。所以，需要對提取的文本進行預處理，將原始數據轉換成統一格式，以方便后續的檢索處理。

文本預處理的一般步驟主要有: 文本的獲取、轉碼、詞綴的切分以及去除停用詞等操作。此外，由于蒙古文自身結構特點，有的詞從字形上看是正確的，可它的內部編碼卻是錯誤的。而在多數情況下，計算機是按照字符編碼識別詞匯，若不糾正這些錯誤，將加大后續處理的難度，故在預處理階段還需要對蒙古文進行編碼校對。預處理過程不僅可以減小索引的空間，還可以提高搜索的精度。

3.1 編碼轉換

獲取到文章后，需要對蒙古文的文檔進行格式統一，以方便計算機辨認出文檔的不同部分然后進行檢索。這些內容的區分對信息檢索來說是十分必要的，也是檢索系統實現的一個重要先決條件。大部分蒙古文的網站使用的編碼方式均為蒙科立編碼。因此，本文將蒙科立編碼的蒙古文轉換為國際標準編碼的蒙古文。

蒙科立編碼采用變形顯現字符編碼，國際標準編碼采用名義字符編碼。在使用蒙科立編碼的蒙古文中，一個相同的字符，出現在不同蒙古文詞的不同位置時，它的編碼不同。而在國際標準編碼中，無論該字符出現在任何位置，均使用統一編碼。為了使所有的數據在我們的系統中具有唯一的編碼，需要對蒙古文進行編碼轉換。采用基于規則和詞典的方法，來實現蒙科立編碼的蒙文轉換為國際標準編碼的蒙古文，圖2為轉換后的文檔。

圖2 處理后的文檔

3.2 詞綴切分

蒙古文依據其本身的構詞特點與書寫規則，是由空格進行分詞的。蒙古文詞匯通常包括兩部分，詞干和詞綴。與英文的區別在于，蒙古文詞匯中沒有前綴和中綴，只有后綴。蒙古文中一個詞干后面可以連接多種后綴，形成大量代表不同意義的詞。如果不對其進行詞干的切分，將會導致索引庫規模過于龐大，嚴重影響檢索的速度。因此，對蒙古文進行詞干提取是很有必要的。蒙古文在去除詞綴后，不僅可以有效地提高搜索的效率，還能減少索引的存儲空間。

傳統蒙古文和西里爾蒙古文切詞: 首先要將蒙古文按照空格分詞。以詞級為單位，從后綴表和詞干庫中匹配到當前單詞的后綴和詞干。再采用基于規則的方法進行詞綴切分，提取詞干。表2為西里爾蒙古文切分詞綴后得到的詞干表。

表2 切分后得到的詞干表

4 索引構建

將非結構化數據中的一部分信息提取出來，重新組織，使其具有一定結構。然后，對這些有一定結構的數據進行搜索，從而達到搜索相對較快的目的。這部分從非結構化數據中提取出來的數據，重新組織后的信息，稱之為索引。將輸入的數據以倒排索引的數據結構進行存儲，索引的建立可以極大地提升搜索速度。倒排索引主要用來存儲全文搜索條件下，某一個單詞在一篇文檔或文檔集中存儲位置的映射關系及其他信息。本文倒排索引如表3所示。

表3 倒排索引

5 檢索模型與重排序

信息的檢索與排序是信息檢索系統的核心部件。檢索部分是從用戶那里得到需求信息，利用向量空間模型的檢索原理在索引文件中進行查詢，檢索的效率依賴于構建索引的結構。排序部分是將檢索出的結果生成一個按分值排序的文檔列表。目的是盡量給用戶返回和用戶提問最相關的文檔集合。

5.1 向量空間模型

將建立完成后的索引，利用向量空間模型[11]，將查詢關鍵詞和文檔都表示成為向量。文檔和查詢關鍵詞之間的相似度通過向量夾角的余弦值表示。在檢索時,查詢關鍵詞為Q，文檔集合D=(D1,D2,...,Dn)，則檢索的過程可以描述為計算Q與Dj的相關程度。

在向量空間檢索模型中,把文檔和用戶查詢均用一組相互獨立的詞條組成,設在文本集中,共使用了n個詞條t1,t2,...,tn。文本集中某一文檔dj可表示為:dj=(wj1,wj2,...,wjn),其中wi1,wi2,...,win分別為詞t1,t2,...,tn在文檔dj中的權值。權值越大,表示該詞在文檔中的份量越大,即該詞越能反映dj的內容: 如果權值越小，說明該詞的份量越小,越不能反映dj的內容。權值的取值范圍是[0,1]。同樣地,用戶的查詢可表示為q=(w1,w2,...,wn),其中w1,w2,...,wn分別為給出的t1,t2,...,tn的權值。把幾個詞看作為n維坐標系中的坐標,權植對應其坐標值。這樣,文檔和用戶查詢均可看成是由這坐標軸組成空間中的一個點,或稱為一個矢量。計算相似度有多種方法,一般常用式(1)計算。

(1)

Wi代表權重，即這個詞在文本檢索中的重要程度。一般地，通過式(2)計算權值。

Wij=TFi,j×IDFi

(2)

TF是指Term Frequency表示詞i在文檔Dj中出現的次數，即詞頻；IDF是指Inverse Document Frequency。IDF定義如式(3)所示。

(3)

公式中，N表示文檔集合中所有的文檔的數目，ni表示整個文檔集合中出現過詞i的文檔的總數，稱為逆文檔頻率。

模型的優點: 利用向量空間模型進行檢索，可以通過調節權值的大小來反映關鍵詞與文檔的相關程度。檢索時要計算文檔間的相似度，使得屬相相似的文檔會聚集在一起，提高檢索的效率。

5.2 搜索排序算法

我們需要將搜索出的文章根據其與查詢的相關性進行打分排序。目的是將與用戶提問最相關的檢索結果排在最前面返回給用戶，更好地滿足用戶的需求。本系統使用的是一種改進的TF-IDF的排序算法，排序如式(4)所示。

Score(q,d)=cord(q,d)×queryNorm(q)×

∑(tf(tind)×idf(t)2t.getBoost()×norm(t,d)

(4)

(1)cord(q,d)為協調因子。表示文檔(d)中Term(t)出現的百分比，也就是計算查詢條件(q)中不同Term(t)，以及在文檔中出現的數量之和，兩者的數量之比。通常在文檔中出現查詢Term種類越多，分值越高。

(2)queryNorm(q)，為調節因子。不影響索引排序情況，只在檢索時使用。主要是用來讓排序結果在不同的查詢條件之間可以比較。這個條件是在搜索時計算。數值是根據每一個查詢項權重的平方和計算得到。計算如式(5)所示。

queryNorm(q)=

(5)

(3)tf(tind)，為文檔頻率，表示查詢詞中，每個Term在對應的結果文檔(d)中出現的次數。查詢詞出現的次數越多，表示出現頻率越高，文檔的檢索得分就越高。為了避免獲得更大的相關性函數，實際中，使用次數的平方根作為文檔頻率tf的值，避免數值過度放大。

(4)idf(t)2，為逆文檔頻率。用于檢索匹配文檔數量的反向函數。按照信息理論，文檔出現的次數越少，每一篇文檔的信息量就會越大。所以匹配的文檔數越少，得分就越高。而索引庫中文檔總數越多，找到一篇目標文檔難度越大，相應的信息量也會越大。

(5)norm(t,d)，為長度因子。由每個索引詞匯在域中的總體長度決定的，這個參數在索引建立時確定。數值根據文檔中實際具有的索引項個數確定。檢索詞長度在文檔總長度中占的比例越大，長度因子的數值也越大。

根據文檔與查詢的相關程度的大小，綜合考慮關鍵詞在文檔中出現的詞頻等各項指標。對檢索出的每一篇文檔進行打分，分值越高說明該篇文檔與查詢詞的相關程度越高。返回結果時，隨著分數的高低依次排列輸出給用戶。

6 系統實現

在系統實現階段，本系統可以同時對傳統蒙古文和西里爾蒙古文進行檢索。并在系統中加入了西里爾蒙古文轉換傳統蒙古文和網站更新統計模塊，方便用戶使用，最后對系統的性能進行了評測。

6.1 檢索模塊

在預處理后的文檔上，采用Lucene[12-14]工具對蒙古文文檔構建索引并實現檢索，索引的內容包括新聞的標題，正文。檢索的實現分為三個步驟: 第一，用戶輸入要檢索的關鍵詞；第二，使用向量空間檢索模型，在建立的倒排文檔中進行關鍵詞檢索；第三，將結果打分排序后反饋給用戶。系統在文檔庫中的檢索結果分別如下圖所示。圖3為使用西里爾蒙古文檢索得到的結果，圖4為使用傳統蒙古文檢索得到的結果，系統采用豎排的方式顯示傳統蒙古文，檢索的關鍵字會在文中標紅。

圖3 西里爾蒙古文檢索結果

圖4 傳統蒙古文檢索結果

6.1.1 檢索測試

本文將三個關鍵詞，放在不同索引規模中進行檢索測試。從表4中可以看出，對于同一個關鍵詞，索引的規模對于系統檢索速度影響不大，并不是索引規模越大檢索時間越長，檢索的時間主要是受命中數影響。從檢索時間上可以看出系統在實際應用中，基本可以滿足用戶快速檢索的需求。

表4 檢索測試

續表

6.2 西里爾蒙古文到傳統蒙古文轉換模塊

為了方便我國用戶的使用、加快對西里爾蒙古文的閱讀速度，對于系統中檢索出的西里爾蒙古文，利用SOPA調用了西里爾蒙古文到傳統蒙古文轉換的Web Service接口，在系統中加入西里爾蒙古文轉換為傳統蒙古文的功能模塊。對于西里爾蒙古文轉換為傳統蒙古文，采用基于詞典和規則的方法與基于統計模型的方法[15-16]相結合的方法，使得轉換更高效。圖5為轉換后的結果。

圖5 西里爾蒙文轉換為傳統蒙文

6.3 網站更新統計模塊

系統中加入了對蒙古文網站的更新統計和管理模塊。用戶不僅可以自己增減想要查看的蒙古文的網站，還可以查看蒙古文網站每天、每月、每年的更新量。系統會將統計的數據以圖表的形式顯示，給用戶一個相對直觀的感覺。該模塊充分考慮到用戶對網站側重度的不同，可以自主增、刪、改所要關注的網站，同時，系統還提供了不同網站的更新統計圖，滿足用戶對系統的個性化需求，如圖6所示。

圖6 網站更新統計

6.4 系統性能評價

本文利用爬蟲從網上抓取了30多萬個新聞網頁作為測試文檔集，設計了10個查詢作為查詢集，通過人工比較的方法本文獲得這些查詢的相關文檔數。參評指標主要采用MAP和P@N兩個指標，其含義如下:

(1) MAP(Mean Average Precision)

單個主題的平均準確率是每篇相關文檔檢索出結果后的準確率的平均值,是反映系統在全部相關文檔上性能的單值指標。系統檢索出來的相關文檔越靠前則分數就越高，反之則分數越低。

(2) P@N(Precision @ N)

是系統對于該主題返回的前N個結果的準確率。考慮到用戶在查看搜索引擎結果時，往往希望在第一頁或者第二頁就找到自己所需的信息。因此，取N為10、15、20來對系統進行性能評價，常常能比較有效地反映系統在真實應用環境下所表現的性能。

從表5中可以看出，MAP與檢索出的文檔位置有關，誤檢的文檔越靠前MAP值越小，隨著N值的增大誤檢的錯誤率也增大，但是系統平均的MAP值基本保持在80%左右。

表5 不同N值下檢索結果的MAP和P@N

7 結論與展望

本文基于蒙古文的語言特點構建了一個可以同時檢索傳統蒙古文和西里爾蒙古文的信息檢索系統。在文檔獲取階段，對網絡爬蟲進行了改進，使用MD5算法對網頁文件進行去重，提升了爬蟲的爬取速度。在文本預處理階段，對蒙古文進行編碼轉換、詞綴切分以及編碼校正等操作，將原始的數據轉換成統一的格式，方便后續建立索引和檢索處理。在檢索階段，使用向量空間檢索模型對倒排索引文檔進行檢索。系統可以對傳統蒙古文和西里爾蒙古文兩種不同形式的蒙古文進行檢索，并對檢索到的文檔集合進行打分排序，返回給用戶最相關的查詢結果。在系統的實現階段，考慮到我國大部分人使用的是傳統蒙古文。系統中加入了西里爾蒙古文到傳統蒙古文轉換的模塊，以方便用戶閱讀。同時，在系統中加入了網站更新統計的模塊，用戶不僅可以獲得每個網站每天、每月以及每年的更新統計量，還可以根據需要增、刪、改想要關注的網站，滿足用戶個性化的需求。最后對系統的性能進行了評測，從結果來看，系統已經達到了可應用的水平。