XML數據壓縮索引研究

摘要：隨著Internet的迅速發展，大量信息充實了我們的生活，索引成為人們檢索信息的必要途徑之一。另一方面XML逐漸成為數據表示與交換的標準，對于XML數據文檔的查詢變成當今研究的熱點

關鍵詞：XML；后綴樹；后綴數組；自索引；BWT

中圖分類號：TP311.13 文獻標識碼：A 文章編號：1674-7712 (2012) 06-0099-01

一、數據壓縮知識

數據壓縮技術的發展。

隨著計算機技術的飛速發展，數據壓縮作為解決海量信息存儲和傳輸的支撐技術受到了人們的極大重視，對數據壓縮算法的研究也不僅局限于信息論中有關信源編碼的范疇，數字圖像信號、語音信號的分析和處理等技術被大量引入到有關的研究領域。

1977年，兩位以色列科學家Jacob Ziv和Abraham Lempel發表了名為“A Universal Algorithm for Sequential Data Compression”（順序數據壓縮的通用算法）的論文，提出了一種不同與以往的基于字典的壓縮方法——LZ77，他們在1978年又提出了LZ77的改進算法——LZ78，這兩個算法吧數據壓縮的研究推向了一個全新的階段。1984年，Terry Weleh發表的論文“A Technique for High Performance Data Compression”（高性能數據壓縮技術）描述了對LZ78算法的改進和具體實現技術，成為LZW算法。目前，無損數據壓縮領域中流行的數據壓縮方法多是基于字典的壓縮技術。UNIX系統上的一個實用壓縮軟件COMPRESS和Windows系統下的壓縮軟件Winzip和Winrar中所使用的壓縮算法都是基于字典壓縮技術的。

當數據壓縮被用于減少存儲空間時，可以減少程序的總執行時間。這是因為存儲量的減少將導致磁盤存取次數的減少，雖然數據的壓縮/解壓縮過程會增加額外的程序指令，但由于程序的執行時間通常少于數據的存儲時間，因此中的執行時間將減少。也正因如此，數據壓縮技術在計算機技術飛速發展的今天仍然有著很重要的作用。

二、XML壓縮索引

（一）XML壓縮背景

上文中已經述說了XML的優點，但和其它形式的數據表示相比，XML文檔往往很大。因此有些時候，傳輸速度和存儲空間會非常重要。具體來說：

1.XML是一種清晰而易用的文本標記格式，但它的弱點就是當有大量數據需要交換，而程序內部處理部分又非常少時，會導致XML文檔非常大，這樣過大的空間占用意味著更大的處理代價；

2.由于本文壓縮算法多年來一直是大量研究項目的課題，目前已經非常成熟。這種類型的算法都能方便的將XML進行壓縮，但將XML文本作為一般文本文件進行壓縮，這類算法都不大可能改善處理的速度，而且還會增加了解壓后再解析的步驟；

3.我們把XML文檔用于索引結構，這樣就不能只保持了XML文檔的結構而無法對XML進行索引搜索。也就排除了一些簡單的XML壓縮算法。

（二）XML壓縮方法

當壓縮文檔時，通常首先考慮常用的壓縮算法，如：Lempel-Ziv和Huffman，以及在它們上面實現變化的一些常用實用程序。在類Unix平臺上通常是gzip；在其它平臺上，zip更為常用，比如：PKZIP、Info-ZIP和WinZip。但這些實用程序實際上意在充分地減少XML文件的大小。但是，都沒有保持了XML文檔的結構，或是無法對XML文檔進行索引。這樣本文選擇使用BWT壓縮算法而不是順序Lempel-Ziv算法。

（三）BWT數據壓縮

利用BWT壓縮算法，我們先把字符文本進行轉換，然后進行壓縮，這樣就解決了XML文檔過大的弊端。而且BWT壓縮算法要比順序LZ算法，解壓時速度有所提高。BWT算法的具體介紹我們在第5章進行講解。

三、系統設計

（一）XML文件整體輸出

首先，我們先不考慮XML文件的結構，這樣把XML數據文件提交給程序，會按照普通文本文件的方式進行處理。程序先讀取整個文件的內容，之后將它們作為一個字符串，進行后綴數組排序，然后BWT轉換。但是這樣的結果并不如意，有以下兩個缺點：

1.程序執行的效率不高，文件內容如過大，導致整體的速度下降；

2.不便于查找，整體進行排序換轉后打亂了文件結構，不能成為索引；

（二）以XML文件結構進行輸出

由于不能破壞XML文件的結構，只能按照XML現有的標簽內容進行。這樣我們就引入了XML解析器，它可以分析出XML文件的結果和具體內容。先用解析器解析XML文件，我們就方便的判斷出，什么是標簽，什么是數據。把每個標簽或者數據，單獨進行排序轉換。

具體過程：

1.XML解析器讀取分析XML文件；

2.建立一個空的XML文件，進行添加排序轉換后的數據；

3.如分析出標簽開始，則提取此標簽，對其進行排序轉換，把結果插入新的XML文件；并記住此標簽的級別，用于插入下級標簽時使用；

4.如分析出數據，則對數據進行排序轉換，并直接把新數據插入包含它的標簽中；

5.如分析出標簽結束，則關閉此級標簽，結束數據轉換；并記錄新的標簽級別，用于插入平級標簽時使用。

參考文獻：

[1]Donald Knuth.Art of Computer Programming[M].2002，Volume，3

[2]N.Jesper Larsson.Structures of String Matching and Data Compression[D].Sweden:Lund University，1999

[3]包小源，宋再生，唐世渭，楊冬青，王騰蛟.SuffIndex——一種基于后綴樹的XML索引結構[J].計算機研究與發展，2004，41(10):1793-1801