全文檢索的原理與實現探討

〔摘 要〕本文主要在介紹全文檢索的概念和原理的基礎上，論述了全文檢索的幾種主要技術，并給出了逆向最大分詞法的具體實現。

〔關鍵詞〕全文檢索;搜索引擎;中文分詞

〔中圖分類號〕TP31 〔文獻標識碼〕A 〔文章編號〕1008-0821(2009)07-0138-03

Discussion on Principle and Implementation of Full Text SearchMan Peng

(Computer Center，Changchun University，Changchun 130022，China)

〔Abstract〕Based on the introduction of concept and theory of full text search，in this paper，it expounded a few primary technologies in full text search，proposed an implementation of reverse direction maximum word-dividing.

〔Key words〕full text search;search engine;chinese division

全文檢索是對大數據文本進行索引，在建立的索引中對要查找的單詞進行搜索，定位哪些文本數據包括要搜索的單詞。因此，全文檢索的全部工作就是建立索引和在索引中搜索定位，所有的工作都是圍繞這兩方面展開的。下面本文就對它的原理、技術和實現，一一加以分析與探討。

1 原 理

全文搜索的典型代表是網絡蜘蛛程序(網絡機器人)，可以通過對它的工作過程分析，分析出全文搜索的技術原理。網絡蜘蛛程序是一個自動搜索程序，可自動在互聯網上搜索信息。并且查看頁面的內容，然后從中找到相關的信息，最后再從該頁面的所有鏈接出發，繼續尋找其它相關的信息。網絡蜘蛛不斷的重復這個過程，并把經過的所有網頁收集到搜索引擎所在的服務器中，這個過程一般采用的是廣度優先算法。當網絡蜘蛛收集到信息后，接下來要進行以下幾個方面的工作:

1.1 建立索引數據庫

當網絡蜘蛛存儲網頁后，再由自定義程序對服務器中保存的網頁進行分析，提取相關網頁的URL、編碼類型、關鍵詞位置、生成時間、大小和與其他網頁的鏈接關系等。根據網站自定義的相關度算法進行運算，最后得到相關度信息，然后用這些相關信息建立網頁索引數據庫。

1.2 在索引數據庫中搜索

當用戶輸入搜索內容，單擊搜索按鈕后，系統自定義程序開始根據相關技術，分析用戶的搜索內容，然后從網頁索引數據庫中，找到包含用戶搜索內容的所有相關網頁。

1.3 對搜索結果進行排序

在網站自己的索引庫中，對網頁的每個關鍵詞都有記載，根據關鍵詞的搜索次數以及在網頁中出現的次數等分析要素，對搜索到的結果進行排序，也可以自己定義排序處理程序。最后將處理好的結果展現出來。

2 技 術

下面對于全文搜索中的主要幾種技術，加以分析探討，以便為全文搜索的技術實現提供某種思路。

2.1 中文分詞技術

英文是以詞為單位的，詞與詞之間上靠空格隔開，而中文是以字為單位，句子中所有的字連起來才能描述一個意思。例如，英文句子I am Chinese，翻譯成“我是中國人”。計算機可以很簡單的通過空格知道Chinese是一個單詞，但是不能很明白“中”、“國”兩個字合起來才表示一個詞。把中文的漢字序列切分成有意義的詞，就是中文分詞。現有的分詞算法有3種:基于字符串匹配的分詞算法、基于理解的分詞算法和基于統計的分詞算法。本文不對此一一分析，請讀者自行查閱相關文獻。

2.2 排序技術

排序技術類似于曝光率，誰出現的次數最多，誰排在前面。在互聯網上，鏈接就相當于“曝光”，在B網頁中鏈接了A，相當于在談話中提到了A，如果在C、D、E、F中都鏈接了A，那么說明A網頁是最重要的，A便會排在最前面。另外還有HillTop算法等。

2.3 網絡蜘蛛

網絡蜘蛛即Web Spider，是一種很形象的網頁搜索技術。把互聯網比喻成一個蜘蛛網，那么Spider就是網上爬來爬去的蜘蛛。網絡蜘蛛是通過網頁的鏈接地址來尋找網頁，從網站某一個頁面(通常是首頁)開始，讀取網頁的內容，找到在網頁中的其他鏈接地址，然后通過這些鏈接地址尋找下一個網頁，這樣一直循環下去，直到把這個網站所有的網頁都抓取完為止。如果把整個互聯網當成一個網站，那么網絡蜘蛛就可以用這個原理把互聯網上所有的網頁都抓取下來。在抓取網頁的時候，網絡蜘蛛一般有兩種算法:廣度優先和深度優先。廣度優先是指網絡蜘蛛會先抓取起始網頁中鏈接的所有的網頁，然后再選擇其中的一個鏈接網頁，繼續抓取在此網頁中鏈接的所有網頁。這是最常用的方式，因為這個方法可以讓網絡蜘蛛并行處理，提高其抓取速度。深度優先是指網絡蜘蛛會從起始頁開始，一個鏈接一個鏈接跟蹤下去，處理完這條線路之后再轉入下一個起始頁，繼續跟蹤鏈接。這個方法的優點是比較容易設計。

3 實 現

建立全文索引中有兩項非常重要:一個是如何對文本進行分詞;一個是建立索引的數據結構。

3.1 如何分詞

分詞的好壞關系到查詢的準確程度和生成索引的大小。在中文分詞發展中，早期經常使用分詞方式是二元分詞法，該方法的基本原理是將包含中文的句子進行二元分割，不考慮單詞含義，只對二元單詞進行索引。因此該方法所分出的單詞數量較多，從而產生的索引數量巨大，查詢中會將無用的數據檢索出來，好處是算法簡單不會漏掉檢索的數據。之后又發展出最大匹配分詞方法，該方法又分為正向最大分詞和逆向最大分詞。其原理和查字典類似，對常用單詞生成一個詞典，分析句子的過程中最大的匹配字典中的單詞，從而將句子拆分為有意義的單詞鏈。最大匹配法中正向分詞方法對偏正式詞語的分辨容易產生錯誤，比如“首飾和服裝”會將“和服”作為單詞分出。本文實現的是逆向最大分詞方法，該分詞方法較正向正確率有所提高。最為復雜的是通過統計方式進行分詞的方法。該方法采用隱式馬爾科夫鏈，也就是后一個單詞出現的概率依靠于前一個單詞出現的概率，最后統計所有單詞出現的概率的最大為分詞的依據。這個方法對新名詞和地名的識別要遠遠高于最大匹配法，準確度隨著取樣文本的數量的增大而提高。二元分詞方法和統計方法是不依賴于詞典的，而最大匹配法分詞方法是依賴于詞典的，詞典的內容決定分詞結構的好壞。

3.2 索引的結構

索引的數據結構基本上采用倒排索引的結構。全文檢索的索引被稱為倒排索引，之所以稱為倒排索引，是因為將每一個單詞作為索引項，根據該索引項查找包含該單詞的文本。因此，索引都是單詞和惟一記錄文本的標識是一對多的關系。將索引單詞排序，根據排序后的單詞定位包含該單詞的文本。

3.3 逆向最大分詞算法

逆向最大分詞的實現算法說明:

(1)讀取一整條句子到變量str中，轉到(2);

(2)從句子的尾端讀取1個字到變量word中，轉到(3);

(3)在字典查找word中保存的單詞。如果存在則保存word，轉到(4)，否則轉到(5);

(4)如果是字典中最大單詞或者超過最大單詞數(認定為新詞)，從句尾去掉該單詞，返回(2);

(5)讀取前一個字到word中，構成新單詞，轉到(3)。

假設字典中有如下的單詞:

中國

中華民國

國家

人民

民主

在內存中按照如下方式按層排列:其中每一個方塊代表一個字，箭頭所指向為該單詞的前一個字。

那么，如查找單詞“中華民國”:(1)首先在第一層中使用二分法找到“國”字，獲得“國”下層的數組“中民”;(2)在該層使用二分法查找“民”，獲得“民”下層的數組“華”;(3)在該層使用二分法查找“華”，獲得“華”下層的數組“中”;(4)最后在該層找到“中”，至此匹配完畢。

3.4 索引的格式

索引的格式是倒排索引的格式，也就是一個單詞對應若干個文本表示。比如，建立全文索引的對象是rec中的字段，生成倒排索引使用數據庫中的b樹進行存儲。在數據庫是對某個字符字段進行全文索引，因此，rec的rowid作為該rec上該field的標示是必須要被記錄的。因此倒排索引存儲的格式如下:

字段1字段2單詞1Rowid1，rowid2…單詞1 Rowid1，rowid2………字段1字段2字段3單詞1單詞1Rowid的格數Rowid1，rowid2…單詞1單詞2Rowid的格數Rowid1，rowid2…………

3.5 全文索引的查詢

全文的索引查詢首先將對要查詢的單詞進行分詞，然后在存儲倒排索引的b樹中將包含這些單詞的rowid全部查找出來，并根據這些rowid在存儲實際數據的b樹中，將包含這些數據的行過濾出來。

4 結 論

本文簡單地介紹了全文檢索技術的基本概念、原理和相關技術，并給出了逆向最大分詞技術的具體實現。隨著搜索引擎市場空間越來越大，搜索引擎也分得越來越細，搜索需求不可能都一樣，搜索引擎會不斷細化，各具特色的搜索引擎也陸續出現。本文中的所實現的技術，在這些不同的應用領域中，都將會有一定的使用價值。

參考文獻

[1]李盛韜.基于主題的Web信息采集技術研究[D].中國科學院計算技術研究所碩士畢業論文，2002.

[2]許洪波.大規模信息過濾技術研究及其在Web問答系統中的應用[D].中國科學院計算技術研究所博士畢業論文，2003.

[3]譚建龍.串匹配算法及其在網絡內容分析中的應用[D].中國科學院計算技術研究所博士畢業論文，2003.

[4]Winter.中文搜索引擎技術揭密:系統架構[EB].中文全文檢索網，2004.

[5]Lawrence S，Giles C L.Searching the world wide web[J].Science，1998，280(4).

[6]http:∥www.bhasha.com[EB].2007.5.

[7]Hendler J.Agents and the Semantic Web.IEEE Intelligent Systems，2001-03-04.

[8]T Berners Lee.J Handler.O Lassila，The Semantic Web.Scientific America，May 2001:219.

[9]Cardie C.Empirical methods in information extraction.AI Magazine，1997，18(4).

[10]HSUC N，DUNG M.Generating finite-state transducers for semi-structured data extraction from the Web[J].Information System，1998，23(8):521-538.