一種新的數據無損壓縮編碼方法

蔡 明 喬文孝鞠曉東 車小花 盧俊強 賈安學

(中國石油大學油氣資源與探測國家重點實驗室 北京 102249)(北京市地球探測與信息技術重點實驗室 北京 102249)

1 引言

數據壓縮是一種消除原始數據之間的冗余性，并通過特殊的編碼方式將原始數據文件轉化為另一個占用存儲空間更小的數據文件的技術[15]-。數據壓縮技術在過去 20年里得到了快速的發展[5,6]。目前，它已廣泛應用于數字通信、數字存儲、計算機、數字出版及智能控制等眾多領域[612]-。編碼是所有數據壓縮方法的關鍵組成部分，且不同的編碼方法對不同類型的數據序列有效[2]。如果采用一種專門為圖像或音頻數據設計的壓縮程序(或編碼方式)對文本文件進行壓縮，則壓縮后的文件大小可能大于甚至遠大于原始數據文件。因此，針對不同類型的數據文件，選擇或設計合適的編碼方式是壓縮成功的關鍵。

本文為均方值(定義均方值為各樣值平方的算術平均值)較小的整型數據序列(或均值為0，方差較小的整型數據序列)設計了一種新的編碼方式位重組標記編碼，該編碼方式是一種無損編碼方式。對于滿足均方值較小的整型數據序列，可直接用位重組標記編碼進行壓縮處理；對于不滿足該條件的數據序列，可先利用相關的信號處理方法進行處理，使之滿足條件后再利用位重組標記編碼進行壓縮處理；即位重組標記編碼既可作為一種獨立的數據壓縮方法，也可與其它信號處理方法結合組成新的數據壓縮方法，可應用于多種類型數據的壓縮。利用具有較小均方值特征的整型數據序列對算術編碼，LZW 編碼，WinRAR，專業音頻數據壓縮軟件FLAC(Free Lossless Audio Codec)[13]和本文的方法進行了壓縮解壓測試，并對比分析了上述方法的壓縮效果。

2 位重組標記編碼

位重組標記編碼主要包括位重組和標記編碼兩個組成部分，是為具有較小均方值特征的整型數據序列設計的一種有效的無損編碼方式。圖像數據、音頻數據和其它波形數據經過預測處理得到的預測誤差或經過小波變換處理得到的小波系數以及具有均值為零，方差較小的正態分布特征的實驗數據等數據序列的均方值都比較小，可利用位重組標記編碼進行壓縮處理，且理論上可以取得較好的壓縮效果。測試表明，位重組標記編碼對具有較小均方值特征的整型數據序列的壓縮效果優于算術編碼，LZW 編碼，WinRAR軟件和專業音頻數據壓縮軟件FLAC的壓縮效果。

2.1 標記編碼

標記編碼的基本思想源于文獻[14]中的一種Index-Data記錄格式的啟發。Index-Data記錄格式是一種比較初級的標記記錄格式，只有在數據0出現的頻次占絕對優勢時才會取得較好的壓縮效果，否則可能導致壓縮后數據文件大小大于甚至遠大于原始數據文件大小。本文提出了一種更為有效的標記編碼方式，可以根據數據的分布特點自適應地進行標記編碼。

標記編碼的核心思想是利用較短的碼字(也稱為替代碼字，指需要用較少二進制位數表示的符號)代替數據流中出現頻率最高的數據，其它數據正常編碼(即不做任何改變，原樣記錄需要編碼的數據，且每個數據認為是一個碼字，稱為非替代碼字)，并在每個非替代碼字前給出一個特殊的位標記。除了替代碼字之外，其它碼字均具有相同的長度。給出特殊的位標記的目的是為了在數據解壓時能夠正確地區分非替代碼字和替代碼字，以保證解碼的正常進行。

本文的標記編碼采用了雙重標記，可根據局部數據的概率分布特點選擇合理的編碼方式，具有自適應性。標記編碼的具體實現過程主要分3步完成。第1步，將輸入數據流分隔成多個數據塊，前面的數據塊具有相同的大小，最后一個數據塊可以稍小一些；第2步，統計數據塊中各個數據出現的概率，并記錄出現概率最大的數據及其對應的概率；第 3步，根據第2步記錄的最大概率值大小選擇標記編碼或正常編碼(原樣輸出輸入的各個數據)對該數據塊進行編碼；編碼方式選擇的準則是：當最大概率值大于設定的閾值時選擇標記編碼方式，否則選擇正常編碼方式。其中，第3步是本文標記編碼方式的關鍵和難點。第1步中確定的數據塊大小對編碼效果也會有一定的影響，但影響不太大；一般而言，對于相同類型的數據序列，最佳數據塊大小也是相近的，可以通過經驗確定。

編碼過程是對輸入數據流中各數據塊依次進行的，直到最后一個數據塊被編碼。首先，根據將被編碼的數據塊選擇的編碼方式，將其對應的編碼方式標記符(此為一重標記)記錄到輸出文件中；然后，按選定的編碼方式對該數據塊進行編碼；若選擇標記編碼方式進行編碼，則先原樣輸出數據塊中出現概率最大的數據，然后依次對數據塊中的各數據進行編碼，當編碼過程中遇到出現概率最大的數據時，則用選定的較短的替代碼字代替，其它數據原樣輸出并在前面給出一個特殊的位標記(此為二重標記)；若選擇正常編碼方式進行編碼，則依次原樣輸出數據塊中各數據即可。如此循環，即可完成對整個輸入數據文件的編碼，編碼過程如圖1所示。

圖1 標記編碼流程

將輸入數據流分塊進行編碼的好處是可以自適應地根據數據流中局部數據的分布特點選擇合適的編碼方式進行編碼。然而，普通的標記編碼方式(不對數據流進行分割，對整個數據流采用統一的標記編碼方式進行編碼)則沒有這種自適應性。利用普通標記編碼方式進行編碼時，對于非替代數據(出現頻率非最高的數據)，除了原樣輸出該數據外，還需要給出特殊的標記符號，而過多的標記符號也將額外地占據大量的存儲空間，不利于提高數據壓縮的效果。因此，當數據塊中沒有數據出現的頻率占有絕對優勢時，若仍采用標記編碼方式進行編碼，則需要給出大量的標記符號，這可能導致壓縮后數據文件比原始數據文件占據的存儲空間還大，達不到數據壓縮的目的；而此時若選擇正常編碼方式進行編碼，則可以避免這種不利情況的發生。

本文的標記編碼方式可以根據各數據塊中數據的概率分布特點自適應地選擇合適的編碼方式進行編碼。當數據塊中有數據出現的概率高于設定的閾值時選擇標記編碼方式進行編碼，使壓縮后數據小于或遠小于壓縮前數據占據的存儲空間；否則選擇正常編碼方式進行編碼，使壓縮前后數據文件大小相同；這樣就保證了每個數據塊壓縮后的數據比壓縮前的數據占據的存儲空間小或相等，從而獲得整體上的壓縮效果。因此，本文的標記編碼方式一般都會取得一定的壓縮效果，絕對不會出現壓縮后數據文件大小遠大于壓縮前數據文件大小的情況。

2.2 位重組

位重組的目的是為了提高某一數據(一般情況下主要是數據0)出現的概率，是為標記編碼服務的。位重組的基本思想來源于洗牌(Shuffle)原理[15,16]。本文使用的位重組處理方法可描述為：首先依次提取數據流中各數據的最高位，然后依次提取各數據的次高位，如此循環，直至最后依次提取各數據的最低位，之后將這些提取的數據位按順序組合成新的數據；對于16位無符號整型數而言，首選按順序依次提取數據流中各數據的第16位，第15位，…，第1位，然后將這些提取到的數據位按順序組合成新的數據(每16位組合成1個數據)即完成了位重組處理。

具有較小均方值特征的整型數據序列中各數據的高位部分基本都是由0組成的，對這類數據進行位重組處理理論上可以大大提高某些數據(主要是數據0)出現的概率。實際測試表明，對具有較小均方值的整型數據序列進行位重組處理確實可以明顯提高某些數據出現的概率，有利于提高最終的壓縮效果。

3 基于位重組標記編碼的數據壓縮與解壓方法

3.1 數據壓縮方法

由于具有較小均方值特征的整型數據序列一般既包括負整數，又包括非負整數，即為有符號整型數據序列。所以在采用位重組標記編碼對這類數據序列進行壓縮之前，有必要先對數據序列進行數據類型轉換處理，即將有符號整型數據序列轉換為無符號整型數據序列。做這一處理有兩點好處：(1)可以避免編碼和解碼過程中對符號位進行特殊的處理；(2)可以提高位重組標記編碼的處理效果，進而提高最終的壓縮效果。由于負整數的符號位為 1，而非負整數的符號位為 0，所以有符號整型數據序列的符號位由0和1組成，且其出現的概率可能相近，這不利于提高位重組標記編碼的效果。而轉換為無符號整型數據序列之后再進行位重組處理則可以避免這一問題，因為序列中無符號整型數的最高位主要由0組成，且一般情況下全為0。

數據類型轉換可以通過一種可逆的一一映射來實現，即將第n個負整數(如 n-)映射到第n個奇數(如(2 1)n- )，將第m個正整數映射到第m個偶數(2m)。具體轉換式為[17,18]

基于上述討論容易得出本文數據壓縮的實現方法。本文的數據壓縮方法主要包括 3個部分：(1)對具有較小均方值特征的整型數據序列進行數據類型轉換處理，將有符號整型數轉換為無符號整型數；(2)對無符號整型數據序列做位重組處理；(3)標記編碼，實現壓縮。數據壓縮流程如圖2下半部分所示。

3.2 數據解壓方法

數據解壓是數據壓縮的逆過程。數據解壓方法同壓縮方法一樣也包括3個部分：(1)對壓縮數據進行標記解碼，這是標記編碼的逆過程且根據標記編碼的原理和實現方法容易得到標記解碼的實現方法；(2)對標記解碼后的數據做位恢復處理，這是與位重組相對應的反處理，即將各數據位恢復到位重組前的原始位置上；(3)進行數據類型轉換；解壓過程中的數據類型轉換是將無符號整型數轉換為有符號整型數，這與壓縮過程中的數據類型轉換正好相反，由式(1)很容易得出無符號整型數到有符號整型數的轉換公式。完成以上3步處理之后就重構出了原始數據序列，解壓過程完畢。數據解壓流程如圖2上半部分所示。

圖2 數據壓縮/解壓流程

根據數據壓縮各處理部分的原理及實現方法容易得到對應的數據解壓各處理部分的實現方法。由于壓縮各部分處理都是完全可逆的，所以整個壓縮處理方法也是完全可逆的，即通過壓縮數據文件可以完全無失真地重構出原始數據序列。對具有較小均方值特征的整型數據序列進行的壓縮解壓測試也證明了這一點。

4 應用效果與分析

根據上文介紹的壓縮解壓方法，本節在VC++平臺上編寫了相應的壓縮和解壓程序。運用編寫的程序和其它幾種無損壓縮方法(或編碼方法)對實際的具有相對較小均方值的整型數據序列進行了壓縮解壓測試，并對比分析了它們的壓縮效果。

測試數據是由實際的聲波測井波形數據經過去相關處理后得到的。我們從實際的聲波測井資料中隨機地抽取了12道波形，并利用信號處理方法對波形數據進行去相關處理得到了 12道均方值相對較小的測試數據序列，每道測試數據文件大小均為21968 Byte。測試數據序列的均方值明顯小于原始聲波測井數據序列的均方值，其波形如圖3所示。利用這12道測試數據序列對算術編碼，LZW編碼，WinRAR軟件，專業音頻數據壓縮軟件FLAC和本文方法進行了壓縮解壓測試。測試結果表明，這幾種壓縮方法都是無損的，且各種壓縮方法對不同道測試數據的壓縮因子(原始數據文件大小與壓縮數據文件大小之比)如表1所示。

從表1可以看出，FLAC軟件基本沒有壓縮能力，且對于有些測試道數據，其壓縮后數據文件大小反而超過了原始數據文件大小；LZW編碼方法有一定的壓縮效果，但效果不佳；相比而言，算術編碼，WinRAR軟件和本文方法均取得了相對較好的壓縮效果。另外，無論從單個測試道數據的壓縮效果，還是最后各種壓縮方法的平均壓縮因子的對比情況來看，本文方法的壓縮效果均明顯優于其它壓縮方法的壓縮效果。

5 結論

針對具有較小均方值特征的整型數據序列，本文提出了一種新的有效的可用于無損數據壓縮的位重組標記編碼方法，并在VC++平臺上實現了相應的壓縮解壓程序。利用實際具有較小均方值特征的整型數據序列對本文方法和其它幾種無損壓縮方法進行了壓縮解壓測試，并對比分析了各種壓縮算法的壓縮效果。本研究主要得出如下結論：(1)本文數據壓縮方法可以實現整型數據序列的無損壓縮與解壓，壓縮解壓速度快，效果穩定； (2)對具有較小均方值特征的整型數據序列，位重組標記編碼是一種較好的無損壓縮方法，且一般情況下均方值越小，壓縮效果越好；(3)本文方法對滿足應用條件的數據序列具有較高的壓縮因子，壓縮效果優于經典的算術編碼，LZW編碼，通用的WinRAR軟件和專業音頻數據壓縮軟件FLAC的壓縮效果；(4)對于具有較小均方值特征的整型數據序列，可直接利用位重組標記編碼進行壓縮處理；對于不滿足該條件的數據序列，可先利用相關的信號處理方法進行處理，使之滿足條件后再利用位重組標記編碼進行壓縮處理；因此，位重組標記編碼可應用于多種類型數據的壓縮，應用范圍廣泛。

表1 各種壓縮方法對不同道測試數據壓縮因子統計表

圖3 某道測試數據波形及其對應的原始聲波測井波形圖

本文方法是針對具有較小均方值特征的整型數據序列設計的，只有對滿足此條件的數據序列才會取得良好的壓縮效果，且一般情況下數據序列的均方值越小，壓縮效果越好。另外，在必要的情況下，可進行進一步的研究，將該方法發展為適用于平均有效位數較少的浮點型數據序列的位重組標記編碼方法。

[1] Salomon D. Data Compression: The Complete Reference[M].London: Springer-Verlag, 2007: 1-952.

[2] Salomon D and Motta G. Handbook of Data Compression[M].London: Springer-Verlag, 2009: 1-1198.

[3] Li X. Compression of well-logging data in wavelet space[C].1996 SEG Annual Meeting, Denver, Colorado, 1996:1615-1618.

[4] Schendel E R, Ye J, Shah N, et al.. ISOBAR preconditioner for effective and high-throughput lossless data compression[C]. 2012 IEEE 28th International Conference on Data Engineering, Washington, 2012: 138-149.

[5] Sayood K. Introduction to Data Compression[M].Massachusetts: Morgan Kaufmann, 2006: 1-39.

[6] 吳家安. 數據壓縮技術及應用[M]. 北京: 科學出版社, 2008:1-282.

[7] Keymeulen D, Aranki N, Hopson B, et al.. GPU lossless hyperspectral data compression system for space applications[C]. 2012 Institute of Electrical and Electronics Engineers Aerospace Conference, Big Sky, MT, 2012: 1-9.

[8] Srisooksai T, Keamarungsi K, Lamsrichan P, et al.. Practical data compression in wireless sensor networks: a survey[J].Journal of Network and Computer Applications, 2012, 35(1):37-59.

[9] Hou Zhi-ling, Su Xian-yu, and Zhang Qi-can. Virtual structured-light coding for three-dimensional shape data compression[J]. Optics and Lasers in Engineering, 2012, 50(6):844-849.

[10] 劉杰, 易茂祥, 朱勇. 采用字典詞條衍生模式的測試數據壓縮[J]. 電子與信息學報, 2012, 34(1): 232-235.Liu Jie, Yi Mao-xiang, and Zhu Yong. Test data compression using entry derivative mode of dictionary[J]. Journal of Electronics ＆amp; Information Technology, 2012, 34(1): 232-235.

[11] Chen F, Chandrakasan A P, and Stojanovic V M. Design and analysis of a hardware-efficient compressed sensing architecture for data compression in wireless sensors[J]. IEEE Journal of Solid-State Circuits, 2012, 47(3): 744-756.

[12] Salomon D. A Concise Introduction to Data Compression[M].London: Springer-Verlag, 2008: 1:20.

[13] Coalson J. FLAC[OL]. http://flac.sourceforge.net/. 2011.

[14] 李傳偉, 慕德俊, 李安宗, 等. 隨鉆聲波測井數據實時壓縮算法[J]. 西南石油大學學報(自然科學版), 2008, 30(5): 81-84.Li Chuan-wei, Mu De-jun, Li An-zong, et al.. A real-time data compression algorithm for acoustic wave logging while drilling[J]. Journal of Southwest Petroleum University(Science ＆amp; Technology Edition), 2008, 30(5): 81-84.

[15] 吳國清, 陳虹. 一種科學數據無損壓縮方法[J]. 計算機工程與應用, 2006, (5): 172-175.Wu Guo-qing and Chen Hong. A lossless compression scheme for scientific data from simulation[J]. Computer Engineering and Application, 2006, (5): 172-175.

[16] 劉杰, 徐三子. 用于編碼壓縮的測試位重組算法[J]. 計算機工程, 2010, 36(21): 19-21.Liu Jie and Xu San-zi. Test-bit-rearrangement algorithm applied to code compression[J]. Computer Engineering, 2010,36(21): 19-21.

[17] 胡學龍, 江新煉, 周琳, 等. 一種改進的無損壓縮數字音頻編碼器[J]. 微電子學與計算機, 2003, (7): 23-25.Hu Xue-long, Jiang Xin-lian, Zhou Lin, et al.. An improved lossless compression in digital audio coder[J]. Microelectronics and Computer, 2003, (7): 23-25.

[18] Robert F R. Some practical universal noiseless coding techniques, Part III[R]. Jet Propulsion Laboratory, California Institute of Technology, 1991.