基于倒排索引的答疑系統知識庫文本研究

寧可為，王 煒

（新疆師范大學 教育科學學院，新疆 烏魯木齊 830054）

基于倒排索引的答疑系統知識庫文本研究

寧可為，王 煒

（新疆師范大學 教育科學學院，新疆 烏魯木齊 830054）

通過對自動答疑系統的知識庫存儲及檢索方式進行分析，提出了以倒排索引方式對答疑系統知識庫文本進行重構，實現了知識庫文本預處理和建立倒排索引功能，該系統的建立提高了文本內容的檢索的準確率和查全率，使用戶獲得更好的體驗。

知識庫；倒排索引；文本；答疑系統

一、引言

在面向某學科的自動答疑系統中，我們把一些常用知識點（概念）作為的答疑系統中問句答案進行存儲，而學科分類中，有幾十個學科，每個學科至少有幾十門課程，每門課程中至少有若干個知識點，而每個知識點又對應若干個問句答案。這樣，知識庫中的知識（問句答案）中就存在上千萬條數據。知識庫組織關系到知識查詢的效率及用戶的體驗，如果單純的數據庫查詢，在海量知識文本中查找用戶所需的問句答案其查詢時間是非?？捎^的。如此巨大的知識庫文本如何存儲，并且如何在幾秒內返回搜索結果確實是一項挑戰。基于以上分析，答疑系統中的知識庫不能簡單是數據庫中幾張表，而是一個復雜的數據結構，本文根據自動答疑系統的檢索特性提出一個良好的數據存儲結構——索引，極大地提高了系統的檢索效率。

二、知識庫文本的預處理

1.文本的歸一處理

答疑系統與搜索引擎的功能有一定區別，也導致處理文檔也有不同區別。根據答疑系統檢索的特點，一般一個問題對一個文檔中的某一段進行搜索，抽取其中的答案返回給用戶，用戶也不必瀏覽知識庫源文檔。因此對于大文檔必須以一個固定的量為單位及以段落為分割點切分為多個小較少的文檔，并以統一的.txt文件進行存儲。檢索時面對統一格式文檔能提高文檔的加載及檢索速度。

2.索引關鍵詞提取

在信息檢索中，常常用文本中含有一些關鍵詞代表了語句的主體含義，在建立索引時文本中的關鍵詞是索引項一部分，因此，從文本中提取索引項就是從給定文本的連續字符中找出完整的單詞。英語，法語等語言詞與詞有天然的分隔符空格，單詞確定較為容易，對于漢語要在句子中確定單詞就極為困難，為了能正確提取單詞一般先對句子進行詞法分析并采用基于詞庫和 N元組為索引單位的混合方式切分出索引關鍵詞?，F在流行的分詞系統如中科院的ICTCLAS分詞系統及JE分詞系統，本文采用的是ICTCLAS分詞，它能高效地在句子切分出單詞，“分詞正確率高達97.58%”[1]。根據分詞系統可以把整編文檔切分成一個個離散的單詞，但并不是所有單詞都可以作為關鍵詞，還應該對單詞集進行過濾去掉無用詞。

根據自然語言詞性特征將單詞分為內容詞（Content word）功能詞（Function word）兩類[2]。其中內容詞表示某個特定的概念的詞。如漢語中的名詞，動詞等。功能詞表示詞與詞之間的關系，如漢語中的助詞，連詞，語氣詞等等。經過大量統計發現它們頻繁出現在文本中，其表義值非常低，選擇索引詞條時應該被過濾掉。去停用詞方法是把無用詞構建成一張停用詞表（stop list），凡是這張表中出現的詞都將被過濾掉。

三、知識庫的索引

對知識庫文本建立索引方式常用的有 3種，分別是倒排，后綴數組和簽名文件。倒排索引被當前主流搜索引擎所廣泛使用，它對關鍵詞的檢索非常有效。在倒排索引中，無論多大數量的文本數據庫，總能夠規范出一個關鍵詞表，所有關鍵詞的數量不會隨文本內容的增長而線性增長。據統計對于1GB的文本信息，倒排文檔的關鍵詞表的大小在5MB左右[3]。由于倒排文檔的組成特點，使得許多數學檢索模型（如布爾模型，集合運算等）能夠方便地用于信息檢索中。因此本文采用倒排索引結構。

1.倒排索引結構

本文將知識庫索引結構如圖 1所示，具體分如下幾部分：主文件索引MX（Master File Index），主要為知識庫源文檔提供一個順排文件。MX結構：文檔號，文檔分值，地址指針。其中文檔號是對應知識庫源文檔的編號，可通過折半找查定位到該源文件，分值是根據文檔激勵因子及長度因子計算出的文檔得分。

圖1 索引結構

倒排文件索引IX（Inverted File Index）保存關鍵詞和其文檔集合之間關系映射，能快速找出要檢索的關鍵詞所在的文檔號集合。IX結構：關鍵詞序列，目長（含有該關鍵詞的記錄的條數），文本號向量，IF地址指針。本文新增“文本號向量”元素取代傳統倒排文件的“記錄號集合”[4]元素，文本號向量從左邊第一位起對應該著所有文檔號。通常，計算包括兩個查詢詞的文檔集合的交集時間復雜度為 O（m*n），通過文本號向量計算其交集時間復雜度為O（1）。檢索系統給出復數個查詢詞時，僅需要進行文本號向量間的邏輯運算能就高速檢索出所有關鍵詞共同所對應的文檔號。

倒排文件IF（Inverted file）為降低IX文件所占用的內存容量把IX中與關鍵詞相關的文檔號及關鍵詞相關信息轉存到IF中。IF結構：文檔號，位置信息。其中位置信息是關鍵詞在本文檔中出的位置。

專用詞表RT（Related Terms）是為面向特定領域的答疑系統設計的詞表。RT的構成以IX為基礎，加入詞間關系的指針，幫助用戶選準主題詞，擴大檢索途徑，提高查全率與查準率。

2.倒排索引的建立

建立倒排索引就如同寫一本書的目錄一樣，目錄是章節標題對應頁碼，對全文搜索來講，倒排索引就是詞對應該文檔編號。通過分詞后普通文檔的存在形式為：

Doc1 KeyWord1，KeyWord2，KeyWord4，KeyWord5（形式1 ）

Doc2 KeyWord1，KeyWord2，KeyWord3

Doc3 KeyWord1，KeyWord4

Doc4 KeyWord3，KeyWord4

Doc5 KeyWord3，KeyWord5

建立倒排索引就是將此過程翻轉過來，如下：

keyWord1，keyWord2，KeyWord4，KeyWord5 Doc1（形式2）

KeyWord5，KeyWord3 Doc5

在知識庫建索引時，把形式 1轉化形式 2并且把KeyWord 與Doc 進行歸并，消去重復的DocID，計算出每個文檔的得分和關鍵詞出現在文檔的位置信息以升序方式排列存儲，并將文本號向量代替文檔號消去文檔號（如表1所示）。

表1 歸并后的索引

文檔集合列中數字表示KeyWrod在文檔中的出現的位置，并按出位置升序排列。Doc（i）不存儲在文件中。實際應用中對KeyWord進行排序并對其進行折半查找可以提高關鍵詞的檢索速度并能達到高速的數據插入。

當知識庫有大量數據時，倒排表會變得非常龐大，為了提高檢索速度檢索系統必須將倒排表載入內存，就可能導致內存溢出，系統的性能瞬間降到為零。本文采取一種倒排索引重組的方法，拿關鍵詞部分到內存中的詞典項中過行Hash查找，將倒排索引（IX）的右部存在倒排文件（IF）中，并將原先的右部改成在IF文件中的偏移地址，形成對應的指針項讀取指定的文件中倒排表。例如：

K1 （18），（13），（24;40），11100

K2 （11），（6）， 11000

經過處理在內存中的倒排表便為以下形式

K1 File1，3，StartPos1，Len1，11100

K2 File1，2，StartPos+Len1，Len2，11000

File1∶ （18），（13），（24;40）， （11），（6）

上面File1是指倒排文件（IF） 的文件名，StartPos 是指倒排表右部在索引文件中的偏移位置，Len是指倒排表右部在索引文件中的長度。

另外為了提高檢索速度，在建立索引時把知識庫中的源文檔信息以記錄形式按升序編號形成主鍵 DocID存儲存在 MX文件中。當檢索系統通過文本向量號邏輯運算后會得關鍵詞所屬的DOC的集合{doc1，doc2，…}，我們要找原始文檔，只要通過對MX進行折半查找便可得出DOC的集合所對應的原文檔信息。

3.文檔的分值（score）計算

當檢索系統對用戶所提的問題進入一次預查找時，可能返回一系列與關鍵詞相關文檔，要做到檢索的結果精確，降低答案相似度計算量，應該優先將與問題最相關的文本優先送出，然后與優先送出的文檔集合進行相似度計算。本文對檢索到的文本增加一個分值屬性（文檔分值），根據分值進行排序，文檔的得分越高，就與用戶所提的問題越接近。分值一部分由檢索時根據關鍵詞的“詞條頻率 TF（Term Frequency）*反轉文檔頻率 IDF（Inversed Document Frequency）公式”[2]臨時計算得出，另一部分由如下兩個因子得出并存儲在MX文件中。

（1）文檔的長度因子

計算公式：1.0/SQR（numTerms）其中numTerms為單個文檔詞條總數。文檔集合中一般含有長短不同的文本，長文本會出現同一個索引項被反復使用的傾向，且長文本中的索引項的種類也多，與查詢出現的索引項相同的機會相應增加，這就使長文本的索引項有較大的權重，長文本與短文本相比長文本被檢索的概率要高。為了消除文本長度帶來的影響，本文采用計算文檔的長度因子方式降低長文本的分值來達到最后文檔得分的平衡。當被索引的文檔中的詞條數量越多，則其長度因子就越小。

（2）激勵因子（boost） 在對某文檔進行索引時，知識庫構建者想人為增加某個文檔相關度，使其在搜索結果中排在更靠前的位置上，可以通過增加boost值，其值越大其相關度越大，就越接近用戶所提的問題。

四、結束語

自動答疑系統中進行問句答疑就是以毫秒級的速度對海量知識庫文本進行關鍵字匹配找出得分最高的文本序列，然后根據用戶問句與文本序列進行語義相似度計算得出最終結果。對于擁有海量數據的知識庫來講，知識庫文本存儲結構的優劣直接影響查詢效率，實踐證明對其知識文本采用倒排索引結構進行索引存儲能極大地提高數據檢索速度。

[1] 張輝麗. 計算機鄰域中文自動問答系統的研究[D].天津大學，2006.

[2] 邰曉英.信息檢索技術[M].科學出版社，2006.

[3] 邱哲，符滔滔.開發自己的搜索引擎――Lucene2.0+ Heritrix[M].人民郵電出版社，2007.

[4] 袁津生，趙傳剛.搜索引擎與信息檢索教程[M].中國水利水電出版社，2008.

[5] 盧亮，張博文.搜索引擎原理實踐與應用[M].電子工業出版社，2007.

[6] 蘇新寧.信息檢索理論與技術[M].科學技術文獻出版社，2004.

Research of Knowledge Database Document of Question Answering System based on the Inverted Index

NING Ke-wei，WANG Wei

The present study, by means of the analysis of Knowledge Database Document of Question Answering System （KDDQAS for short） and the Inverted Index, proposes the way of applying the Inverted Index to reconstruct the texts of KDDAQS, and then achieve the pre-management of knowledge database and the function of Inverted Index. The construction of this system can enhance the accuracy of query and the full use when indexing texts. Users on this occasion can have a better experience than before.

Knowledge database, Inverted index, Document, Question Answering System

G254.36

A

1008-7427（2010）06-0148-02

2010-04-02

新疆師范大學研究生科技創新項目基金，項目編號：20091106。