基于BWT和PPM的XMAC數據無損壓縮方法研究

摘 要：正交多極子陣列聲波測井儀（XMAC-II）采集交叉偶極X、Y方向各8個接收器及單極8個接收器的陣列數據，所采用的XTF文件格式使得解釋完成后的數據存儲要占用大量硬盤空間，因此對陣列聲波數據進行有效的編碼和壓縮，對于減少存儲空間、節約企業運行成本具有重要意義。本文在分析聲波波列數據特征的基礎上，提出了一種將16位二進制數據的高8位和低8位分別編碼的無損壓縮策略，其中高8位采用部分匹配預測（PPM）編碼方式，低8位經過BW變換、前移編碼后再采用PPM編碼。實驗表明，本文方法的壓縮率不僅優于傳統的Huffman、LZW、RLE等算法，還優于目前流行的WinZip、Bzip2等軟件。

關鍵詞：數據無損壓縮 BWT PPM

中圖分類號：TH841 文獻標識碼：A 文章編號：1674-098X（2011）12（a）-0000-00

XMAC-II儀器采用的XTF文件格式直接將每個時間采樣點的值以十六位整型方式存儲，未經優化編碼，占用空間較大，僅600米井段的數據就要占用250M字節。按照勝利測井公司每年平均施工110井次、每井次測量井段2000米計算，解釋完成后的數據存檔就需要占用大約92G的硬盤空間。因此，對XTF文件進行壓縮編碼非常必要。作者詳細分析了陣列聲波數據的特點，發現數據具有以下兩個特征：(1)波列數據比較連續，相鄰數據差值較小，具有較強的相關性；(2)大部分數據在基線附近上下波動。此外，由數據的二進制形式可以看到高8位數據在變化幅度不大的地方基本保持不變，且波峰、波谷位置附近高8位也大致相同。對于低8位數據來說，雖然相鄰時刻的值不可能完全相同，但某一個值也會重復出現。有鑒于此，本文提出一種新的無損壓縮策略，即對高8位采用部分匹配預測算法（PPM）編碼，而對規律性較差的低8位先采用Burrows-Wheeler變換使相同值在一定程度上集中在一起，經過前移編碼后再使用PPM編碼，從而實現更高的壓縮率。

算法實現

1.1 數據預處理

1.1.1 Burrows-Wheeler變換（BWT）

BW變換【1】是一種有效的數據變換方法。對于長度為n的輸入符號串S ，BW變換將其改序成另一個符號串L，新的符號串L按如下步驟生成:

①找出字符串S中最小的字符a并保存到數組F中；

②將最小字符所在位置的前一個字符存放到字符數組L中，這就是所要得到的新符號串L；

③將最小字符后所有字符移到該符號串S的開始位置，最小字符串前的符號串依次向后移動，組成新的符號串S′，然后返回到第一步，直到將字符串S中的所有字符處理完；

④在處理完某個字符后，必定得到一個新的符號串S′和原始的符號串S相同，記錄下此時已經處理的字符的個數，記為I，解碼時會用到。

1.1.2 前移編碼（MTF）

經過BW變換所產生的符號串L具有如下特性：相同符號在L中的分布趨于集中，即在L中的某一區域內某一符號x的出現概率很大，而在其它區域則很小。這樣L便適合采用前移編碼【1】進行去相關。

L中某符號x出現概率相對集中于某一區域的特性，正好是前移編碼能實現高效壓縮的條件。具體實現步驟如下:

①初始化一個字符表數組A，此數組中含有字符串S的所有字符(對相同的字符只記錄一次)；

②對于尋找在A中的位置，將在它前面的符號數保存到數組C中， 然后把移到A的開頭。

數組C即為前移編碼結果，當L中某字符連續出現時，C中將會出現大量的0，于是C適合用統計模型方法進行編碼。

1.2 部分匹配預測算法（PPM）

PPM(Prediction by Partial Matching)是一種上下文統計模型編碼技術，其基本思想就是利用最近輸入的幾個字符(叫做上下文模型)，來預測下一個字符。其中，模型的長度k可以從0到已輸入字符的最大長度km不等。PPM算法分為建模和編碼兩個過程，對于k長度的上下文模型來說，首先要計算在輸入字符串中，每個k長度的字符串后面不同字符出現的次數，然后可以得到該上下文模型的預測概率，即為建模過程。

定義一個已知字符串模型的最大長度為k，當下一個輸入的字符已經由該上下文模型預測出時，該輸入字符出現的概率就是預測概率。而當下一個字符不能由上下文模型預測出時，輸入字符的概率無法得到，這時，就需要用到“逃逸(escape)”概率。添加逃逸上下文預測模型是為了防止零概率字符的情況出現。“逃逸”概率將模型從k跳到k-1，如果k-1長度的模型能預測出該字符，就能得到相應的預測概率。如果不能，該過程將一直進行直到某個模型可以預測出該字符。為了保證無論出現什么字符，最后“逃逸”過程都能結束，最低長度的模型中必須包括字母表中所有的字符。逃逸上下文預測模型概率的計算方法有多種，每一種方法對應PPM一種類型。

實驗結果與分析

實驗過程中，將傳統的字典編碼方法LZW、熵編碼算法、游程長度編碼（RLE），以及當前比較流行的WinZip軟件（基于Windows平臺）和Bzip2軟件的壓縮效果與本文方法的壓縮結果進行對比。實驗數據為勝利油區YI7-7井中3000～3430米井段的XMAC-II實測數據，并選擇其中TFWV01二維曲線的所有8個接收器測量信號，共計30860K字節。

本文方法在所有方法中壓縮率是最高的，達到了50.541%；Bzip2壓縮率也較高，究其原因是采用了BW變換和Huffman編碼；采用RLE算法壓縮后數據量反而增大，作者通過實驗證明這是由于陣列聲波數據中相同值的采樣點分布很不集中造成的。由此可見，本文方法采取將數據分為高8位和低8位分別壓縮，并在數據預處理時進行BW變換以提高壓縮率的策略是正確的。

3 結語

正交多極子陣列聲波數據存檔占用大量硬盤空間的問題亟待解決，而目前勝利測井公司在工作流程中使用的Unix系統中的Compress程序壓縮率僅達到10%左右，不能滿足需要。本文提出的新的無損壓縮策略，針對陣列聲波數據特點，并采用高壓縮性能的部分匹配預測算法（PPM）和BW變換及前向編碼，能夠將陣列聲波數據的壓縮率提高到50%以上，可以節約大量的計算機資源，其程序源碼也可以移植到Unix平臺上，因此這種方法具有良好的應用前景。

參考文獻

[1] 田峰. 基于BW 算法的高采樣率心電數據無損壓縮[J]. 生物醫學工程學雜志， 2008

[2] 周小四，楊杰，王淑華. 改進的PPM 數據壓縮算法及性能分析和比較[J]. 上海交通大學學報， 2002;