數(shù)據(jù)壓縮算法研究

胡志鵬

摘 要 數(shù)據(jù)壓縮可以去除數(shù)據(jù)中的冗余信息，減少數(shù)據(jù)的存儲(chǔ)量，同時(shí)也可以減輕網(wǎng)絡(luò)負(fù)擔(dān)。本文介紹了目前最常用的幾種數(shù)據(jù)壓縮的方法，包括預(yù)測(cè)編碼技術(shù)、時(shí)間序列線性擬合技術(shù)、DCT變換、DWT變換和壓縮感知。

關(guān)鍵詞 數(shù)據(jù)壓縮 預(yù)測(cè)編碼 壓縮感知 小波變換

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A

0引言

數(shù)據(jù)壓縮技術(shù)一直是一個(gè)熱門(mén)研究領(lǐng)域，其作用是去除數(shù)據(jù)中存在的冗余信息，以不影響數(shù)據(jù)內(nèi)容為前提，盡量減小數(shù)據(jù)存儲(chǔ)大小。

1預(yù)測(cè)編碼技術(shù)

預(yù)測(cè)編碼技術(shù)根據(jù)信源存在的時(shí)空相關(guān)性這一特點(diǎn)去預(yù)測(cè)信源數(shù)據(jù)，然后用預(yù)測(cè)數(shù)據(jù)減去真實(shí)信源數(shù)據(jù)得到預(yù)測(cè)值，最后將差值進(jìn)行存儲(chǔ)，利用這種方法去除信源中的冗余信息，實(shí)現(xiàn)數(shù)據(jù)壓縮的目的。

預(yù)測(cè)是根據(jù)前n個(gè)測(cè)量參數(shù)，估計(jì)當(dāng)前的測(cè)量值。x0表示當(dāng)前測(cè)量值，表示估計(jì)值，同時(shí){%Zi|i=1，2，…，N}是預(yù)測(cè)系數(shù)，其中N是預(yù)測(cè)的階數(shù)。

預(yù)測(cè)估計(jì)值：

（1.1）

預(yù)測(cè)誤差：

（1.2）

測(cè)量的預(yù)測(cè)誤差記作MSE：

MSE=e2i （1.3）

預(yù)測(cè)多項(xiàng)式階數(shù)越高，預(yù)測(cè)準(zhǔn)確性越高，計(jì)算復(fù)雜性也急劇增加。

2時(shí)間序列線性擬合技術(shù)

數(shù)據(jù)在一段時(shí)間內(nèi)保持相對(duì)穩(wěn)定的某種趨勢(shì)，使得采樣數(shù)據(jù)構(gòu)成時(shí)間序列，可以通過(guò)構(gòu)建合適的時(shí)間序列數(shù)學(xué)模型得到近似的數(shù)據(jù)，使數(shù)據(jù)量少于原時(shí)間序列，達(dá)到數(shù)據(jù)壓縮的目的。

時(shí)間序列為：

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

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

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

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

（1.6）

得到回歸方程：

（1.7）

3小波變換

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

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

（2.1）

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

對(duì)于任意函數(shù)F（t）屬于L2（R）的連續(xù)小波變換為：

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）

基本小波函數(shù)的選擇取決于實(shí)際應(yīng)用，小波函數(shù)在幾何形狀必須是振蕩函數(shù)和迅速收斂的函數(shù)。尺度因子和平移因子的不同會(huì)給小波函數(shù)的幾何形狀帶來(lái)很大的變化。

4壓縮感知

對(duì)某一信號(hào) f 進(jìn)行采樣實(shí)際上就是將該信號(hào)同一系列波形進(jìn)行內(nèi)積運(yùn)算。例如：奈奎斯特采樣就是信號(hào) f 與一組頻率大于2 f 的脈沖信號(hào)的內(nèi)積。

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

壓縮感知采用波形數(shù)目遠(yuǎn)小于信號(hào)維數(shù)的采樣信號(hào)對(duì)信號(hào) f 進(jìn)行欠采樣。得到的信號(hào)采樣值的數(shù)目m遠(yuǎn)小于原始信號(hào) f 的維數(shù)n。因此壓縮感知在采樣的同時(shí)實(shí)現(xiàn)了對(duì)信號(hào)的壓縮。

壓縮感知將n維可壓縮信號(hào)x∈k通過(guò)采樣矩陣%O∈Cm，n（m<

y=%Ox （3.2）

如果信號(hào) f 在域是稀疏的，那么式（5）就可以寫(xiě)為

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

其中x為信號(hào) f 在%o域的系數(shù)，A=%O%o是一個(gè)m譶階的矩陣，稱(chēng)之為感知矩陣。

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

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

（3.4）

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

壓縮感知恢復(fù)算法的做法是對(duì)信號(hào)或其變換系數(shù)的非零元素個(gè)數(shù)進(jìn)行約束，通過(guò)l0范數(shù)最小化求解：

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

其中||x||0，是l0范數(shù)。

Donoho等利用l0范數(shù)代替l0范數(shù)，將（9）的非凸組合優(yōu)化問(wèn)題轉(zhuǎn)化為凸松弛問(wèn)題求解：

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

其中||x||0，是l1范數(shù)?；粉?（BasisPursuit，BP）方法將（10）中有約束的l1范數(shù)最小化問(wèn)題轉(zhuǎn)換為線性規(guī)劃問(wèn)題進(jìn)行求解。如果信號(hào)足夠稀疏，l1范數(shù)最小化方法能夠比較精確的恢復(fù)出原始信號(hào)。

5總結(jié)

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

參考文獻(xiàn)

[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] 趙潔， 湯寶平， 姚金寶， 盧得芳. 一種自適應(yīng)最優(yōu)化小波變換算法及應(yīng)用[J]. 重慶大學(xué)學(xué)報(bào).第31卷第9期.2008，09：1028-1033.

[4] 戴瓊海，付長(zhǎng)軍，季向陽(yáng).壓縮感知研究[J].計(jì)算機(jī)學(xué)報(bào).第34卷第3期. 2011，03：425-434.