基于自索引的ＤＢＦ壓縮查詢工具研究

(中國科學院 軟件研究所 a. 并行計算實驗室; b. 計算機科學國家重點實驗室， 北京 100190)



摘 要：

介紹了DBF表的文件格式和基于自索引的全文查詢算法FM-index。針對DBF文件同時包含二進制文件頭和純文本數據記錄的特點，以及對查詢結果的特定要求，擴充了現有的FM-index算法，使其支持對DBF文件的壓縮查詢。測試結果表明，雖然FM-index在壓縮/解壓時間上與WinRAR仍有一段差距，但是FM-index對壓縮查詢功能的支持大大提高了文件的查詢性能。

關鍵詞：全文索引; 數據庫表; 壓縮; 查詢

中圖分類號：TP311 文獻標志碼：A

文章編號：1001-3695(2009)02-0628-03



Self-index compressing and searching tool for DBF tables



LIU Sheng-feia，ZHANG Yun-quana，b，ZHANG Dia，b

(a. Laboratory of Parallel Computing， b.State Key Laboratory of Computer Science， Institute of Software， Chinese Academy of Sciences， Beijing 100190， China)



Abstract:Based on the discussion of DBF table format and FM-index algorithm， extended the compressing and searching functions of FM-index for DBF tables. Considering the featuresof DBF tables，developed a tool to search DBF tables on compressed status. Experimental data shows thatalthough the tool spends more time to compress and uncompress than WinRar， it can search DBF tables much more quickly.

Key words：full text index; DBF(database file) table; compress; search



0 引言

聯網審計業務經常要處理報送來的大量DBF壓縮數據，數據的解壓縮常常要耗費很多的時間和空間。如果解壓縮后才發現數據不符合要求，無疑浪費了審計人員寶貴的時間。因此，在壓縮狀態下支持DBF文件的查詢是很重要的。FM-index就是一種自索引的壓縮文本查詢方法，可以同時達到次線性的空間和時間復雜度。FM-index算法可以對純文本的數據建立索引，但是無法對二進制格式的DBF文件頭建立索引。此外，DBF文件查詢需要根據給定的pattern和字段名field，提取滿足字段field中包含pattern的數據記錄（即select records where [field] contains〈pattern〉）。但是，FM_index的查詢功能是對給定的pattern，輸出pattern在文本中的位置及其附近的若干字符。因此，現有的FM_index算法無法滿足DBF文件的壓縮查詢需求。

本文基于FM_index算法，將DBF文件拆分為文件頭和數據記錄兩個部分，僅對數據記錄部分建立索引。在此基礎上，對FM_index的查詢功能進行了擴充，使其能夠支持對DBF的壓縮查詢。

1 DBF文件格式

DBF是在dBASE和FoxPro中使用的數據庫文件[1]。DBF表文件包括一個文件頭和若干個數據記錄。其中，文件頭為二進制格式，數據記錄采用ASCII字符格式。文件頭由文件位置0開始。第一個數據記錄緊接在文件頭之后（連續的字節）。每條數據記錄由若干個字段子記錄組成。

文件頭定義了該表的結構和一些與表相關的其他信息；數據記錄包含了表中的實際文本內容。DBF文件頭的詳細格式如表1所示。

表1文件頭的詳細格式

偏移位置 內容

0表示文件的版本信息

1~3表示最近的更新日期

4~7表示文件中的記錄條數

8，9文件頭長度，單位為Byte

10，11表示每個數據記錄的長度（包括刪除標記），單位為Byte

12，13保留字節，用于以后添加新的說明性信息時使用，這里用0來填寫

14 表示未完成的操作

15 dBASE IV編密碼標記

16~27保留字節

28 表的標記

29 代碼頁標記

30，31保留字節，用于以后添加新的說明性信息時使用

32~m字段描述符，共n×32 Byte，n表示字段的個數，每個字段對應一個字段子記錄，該數據結構在表2中有詳細解釋

m+1文件頭終止符（0X0D）

字段描述符是文件頭中的一個重要的數據結構，它表示數據庫中各個字段子記錄的格式。字段描述符的具體格式如表2所示。

表2 DBF文件頭中字段描述符的詳細格式

偏移位置內容偏移位置內容

0~10字段名（以00h結束）17小數位數

11字段類型18，19字段標記

12~15記錄中該字段的偏移量20工作區ID

16字段長度，以Byte為單位21~31保留字節和標志信息

2 FM-index算法

FM-index算法[2]是基于BWT(Burrows-Wheeler transformation)和后綴數組的一種自索引的文本壓縮查找算法。它可對文本進行無損壓縮，并能夠在壓縮狀態下對文本進行查詢。

2. 1 BWT

BWT[3]是一種文本變換形式，其變換過程如下：a)在文本T末尾添加額外的字符“#”。該字符小于文本中出現的任意字符的值。b)文本T#進行循環移動形成新的文本，原始文本T#和新產生的文本組成一個文本集S。c)對文本集S中的文本按照字典順序排列，并且讓每一個文本做一行組成一個文本矩陣M。d)取文本矩陣M的最后一列L作為變換后的文本。

文本矩陣M的第一列也是一個特殊的列，把它標記為F。相對于原始文本，L中的相同字符容易連續出現，這樣容易應用行程編碼進行壓縮。對于變換過程中形成的文本矩陣M，可以看做是文本T的后綴經過排序形成的，從而可利用后綴數組的結構特性來進行文本的查找。比如文本T=“banana”，經過變換可以形成文本矩陣M，如圖1所示。

圖1中左邊欄表示文本T#旋轉形成的矩陣，右邊欄表示排序后的文本矩陣M。由圖1可以得到變換以后的文本L=“annb#aa”，F=“#aaabnn”。F總是按照字典順序排列的。

2. 2 利用BWT實現FM-index算法

為了實現壓縮狀態下的查詢功能，需要能夠在L上順序查找文本。首先定義兩個輔助數組，即C和OCC。對于任意的字符c，C[c]表示所有比c小的字符在L中出現的次數；OCC[c，k]表示字符c在L[1，..，k]中出現的次數。對于變換矩陣M，從上述的變換過程可以知道，任取一行i，最后一個字符L[i]在原始文本T中是第一個字符F[i]的前一個字符。L中相同字符出現的順序與F中出現的順序是相同的，這也就意味著可以利用映射關系在F中尋找到L中的同一個字符。定義映射關系為LF：任給一個字符c，LF[c]=C[c]+OCC[c，k]。LF[c]表示字符c在F中的位置，k表示字符c在L中的位置。對于字符L[i]，則LF[L[i]]表示字符L[i]在F中的位置，從而也表示字符L[i]在文本T中的前一個字符在L中的位置。這樣可以利用LF映射在L中尋找前一個字符的位置。重復上面的過程，就可以從L還原文本T中的子串用于子串查找。

2. 3 FM-index功能與接口

FM-index作為一款開放源代碼的壓縮查詢軟件。它為用戶提供了以下四個基本的功能模塊，可方便用戶使用和擴充。

a)壓縮功能fm_build。建立索引，進行壓縮。

b)解壓功能fm_uncompress。從壓縮后的數據中還原出原始數據。

c)提取功能fm_extract。對于給定的模式，輸出模式子串前后若干個字符。

d)定位功能fm_locate。查找模式在文本中的準確位置。

搜索功能和定位功能只需解開壓縮文件的很小一部分（通常只需解開幾千個字節），所花時間非常少，查詢數兆的文件僅需幾微秒的時間。不過，定位操作所需的時間還與模式在源文件中出現的頻率有關，模式出現次數越多，定位所需時間越長。現在的Fm_index算法無法對二進制格式的DBF文件頭建立索引。本文對這四個基本模塊對應的接口進行擴充，實現了DBF文件的壓縮查詢功能。

3 FM-index在DBF數據庫中的應用

3. 1 壓縮和解壓算法

在DBF文件頭信息中，文件頭長度采用2 Byte表示。這說明DBF的文件頭最大為216 Byte（64 KB），這相對于整個DBF文件的大小幾乎可以忽略。因此，對DBF文件的壓縮和解壓，可以首先將原始的DBF文件sample.dbf拆分為兩個文件，即文件頭sample.header和數據記錄sample.record，然后僅對sample.record文件進行壓縮。DBF文件壓縮的過程如圖2所示。

首先，輸入原始的DBF文件sample.dbf。從sample.dbf的第8，9 Byte提取文件頭的長度header_length；然后，將sample.dbf文件拆分為文件頭sample.header和數據記錄sample.record，其中sample.header文件包含header_length個字符；接下來調用fm_build函數對sample.record文件進行壓縮，生成sample.record.fmi文件。此時壓縮后的文件包括sample.hea-der和sample.record.fmi，可以把它們作為壓縮結果，也可以將它們合并，生成壓縮文件sample.fmi。

相應地，對DBF文件的解壓縮過程如圖3所示。

首先，輸入壓縮后的文件sample.fmi。從sample.fmi的第8，9 Byte提取文件頭的長度header_length；然后將sample.fmi文件拆分為文件頭sample.header和數據記錄的壓縮文件sample.record.fmi，其中sample.header文件包含header_length個字符；最后，調用fm_extract函數對sample.record.fmi文件進行解壓縮，生成sample.record文件。此時解縮后的文件包括sample.header和sample.record，將它們合并，生成原始文件sample.dbf。

3. 2 DBF查詢算法

FM_index算法可以根據壓縮后的文件，計算給定的pattern在原始文件中的位置，并能夠提取原始文件中的一段或者全部內容。DBF文件的查詢需要根據給定的pattern和字段名field_name，提取field_name字段中包含pattern的數據記錄。設pattern在原始文件中出現的位置保存在positions數組里面，記positions[i]對應的pattern在數據記錄中開始和結束的偏移位置分別為pattern_begin與pattern_end，以及field_name字段在數據記錄中開始和結束的偏移位置分別為field_begin與field_end，則符合條件的數據記錄應同時滿足以下兩個條件：

條件1 Pattern出現在DBF文件的數據記錄中，而不能出現在文件頭部，即positions[i]≥header_length;

條件2 Pattern應該出現在field_name字段中，即滿足pattern_begin≥field_begin且pattern_end≤field_end。

根據這兩個條件，假設輸入壓縮后的文件sample.fmi、給定的字段名field_name和模式串pattern，DBF文件在壓縮狀態下進行查詢可以分為三步：

a）計算字段在數據記錄中的開始位置和結束位置。首先，從sample.fmi的第8，9 Byte提取文件頭的長度header_length。根據field_num=(header_length-33)/32，計算每條數據記錄中字段的個數field_num。依次將field_name和文件頭中的各個字段名進行比較，獲取field_name是數據記錄中的第幾個字段，記為相應的field_id。根據第field_id個字段描述符的第12~15 Byte，提取field_name字段在數據記錄中的開始偏移位置field_begin。然后根據第field_id個字段描述符的第16 Byte，提取字段長度field_length，由此可以計算field_name字段在數據記錄中的結束位置field_end=field_begin+field_length。

b)計算pattern在數據記錄中開始和結束的偏移位置。根據文件頭的第10，11 Byte，提取每個數據記錄的長度record_length。對pattern在sample.fmi中每個出現的位置positions[i]，計算pattern在數據記錄中的開始偏移位置為pattern_begin=positions[i]%record_length。相應地，結束位置為pattern_end=pattern_begin+strlen(pattern)-1。

c)根據條件1和2判斷position[i]是否滿足要求。該步驟可以由下面的代碼表示。

if(pos titions[i]>=header_lengthpattern_begin>=field_beginpattern_end<=field_end){

record_id= positions[i]/record_len;

cout<<第>><

……

//調用fm_extract函數輸出符合條件的記錄

}

表3為一個DBF數據庫文件的數據記錄部分，不含文件頭。如果執行select recordswhere [field3] contains〈pattern〉，則只有record1符合查詢條件，其他的數據記錄均不滿足要求。其中，record2中的pattern在field3字段中；record3中的pattern跨越了field2和field3兩個字段；record4和record5中的pattern跨越了兩個數據記錄，均不符合查詢條件。

表3 查詢示例

記錄field1field2field3field4記錄field1field2field3field4

record1patternrecord4pattern

record2patternrecord5

record3pattern

4 測試結果

關于FM-index算法對文本的壓縮查詢性能測試在文獻[4，5]中有具體的描述。本文對FM-index算法在DBF文件中的壓縮查詢性能進行測試，并將測試結果與現在流行的壓縮軟件WinRAR進行比較。測試平臺為DELL OPTIPLEX 320機器，CPU為Intel 1.8 GHz（雙核），內存1 GB，操作系統為Windows XP，編譯器為Microsoft Visual Studio2005。選擇7 MB的DBF文件，分別采用對DBF文件擴充后的FM_index算法和WinRAR進行壓縮、解壓、查詢操作。對照它們的壓縮/解壓時間、查詢時間、壓縮比，可以得到測試結果如表4和5所示。

表4 壓縮、解壓、查詢時間對照表

測試軟件壓縮時間/s解壓時間/s查詢時間/s

FM-index7.7504.7650.062

WinRAR1.7500.2351.563

表5 壓縮比對照表

測試軟件壓縮前/KB壓縮后/KB壓縮比/%

FM-index7 1051 08215.229

WinRAR7 1054456.263

從測試結果可以看出，FM-index在壓縮/解壓時間和壓縮比方面與WinRAR仍然有一定的差距；但是，在查詢功能上，FM-index的查詢時間不到WinRAR的1/25。這是因為FM-index算法支持在壓縮狀態下進行查詢，而WinRAR則是采用依次解壓數據塊后再進行查詢的方法。此外，WinRAR是按文本方式對查詢串進行模式匹配，而擴充后的FM-index算法考慮了DBF表的文件格式，可以過濾非數據記錄中的匹配串（如文件頭中的匹配串），并對查詢結果按數據記錄的格式輸出。綜上所述，FM-index算法適用于查詢密集型的應用中，而對于需要頻繁壓縮/解壓的應用則更適合選擇WinRAR。

5 結束語

本文對FM_index壓縮查詢算法進行擴充，設計了一種適用于DBF數據庫的壓縮查詢工具。擴充后的FM_index算法需要對DBF文件進行分拆和合并，使得它在壓縮和解壓時需要占用大量的時間。盡管如此，與普遍應用的WinRar軟件相比，FM_index算法在查詢操作所需要的時間僅為WinRar的1/25。因此，FM_index算法更適用于聯網審計等查詢密集型的應用。在以后的工作中，可以考慮采用多線程并行執行，分別進行BWT和文件讀寫，從而提高壓縮與解壓的效率。

參考文獻：

[1]ERIK B. xBase file format description[EB/OL]. (2007-08-18)[2008-02-28].http://www.clicketyclick.dk/databases/xbase/format/index.html.

[2]FERRAGINA P， MANZINI G. Opportunistic data structures with applications[C]//Proc of the 41st Annual Symposium on Foundations of Computer Science.2000:390-398.

[3]BALKENHOL B， KUETZ S. Universal data compression based on the Burrows-Wheeler transformation: theory and practice[J]. IEEE Trans on Computers，2000，49(10):1043-1053.

[4]張廣治，張云泉，李偉華，等. FM-index算法性能測試及并行化[J]. 計算機工程，2005，31(22):51-53.

[5]ZHANG Di， ZHANG Yun-quan， CHEN Jing. Efficient construction of FM-index using overlapping block processing for large scale texts[C]//Proc of the 29th European Conference on Information Retrieval Research.Rome， Italy:[s.n.]， 2007. 