多格式文檔搜索引擎索引系統設計與實現

方躍勝 董 輝 姚宏亮

(安徽水利水電職業技術學院電子系，安徽 合肥 231603) (亳州職業技術學院信息工程系，安徽 亳州 236800) (合肥工業大學計算機與信息學院，安徽 合肥 230009)

多格式文檔搜索引擎索引系統設計與實現

方躍勝 董 輝 姚宏亮

(安徽水利水電職業技術學院電子系，安徽 合肥 231603) (亳州職業技術學院信息工程系，安徽 亳州 236800) (合肥工業大學計算機與信息學院，安徽 合肥 230009)

隨著Internet和計算機的迅猛發展，搜索引擎應需而生，越來越多的企業利用計算機處理運營過程中產生的大量電子文檔。如何從這些網絡和多格式文檔資源中迅速、方便而準確地檢索出企業用戶所需的信息已成為越來越重要的問題。索引系統是搜索引擎的核心，為提高系統的查全率和查準率，設計了一種適用于文檔檢索的數據庫存儲的索引結構并建立索引庫來降低索引組織的復雜度，通過布爾邏輯和向量空間的組合模型實現對檢索結果排序，以返回最優文檔列表。該系統在Windows環境下采用PHP開發組件實現，能夠提高檢索文檔的查全率和查準率。

文檔搜索引擎；索引同步；檢索模型

隨著Internet和計算機的日益發展，搜索引擎已成為人們獲取海量網絡信息的主要工具。按照“快、全、準、穩”的評測標準，目前的許多搜索引擎已經不能滿足人們的需求［1］。此外，越來越多的企業開始利用計算機處理企業的運營過程中產生的大量電子文檔。如何從網絡和多格式的文檔資源中迅速準確地檢索出企業用戶所需的信息已成為越來越重要的問題。因此，開發快速準確和智能化的搜索引擎是目前的研究熱點，而搜索引擎設計中的重要工作是建立索引系統，其目的是能夠快速地響應用戶的查詢。為此，筆者對多格式文檔搜索引擎的索引系統進行了研究。

1 索引構建

1.1索引數據庫設計

圖1 倒排表結構

1)文檔表 文檔表包含文檔編號(File_ID)和文檔名稱(File_Val)2個字段。

2)關鍵詞表 關鍵詞表包含關鍵詞編號(KeyWord_ID)和關鍵詞(KeyWord_Val)2個字段。

3)倒排表 倒排表是索引數據庫的核心部分，其結構如圖1所示。

1.2索引組織設計

1)倒排表存儲 針對倒排表存儲的問題，提出了以下3種設計方案：①直接將倒排表放入內存；②將倒排表存入硬盤上的文件；③將倒排表及必要的文件存入數據庫(此處使用MySQL)。由于數據量很大，綜合考慮各個方面的算法，決定采用方案③，同時在具體實現過程中，對二維數組采用分組的方法來實現對索引文件的存儲。使用數據庫來代替文件流，可使插入、刪除、查詢等操作更加方便、高效。

在具體實現倒排表存儲時基于以下思想［2］：建立多個數據表，其中每個表有2001個字段，每篇文檔作為一個數據插入，其中第一個字段作為文檔編號，后面所有的數據以0作為標志，為0則該文檔不含有對應的詞，否則含有。數據庫中的倒排表有多個數據表組成，具體設計時應注重以下幾個方面：①表與表之間的聯系。將所有的文檔都作為數據量插入表中，各個表唯一的不同是關鍵詞編號，因而可將2000作為一個單位標志分別將表命名為Inverted_0、Inverted_1、…，使得各個表互相聯系。②處理文檔與關鍵詞在數據庫中的存儲方式。對于文檔，在存儲的時候直接存儲其在服務器中的位置信息，以數據庫自動為其添加的ID作為主鍵；對于關鍵詞，使用ID和關鍵詞本身來存儲關鍵詞。③對文檔和關鍵詞的插入和刪除的處理。對關鍵詞的插入和刪除就是對字段的插入和刪除處理，而對文檔的插入和刪除即為對數據的插入和刪除處理。

2)建立關鍵詞表 建立關鍵詞表的流程如圖2所示。

圖2 建立關鍵詞表流程圖

3)插入關鍵詞 插入關鍵詞的步驟如下：①將所有的關鍵詞讀入數據庫；②將文檔插入文檔表，同時運用已經寫好的倒排算法將文檔插入上一步形成的空的倒排表；③在查找過程中首先讀取關鍵詞，查到其在關鍵詞表中的ID，然后在倒排表中讀取該詞的ID遍歷這一行，最終得到該詞所在文檔的編號。具體實現算法［3］：對于給定的關鍵詞，如果不為空，首先將關鍵詞插入關鍵詞表；判斷關鍵詞標志量flag_word 是否為“1”，若是則建立新的倒排表，否則進入下一步；將當前的關鍵詞插入當前的倒排表中的列屬性中，同時使關鍵詞標志量flag_word 加“1”；如果關鍵詞標志量flag_word越界，將關鍵詞標志量flag_word量置“1”，同時使倒排表標志量flag_table加“1”。

4)建立多個倒排表 建立多個倒排表的具體流程如圖3所示。

5)建立文檔表 建立一個文檔表，向其中添加文檔，同時在數據庫中形成了一些類似二維數組的多個倒排表。在向表中插入文檔的同時，對每一個文檔進行遍歷。

6)向倒排表插入數據 向倒排表中插入數據的流程如圖4所示。

圖3 建立多個倒排表流程圖 圖4 向倒排表中插入數據流程圖

1.3索引同步設計

1)關鍵詞同步 對所有的關鍵詞用ELFHash()函數［4］運算，計算出每個關鍵詞的散列碼。將相同散列碼的關鍵詞存在散列表的同一個位置，并記錄其所在文檔信息。在關鍵詞同步的存儲結構中建立了2個數組，其中1個用來存儲關鍵詞，另1個用來存儲與關鍵詞索引值相同的文檔編號，使其一一對應。在程序運行的過程可以直接通過array_search()函數［5］來查找到相應的關鍵詞及其對應的文檔信息。在程序運行的過程中，首先初始化關鍵詞數組并建立文檔類的數組并使其一一對應，然后遍歷所有的文檔并將關鍵詞所在文檔添加進入文檔類數組。在遍歷文檔時，得到該文檔分詞后的某一個關鍵詞，判斷關鍵詞所在文檔是否在文檔數組中的對應位置。若在其對應的位置則證明該文檔已經添加進入其對應位置，不再作任何處理；若不在其對應位置，則將其信息添加進文檔數組。同步流程圖如圖5所示。

2)文檔同步 對于文檔同步，應建立一個關鍵詞類的數組，用數組的下標作為文檔的編號，存儲關鍵詞在該文檔中出現的次數、位置等信息。在程序運行的過程中，對分詞后的關鍵詞數組進行遍歷得到某一個關鍵詞，然后判斷該關鍵詞是否在該篇文檔的關鍵詞數組中，如果在數組中就添加其位置信息，如果不在數組中則添加本關鍵詞及其位置信息進入關鍵詞數組中。

2 索引檢索

圖5 信息檢索組合模型

該系統采用基于詞索引的中文全文檢索，信息檢索模型采用布爾邏輯和向量空間的組合模型，設計思想如下(以法律文檔查詢為例)：①首先用布爾邏輯檢索模型將用戶查詢通過基于Memcached的動態四字雙向詞典機制的分詞系統切分成關鍵詞序列；②將這些關鍵詞組成布爾查詢語句；③利用數據庫查詢，到索引庫中取出包含這些關鍵詞的所有案例，并按照關鍵詞在每一個案例中出現的次數對所有的案例進行第1次排序，取出關鍵詞出現次數最高的前50個案例作為第2次排序的依據；④建立一個向量空間；⑤對上一步分出來的關鍵詞作為向量空間的特征表示集，形成1個N維向量，其中每1維作為1個特征；⑥對第1次排序中的前50個案例利用TFIDF公式［6］分別計算其與查詢的相關度；⑦根據相關度高低對這50個案例進行第2次排序，并與其它案例一起返回給用戶。組合信息檢索模型如圖5所示。該模型不僅能解決布爾邏輯檢索模型對查詢結果排序不準確的問題，而且能提供比向量空間模型更快的查找速度，滿足用戶對系統響應速度的要求，同時還可以降低系統運行成本。

3 系統實現

該系統在Windows環境下采用Apache+PHP+MySQL黃金搭檔來實現：類Inverted函數Create_DB()實現數據庫功能，Create_KeyWord_Table()函數實現初始的關鍵詞表功能，Create_File_Table()實現初始的文檔表功能，Create_InvertedTable($var)實現倒排表的功能，從而實現數據庫的初始化。當更新數據庫時，調用Insert_Dir()函數，將文件夾中所有文檔都輸入數據庫，文檔為經過分詞后的txt文件。函數Insert_Dir()首先將文件名插入file表，然后讀取文件將其中的詞插入關鍵詞表，同時更新倒排表內容，記錄關鍵詞在文檔中的出現次數與位置。檢索時，對輸入內容首先進行分詞和去停用詞處理，然后對數據庫中文檔運用綜合模型分析、計算以確定輸出。

4 結 語

隨著Internet和計算機的迅猛發展，許多企業利用計算機處理運營過程中產生的大量電子文檔。為了從網絡和多格式文檔資源中迅速準確地檢索出所需信息，設計了一種適用于文檔檢索的數據庫存儲的索引結構，通過建立索引庫來降低索引組織的復雜度，利用布爾邏輯和向量空間的組合模型對檢索結果排序并返回最優文檔列表，系統在Windows環境下采用PHP開發組件實現。實際運行表明，該系統能夠提高檢索文檔的查全率和查準率。

［1］鄭榕增，林世平. 基于Lucene的中文倒排索引技術的研究［J］.計算機技術與發展，2010(3)：55-56.

［2］楊安生.基于倒排表的中文全文檢索研究［J］.情報探索，2009(7)：77-80.

［3］陳海波.基于自動分詞的企業文檔搜索引擎設計與實現［D］.西安：西北工業大學，2007.

［4］肖麗.哈希查找中散列函數的運用［J］.技術與市場，2009，16(8)：18-19.

［5］曹衍龍，趙斯思.PHP網絡編程技術與實例［M］.北京：人民郵電出版社，2006.

［6］熊回香，夏立新.基于詞索引的中文全文檢索關鍵技術及其發展方向［J］.中國圖書館學報，2007，33(4)：47-51.

10.3969/j.issn.1673-1409(N).2012.07.038

TP391

A

1673-1409(2012)07-N111-03

2012-04-24

國家自然科學基金資助項目(60705015)。

方躍勝(1975-)，男，1999年大學畢業，講師，碩士生，現主要從事中文分詞與索引關鍵技術方面的教學與研究工作。

［編輯］ 李啟棟