數據壓縮算法研究

胡志鵬

摘 要 數據壓縮可以去除數據中的冗余信息，減少數據的存儲量，同時也可以減輕網絡負擔。本文介紹了目前最常用的幾種數據壓縮的方法，包括預測編碼技術、時間序列線性擬合技術、DCT變換、DWT變換和壓縮感知。

關鍵詞 數據壓縮 預測編碼 壓縮感知 小波變換

中圖分類號：TP393 文獻標識碼：A

0引言

數據壓縮技術一直是一個熱門研究領域，其作用是去除數據中存在的冗余信息，以不影響數據內容為前提，盡量減小數據存儲大小。

1預測編碼技術

預測編碼技術根據信源存在的時空相關性這一特點去預測信源數據，然后用預測數據減去真實信源數據得到預測值，最后將差值進行存儲，利用這種方法去除信源中的冗余信息，實現數據壓縮的目的。

預測是根據前n個測量參數，估計當前的測量值。x0表示當前測量值，表示估計值，同時{%Zi|i=1，2，…，N}是預測系數，其中N是預測的階數。

預測估計值：

（1.1）

預測誤差：

（1.2）

測量的預測誤差記作MSE：

MSE=e2i （1.3）

預測多項式階數越高，預測準確性越高，計算復雜性也急劇增加。

2時間序列線性擬合技術

數據在一段時間內保持相對穩定的某種趨勢，使得采樣數據構成時間序列，可以通過構建合適的時間序列數學模型得到近似的數據，使數據量少于原時間序列，達到數據壓縮的目的。

時間序列為：

s=（（t1，d1），（t2，d2），…，（tn，dn）） （1.4）

其中（ti，di）表示在ti時的采樣值為di，n為采樣次數。時間序列的擬合回歸線為就是以時間t為自變量，以采樣數值d為因變量的函數。令

d=%Z+%[t+%g，%g∈（0，%]2） （1.5）

對上式參數采用最小二乘法進行線性擬合，得到%Z，%[的估計值分別為：

（1.6）

得到回歸方程：

（1.7）

3小波變換

小波變換在時域頻域都具有表征信號局部特征的能力和多分辨率分析的特點，它將原始信號伸縮和平移，分解為一系列頻率不同的子帶信號， 這些子帶信號具有良好的時域、頻域等局部特征。這些特征可用來表示原始信號的局部特征，進而實現對信號時間、頻率的局部化分析，壓縮后數據失真更小，壓縮效率也更高。

小波變換將信號表示成基函數的線性組合，其基函數是具有緊支集的母函數，對母函數伸縮和平移可以得到小波序列。

（2.1）

其中a為伸縮因子，b為平移因子。

對于任意函數F（t）屬于L2（R）的連續小波變換為：

Wf（%Z，b）=fflF，%q%Z，bffl=|%Z|1/2RF（t）%q*·（）dt （2.2）

其逆變換為：

F（t）=Wf（%Z，b）%q（）d%Zdb （2.3）

基本小波函數的選擇取決于實際應用，小波函數在幾何形狀必須是振蕩函數和迅速收斂的函數。尺度因子和平移因子的不同會給小波函數的幾何形狀帶來很大的變化。

4壓縮感知

對某一信號 f 進行采樣實際上就是將該信號同一系列波形進行內積運算。例如：奈奎斯特采樣就是信號 f 與一組頻率大于2 f 的脈沖信號的內積。

yk，k=1，……，m （3.1）

壓縮感知采用波形數目遠小于信號維數的采樣信號對信號 f 進行欠采樣。得到的信號采樣值的數目m遠小于原始信號 f 的維數n。因此壓縮感知在采樣的同時實現了對信號的壓縮。

壓縮感知將n維可壓縮信號x∈k通過采樣矩陣%O∈Cm，n（m<

y=%Ox （3.2）

如果信號 f 在域是稀疏的，那么式（5）就可以寫為

y=%Ox=%O%ox=Ax （3.3）

其中x為信號 f 在%o域的系數，A=%O%o是一個m譶階的矩陣，稱之為感知矩陣。

Candes和Tao指出采樣矩陣%O需要滿足一定的約束等距條件，如果測量矩陣%O的約束等距常數滿足HQ2k+HQ3k<1，則能夠從k·log（n /k）個測量值中精確恢復出原始信號。

定義：對于矩陣%O∈Cm，n（m<

（3.4）

的最小數值HQk定義為矩陣%O的約束等距常數。如果HQk∈（0，1），就說矩陣%O滿足k階約束等距性。

壓縮感知恢復算法的做法是對信號或其變換系數的非零元素個數進行約束，通過l0范數最小化求解：

s.t.y=%Of=%O%ox （3.5）

其中||x||0，是l0范數。

Donoho等利用l0范數代替l0范數，將（9）的非凸組合優化問題轉化為凸松弛問題求解：

s.t.y=%Of=%O%ox （3.6）

其中||x||0，是l1范數。基追蹤 （BasisPursuit，BP）方法將（10）中有約束的l1范數最小化問題轉換為線性規劃問題進行求解。如果信號足夠稀疏，l1范數最小化方法能夠比較精確的恢復出原始信號。

5總結

數據壓縮算法還有很多，文中只列出了最常見、目前切實可行的、比較成熟的壓縮算法，還有很多算法處于各種原因，未能真正的走進人們的生活，下一步將對這些算法進行深入研究。

參考文獻

[1] Hao Yong-zhi，Chen Jun-jie. Based data compression energy saving method for wireless sensor networks [J]. Huazhong University of Science and Technology （Natural Science edition） ， 2008， 36 （ S1） ： 232-234.

[2] Liu Xiang-yu，Wang Ya-zhe，Yang Xiao-chun，et al. Facing the wireless sensor network streaming data compression technology [J]. Computer Science， 2007，34（ 2） ： 141-143.

[3] 趙潔， 湯寶平， 姚金寶， 盧得芳. 一種自適應最優化小波變換算法及應用[J]. 重慶大學學報.第31卷第9期.2008，09：1028-1033.

[4] 戴瓊海，付長軍，季向陽.壓縮感知研究[J].計算機學報.第34卷第3期. 2011，03：425-434.