一種新的數(shù)據(jù)無損壓縮編碼方法

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

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

1 引言

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

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

2 位重組標記編碼

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

2.1 標記編碼

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

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

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

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

圖1 標記編碼流程

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

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

2.2 位重組

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

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

3 基于位重組標記編碼的數(shù)據(jù)壓縮與解壓方法

3.1 數(shù)據(jù)壓縮方法

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

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

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

3.2 數(shù)據(jù)解壓方法

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

圖2 數(shù)據(jù)壓縮/解壓流程

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

4 應用效果與分析

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

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

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

5 結論

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

表1 各種壓縮方法對不同道測試數(shù)據(jù)壓縮因子統(tǒng)計表

圖3 某道測試數(shù)據(jù)波形及其對應的原始聲波測井波形圖

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

[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] 吳家安. 數(shù)據(jù)壓縮技術及應用[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] 劉杰, 易茂祥, 朱勇. 采用字典詞條衍生模式的測試數(shù)據(jù)壓縮[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] 李傳偉, 慕德俊, 李安宗, 等. 隨鉆聲波測井數(shù)據(jù)實時壓縮算法[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] 吳國清, 陳虹. 一種科學數(shù)據(jù)無損壓縮方法[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] 胡學龍, 江新煉, 周琳, 等. 一種改進的無損壓縮數(shù)字音頻編碼器[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.