基于倒排索引的答疑系統(tǒng)知識庫文本研究

寧可為，王 煒

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

基于倒排索引的答疑系統(tǒng)知識庫文本研究

寧可為，王 煒

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

通過對自動答疑系統(tǒng)的知識庫存儲及檢索方式進(jìn)行分析，提出了以倒排索引方式對答疑系統(tǒng)知識庫文本進(jìn)行重構(gòu)，實(shí)現(xiàn)了知識庫文本預(yù)處理和建立倒排索引功能，該系統(tǒng)的建立提高了文本內(nèi)容的檢索的準(zhǔn)確率和查全率，使用戶獲得更好的體驗(yàn)。

知識庫；倒排索引；文本；答疑系統(tǒng)

一、引言

在面向某學(xué)科的自動答疑系統(tǒng)中，我們把一些常用知識點(diǎn)（概念）作為的答疑系統(tǒng)中問句答案進(jìn)行存儲，而學(xué)科分類中，有幾十個學(xué)科，每個學(xué)科至少有幾十門課程，每門課程中至少有若干個知識點(diǎn)，而每個知識點(diǎn)又對應(yīng)若干個問句答案。這樣，知識庫中的知識（問句答案）中就存在上千萬條數(shù)據(jù)。知識庫組織關(guān)系到知識查詢的效率及用戶的體驗(yàn)，如果單純的數(shù)據(jù)庫查詢，在海量知識文本中查找用戶所需的問句答案其查詢時間是非?？捎^的。如此巨大的知識庫文本如何存儲，并且如何在幾秒內(nèi)返回搜索結(jié)果確實(shí)是一項(xiàng)挑戰(zhàn)?；谝陨戏治觯鹨上到y(tǒng)中的知識庫不能簡單是數(shù)據(jù)庫中幾張表，而是一個復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，本文根據(jù)自動答疑系統(tǒng)的檢索特性提出一個良好的數(shù)據(jù)存儲結(jié)構(gòu)——索引，極大地提高了系統(tǒng)的檢索效率。

二、知識庫文本的預(yù)處理

1.文本的歸一處理

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

2.索引關(guān)鍵詞提取

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

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

三、知識庫的索引

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

1.倒排索引結(jié)構(gòu)

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

圖1 索引結(jié)構(gòu)

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

倒排文件IF（Inverted file）為降低IX文件所占用的內(nèi)存容量把IX中與關(guān)鍵詞相關(guān)的文檔號及關(guān)鍵詞相關(guān)信息轉(zhuǎn)存到IF中。IF結(jié)構(gòu)：文檔號，位置信息。其中位置信息是關(guān)鍵詞在本文檔中出的位置。

專用詞表RT（Related Terms）是為面向特定領(lǐng)域的答疑系統(tǒng)設(shè)計的詞表。RT的構(gòu)成以IX為基礎(chǔ)，加入詞間關(guān)系的指針，幫助用戶選準(zhǔn)主題詞，擴(kuò)大檢索途徑，提高查全率與查準(zhǔn)率。

2.倒排索引的建立

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

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

Doc2 KeyWord1，KeyWord2，KeyWord3

Doc3 KeyWord1，KeyWord4

Doc4 KeyWord3，KeyWord4

Doc5 KeyWord3，KeyWord5

建立倒排索引就是將此過程翻轉(zhuǎn)過來，如下：

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

KeyWord5，KeyWord3 Doc5

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

表1 歸并后的索引

文檔集合列中數(shù)字表示KeyWrod在文檔中的出現(xiàn)的位置，并按出位置升序排列。Doc（i）不存儲在文件中。實(shí)際應(yīng)用中對KeyWord進(jìn)行排序并對其進(jìn)行折半查找可以提高關(guān)鍵詞的檢索速度并能達(dá)到高速的數(shù)據(jù)插入。

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

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

K2 （11），（6）， 11000

經(jīng)過處理在內(nèi)存中的倒排表便為以下形式

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文件中。當(dāng)檢索系統(tǒng)通過文本向量號邏輯運(yùn)算后會得關(guān)鍵詞所屬的DOC的集合{doc1，doc2，…}，我們要找原始文檔，只要通過對MX進(jìn)行折半查找便可得出DOC的集合所對應(yīng)的原文檔信息。

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

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

（1）文檔的長度因子

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

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

四、結(jié)束語

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

[1] 張輝麗. 計算機(jī)鄰域中文自動問答系統(tǒng)的研究[D].天津大學(xué)，2006.

[2] 邰曉英.信息檢索技術(shù)[M].科學(xué)出版社，2006.

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

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

[5] 盧亮，張博文.搜索引擎原理實(shí)踐與應(yīng)用[M].電子工業(yè)出版社，2007.

[6] 蘇新寧.信息檢索理論與技術(shù)[M].科學(xué)技術(shù)文獻(xiàn)出版社，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

新疆師范大學(xué)研究生科技創(chuàng)新項(xiàng)目基金，項(xiàng)目編號：20091106。