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

關(guān)鍵詞：XML；后綴樹；后綴數(shù)組；自索引；BWT

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

一、數(shù)據(jù)壓縮知識

數(shù)據(jù)壓縮技術(shù)的發(fā)展。

隨著計算機技術(shù)的飛速發(fā)展，數(shù)據(jù)壓縮作為解決海量信息存儲和傳輸?shù)闹渭夹g(shù)受到了人們的極大重視，對數(shù)據(jù)壓縮算法的研究也不僅局限于信息論中有關(guān)信源編碼的范疇，數(shù)字圖像信號、語音信號的分析和處理等技術(shù)被大量引入到有關(guān)的研究領(lǐng)域。

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

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

二、XML壓縮索引

（一）XML壓縮背景

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

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

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

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

（二）XML壓縮方法

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

（三）BWT數(shù)據(jù)壓縮

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

三、系統(tǒng)設(shè)計

（一）XML文件整體輸出

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

1.程序執(zhí)行的效率不高，文件內(nèi)容如過大，導(dǎo)致整體的速度下降；

2.不便于查找，整體進行排序換轉(zhuǎn)后打亂了文件結(jié)構(gòu)，不能成為索引；

（二）以XML文件結(jié)構(gòu)進行輸出

由于不能破壞XML文件的結(jié)構(gòu)，只能按照XML現(xiàn)有的標(biāo)簽內(nèi)容進行。這樣我們就引入了XML解析器，它可以分析出XML文件的結(jié)果和具體內(nèi)容。先用解析器解析XML文件，我們就方便的判斷出，什么是標(biāo)簽，什么是數(shù)據(jù)。把每個標(biāo)簽或者數(shù)據(jù)，單獨進行排序轉(zhuǎn)換。

具體過程：

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

2.建立一個空的XML文件，進行添加排序轉(zhuǎn)換后的數(shù)據(jù)；

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

4.如分析出數(shù)據(jù)，則對數(shù)據(jù)進行排序轉(zhuǎn)換，并直接把新數(shù)據(jù)插入包含它的標(biāo)簽中；

5.如分析出標(biāo)簽結(jié)束，則關(guān)閉此級標(biāo)簽，結(jié)束數(shù)據(jù)轉(zhuǎn)換；并記錄新的標(biāo)簽級別，用于插入平級標(biāo)簽時使用。

參考文獻：

[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索引結(jié)構(gòu)[J].計算機研究與發(fā)展，2004，41(10):1793-1801