自動答疑系統(tǒng)知識庫文本的索引研究

摘要:該文從傳統(tǒng)的基于FAQ庫自動答疑系統(tǒng)的知識庫存儲及檢索方式的不足出發(fā)，提出了知識庫文檔預(yù)處理及建立倒排索引結(jié)構(gòu)的方法。對倒排索引文檔進行重組及性能進行優(yōu)化，初始化了文檔的權(quán)重，提高了文檔內(nèi)容的檢索速度。

關(guān)鍵詞:知識庫;倒排索引;答疑系統(tǒng);權(quán)重

中圖法分類號:TP301.6文獻標識碼:A文章編號:1009-3044(2009)35-10100-02

Research of Text Index in Automatic Question-Answering System

NING Ke-wei

(Xinjiang Normal University Institute of Educational Science， Urumqi 830054， China)

Abstract: From the disadvantages of the traditional knowledge saving and seaching ways based on FAQ database，this paper provide the methods about the pretreatment of knowledge database documents and the structural establishment of inverted index. Reorganizing files of inverted index and optimizing their capabilities，and initializing the weight of document，then enhance searching speed of the contents of documents.

Key words: knowledge database; inverted index; question answering system; weight

在一般基于FQA庫自動答疑系統(tǒng)中，其問題庫對應(yīng)的答案基本來源WEB或者通過關(guān)系數(shù)據(jù)庫存儲在本地硬盤中.在系統(tǒng)運行過程中，用戶經(jīng)常問的問題、正確率高的答案被保存在FQA庫做為答案直接返回給用戶，另外在針某門學(xué)科答疑系統(tǒng)中管理員有時也把與某學(xué)科相關(guān)的資料做常識知識存儲起來形成知識庫提高答案的準確率。這樣知識庫中就存在上千萬條數(shù)據(jù)，如果是單純的數(shù)據(jù)庫查詢，如此大數(shù)據(jù)量對查詢效率的影響不會太大，但是在答疑系統(tǒng)中，在檢索時要進行問句的相似度計算，如果知識庫每個問句都要和待查問句進行計算，那么查詢時間就是非?？捎^的。如此巨大的知識庫文本如何存儲，并且如何在幾秒內(nèi)返回搜索結(jié)果確實是一項挑戰(zhàn)?；谝陨戏治觯鹨上到y(tǒng)中的知識庫不能簡單是數(shù)據(jù)庫中幾張表，而是一個復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，本文根據(jù)自動答疑系統(tǒng)的檢索特性提出一個良好的數(shù)據(jù)存儲結(jié)構(gòu)——索引，并對現(xiàn)有答疑系統(tǒng)的索引進行重組和優(yōu)化，大大提高了系統(tǒng)的檢索效率。

1 知識庫的索引

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

2 知識庫索引的優(yōu)化

2.1 索引文件的合并

對答疑系統(tǒng)的巨型知識庫建立索引時若將信息存儲一個索引文件中會超過操作系統(tǒng)限制單個文件最大容量上限。鑒于這種情況，本文在建立索引時一般將索引文件分若干文件。如果索引文件的個數(shù)無限增加，必然帶來一些磁盤I/O的負擔(dān)，當檢索系統(tǒng)檢索一個關(guān)鍵詞時，其相關(guān)的文檔分布大量不同的索引文件，要獲得相關(guān)文檔內(nèi)容則需要打開每一個索引文件，并將其加載。如果此時的索引文件有成千上萬個，那么對于系統(tǒng)的資源消耗是致命的。因此需要對索引文件數(shù)量進行一個控制，將小的索引文件合并成一個或幾個大的索引的文件，以此來提高檢索效率。進行索引文件合并時其原理是將所有小文件全部讀入內(nèi)存，在內(nèi)存中進行整合，然后將內(nèi)存中的數(shù)據(jù)全部寫到一個新的大文件，大文件生成后將原來小文件刪除。其合并過程如圖1所示。

2.2 提高文件掃描性能

在建立索引的時候，系統(tǒng)需要頻繁地訪問文件，就不停地執(zhí)行“文件打開”“文件讀取”，“文件關(guān)閉”這就需要考慮到提升I/O性能。通常我們用系統(tǒng)開發(fā)語言所提供的標準文件操作函數(shù)對索引文件進行操作，其實操作系統(tǒng)本身也提供這些文件操作的函數(shù)如pen()，read()，write()。例如一個文件通過C函數(shù)的fopen()打開，其數(shù)據(jù)傳輸?shù)穆窂脚c被open()這個系統(tǒng)調(diào)用函數(shù)打開是不一樣的，當使用fopen()打開文件時，數(shù)據(jù)首先從用戶數(shù)據(jù)空間移動到函數(shù)緩沖區(qū)間，然后隨著數(shù)據(jù)在函數(shù)庫中的移入移出，才移動底層的系統(tǒng)中，如果使用系統(tǒng)調(diào)用函數(shù)open()，文件操作可以饒過函數(shù)緩沖區(qū)間，數(shù)據(jù)直接從用戶數(shù)據(jù)空間轉(zhuǎn)移到系統(tǒng)底層。索引系統(tǒng)請求的文件大小由讀或者寫的系統(tǒng)調(diào)用決定。當請求的數(shù)據(jù)能被直接I/O(Direct I/O)操作則數(shù)據(jù)從用戶數(shù)據(jù)空間直接移動設(shè)備，就可以節(jié)省管理大量的緩存帶來的系統(tǒng)開銷，否則系統(tǒng)調(diào)用函數(shù)能基于系統(tǒng)的修正的邊界來創(chuàng)建數(shù)據(jù)緩沖區(qū)來實現(xiàn)I/O操作。文獻[2]提出了一種使用操作系統(tǒng)的系統(tǒng)調(diào)用函數(shù)替代程序開發(fā)語言所提供的標準文件操作函數(shù)的方法，并且證明這種方法確實有很好的性能。

2.3 索引文件的壓縮

當知識庫文檔數(shù)量很大時，索引庫的容量會變得很大，占用的空間有時會超過源文檔的占用空間。采用一定的壓縮策略可以節(jié)約存儲空間，另外檢索系統(tǒng)執(zhí)行檢索需要讀取一定的索引數(shù)據(jù)，采用壓縮技術(shù)可以減少讀取數(shù)據(jù)所需的I/O時間，從而提高檢索速度。根據(jù)上節(jié)所提到倒排文檔結(jié)構(gòu)特點，在IX文件中的詞匯表及文本號向量，IF文件中的索引詞的位置信息占兩個文件體積比重較大，有必對其進行壓縮。本文著重從以下幾個方面進行倒排文檔壓縮。

2.3.1 索引詞的壓縮

在IX文件中詞匯已按照字典升序排列的，詞之間前綴出現(xiàn)了大量的冗余。所以本文采用兩種壓縮方法，前方壓縮，后方壓縮。其作法是將詞匯表調(diào)入升序隊列，每個關(guān)鍵詞后的詞逐一與前一詞進行比較，前方一致部分不再重復(fù)存貯，只在該詞前面標上與前一詞的重復(fù)的字符數(shù)。采用前方壓縮處理后(如表1所示)。

為了更有效地對數(shù)據(jù)進行壓縮，可同時采用前方壓縮和后壓縮(Rear-read Compression)，后方壓縮的原理跟前方壓縮是一樣的，只是字之間比較方向是相反，這里就不贅述。通常索引詞表規(guī)模越大，壓縮的效果越好，其存儲空間可壓縮66%左右[3]。

2.3.2 文本號向量的壓縮

本文通過添加文本號向量策略來提高獲取文檔集合的速度，IX中需要存儲大規(guī)模的文本號向量數(shù)據(jù)，其在IX中占了大量空間。從時間效率來看，由于縮小文本查找范圍的速度與索引數(shù)和文本號向量的長度成正比，所以通過壓縮文本號向量提高查找數(shù)速度。根據(jù)文本向量特性，通過“多階段壓縮法”[1]來壓縮稀疏的文本號向量，其作法是將長度為N的文本號向量初始設(shè)定級別為1稱為1級文本號向量，把1級的文本號向量按給定的一個分隔單位D位進行分割，級別數(shù)據(jù)從原來級別上加1，分割的向量為塊向量，把前一級別的d個塊壓縮為由d個bit組成的1個塊。其中前一級別的各個塊內(nèi)的bit值如果都是0，壓縮bit的值為0，在塊內(nèi)有1壓縮bit的值為1。對于前一級別的所有塊一直重復(fù)操作。直分解到Int(Logd(n-1))級為止。例如:把N=64的文本號向量壓縮成N=4的過程，其中分割單位=4，Int(Log4(64-1))=3，通過以上壓縮過程能大大縮小IX的體積，保證倒排索引的檢索速度。

2.3.3 索引詞的位置信息的壓縮

索引詞的位置信息在IF(倒排文件)占較大的比重。對文檔的掃描處理是順序進行的，字符出現(xiàn)的位置必然是按升序排列的。根據(jù)這一特點，可以對位置序列進行壓縮，首先采取差值編碼的思想，減小數(shù)值的范圍。例如:關(guān)鍵詞A出現(xiàn)在某文檔的位置為22，65，120，180，經(jīng)過差值編碼轉(zhuǎn)換為22，43，55，60后數(shù)值降低了很多。但每個數(shù)字仍然用4個字節(jié)來是極大的浪費。對變換后的數(shù)列采用“均勻變長編碼”方式將差值進一步采用短的長度表示，減少數(shù)字占用的存儲空間。其方法是設(shè)計一種整數(shù)變長編碼，將雙字的低字節(jié)的最低2位作為數(shù)值字節(jié)長度標志位。除了2位作為標志位，字節(jié)其它位都用來保存數(shù)據(jù)。比如數(shù)值120，用二進制表示為11110000，壓縮編碼后的二進制表示為 00000011 11000001，可以看出大部分的增量數(shù)值只需1-2個字節(jié)表示，而無需再用4字節(jié)，節(jié)省了大量空間。

3 結(jié)束語

通常的FAQ的知識庫存儲是采用數(shù)據(jù)庫來存放，知識庫的大小直接影響了結(jié)果的好壞。一般一個專業(yè)的FAQ都有上百萬的記錄，如此大數(shù)據(jù)量對查詢效率的影響不會太大，但是在答疑系統(tǒng)中，在檢索時要進行問句的相似度計算，如果知識庫每個問句都要和待查問句進行計算，那么查詢時間就是非常可觀的。如此巨大的知識庫文本如何存儲，并且如何在幾秒內(nèi)返回搜索結(jié)果確實是一項挑戰(zhàn)。本文根據(jù)自動答疑系統(tǒng)的檢索特性提出一個良好的數(shù)據(jù)存儲結(jié)構(gòu)——索引，并對現(xiàn)有答疑系統(tǒng)的索引進行重組和優(yōu)化，大大提高了系統(tǒng)的檢索效率。

參考文獻:

[1] 張帆.信息存儲與檢索[M].北京:高等教育出版社，2007.

[2] 周寧.情報數(shù)據(jù)庫系統(tǒng)[M].武漢:武漢大學(xué)出版社，1988.

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

[4] 趙金海.基于Web的自動答疑技術(shù)研究及系統(tǒng)實現(xiàn)[D].重慶:重慶大學(xué)，2007.

[5] 趙會杰.中文全文檢索系統(tǒng)中索引的研究[D].北京:北京交通大學(xué)，2006.

[6] Newman H.Application Performance and I/O[Z].2001.