基于BWT和小波樹的數(shù)據(jù)壓縮算法.pdf

1、隨著互聯(lián)網領域以及其他新興領域的迅猛發(fā)展，全世界每天產生的數(shù)據(jù)急劇增加。數(shù)據(jù)里面蘊含著非常有價值的信息，于是人們開始對這些數(shù)據(jù)進行分析與研究，挖掘自己感興趣的信息。由于數(shù)據(jù)規(guī)模本身非常大，因此數(shù)據(jù)的存儲是一項很大的挑戰(zhàn)，需要耗費很大的磁帶，磁盤資源；除此之外互聯(lián)網上不同主機之間的數(shù)據(jù)通信量日趨增大，這占用較多的網絡帶寬資源，而且是很耗時的。因此對這些數(shù)據(jù)的壓縮成為大數(shù)據(jù)處理的研究熱點和解決大數(shù)據(jù)問題的必然趨勢。
　　首先分析了基于

2、后綴數(shù)組計算BWT的方法，BWT變換的性質，并且提出一種BWT逆變換時的LF修正算法；其次研究了01序列上各種rank/select數(shù)據(jù)結構的原理，空間大小，并從數(shù)學角度分析了小波樹上內部節(jié)點01序列的層次化對各種rank/select數(shù)據(jù)結構空間大小的影響；最后基于BWT變換和小波樹，我們提出一種數(shù)據(jù)壓縮及解壓縮算法的框架，并且給出了該算法并發(fā)化的一些思路。我們通過定義自己的壓縮文件格式，最終高效地開發(fā)了一款數(shù)據(jù)壓縮軟件，wzip。<

3、br>　　我們還通過實驗測試了小波樹樹形，節(jié)點壓縮方式，BWT變換塊大小對wzip壓縮率的影響。最終我們發(fā)現(xiàn)在BWT變換塊大小固定的條件下，基于hu-tacker[10]編碼的小波樹并且內部節(jié)點采用run-length Gamma[11]的wzip壓縮方案能夠達到最好的壓縮效果。通過將wzip和bzip2，gzip，rar，zip，7z，compress這些數(shù)據(jù)壓縮軟件在壓縮率，壓縮時間，解壓時間方面的對比，我們發(fā)現(xiàn)wzip具有壓縮率好