数据压缩算法研究

胡志鹏

摘 要 数据压缩可以去除数据中的冗余信息，减少数据的存储量，同时也可以减轻网络负担。本文介绍了目前最常用的几种数据压缩的方法，包括预测编码技术、时间序列线性拟合技术、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.