文本压缩算法

《文本压缩》算法是:

三大类：预测编码、变换编码、统计编码

常用的解除相关性的措施是预测和变换，其实质都是进行序列的映射。

一般，预测编码有可能完全解除序列的相关性，但须确知序列的概率特性；变换编码一般只解除矢量内部的相关性，但它可有许多可供选择的变换方法，以适应不同的信源特性。

一、预测编码:

若有一个离散信号序列，序列中各离散信号之间有一定的关联性，则利用这个序列中若干个信号作为依据，对下一个信号进行预测，然后将实际的值与预测的值的差进行编码。

预测编码中典型的压缩算法有DPCM、ADPCM等，它们适合于声音、图像数据的压缩。

（1）DPCM中文术语为差分脉冲编码调制(differentialpulse code modulation的缩写)

利用样本与样本之间存在的信息冗余来进行编码的一种数据压缩技术

基本思想：根据过去的样本去估算下一个样本信号的幅度大小，这个值称为预测值，然后对实际信号值与预测值之差进行量化编码，从而就减少了表示每个样本信号的位数

它与脉冲编码调制(PCM)不同的是，PCM是直接对采样信号进行量化编码，而DPCM是对实际信号值与预测值之差进行量化编码，存储或者传送的是差值而不是幅度绝对值，这就降低了传送或存储的数据量。可适应大范围变化的输入信号。

差分脉冲编码调制(DPCM)的基本出发点就是对相邻样值的差值进行量化编码。由于此差值比较小，可以为其分配较少的比特数，进而起到了压缩数码率的目的。

（2）ADPCM的概念

ADPCM的中文术语为自适应差分脉冲编码调制(adaptive difference pulse code modulation的缩写)

综合了APCM的自适应特性和DPCM系统的差分特性，是一种性能比较好的波形编码技术

它的核心想法是：

利用自适应的思想改变量化阶的大小，即使用小的量化阶(step-size)去编码小的差值，使用大的量化阶去编码大的差值。

使用过去的样本值估算下一个输入样本的预测值，使实际样本值和预测值之间的差值总是最小。

二、变换编码

变换编码是指在发送端，先对信号进行映射变换，然后再针对变换后的信号进行量化和编码；在接受端，则先将收到的信号进行解码等操作，然后再进行反映射变换，以再现原始信号。变换编码是在变换域上解除相关性，以提高信息传输效率的。

变换编码中系统压缩数据有三个步骤，即映射变换、映射变换域采样和量化编码。

对于图像信源等相关性更强的信源，常采用基于正交变换的变换编码方法进行数据压缩。

变换编码中的关键技术在于正交变换。与预测编码一样，正交变换是通过消除信源序列中的相关性来达到数据压缩的。它们之间的区别在于预测编码是在空间域（或时间域）内进行的，而变换编码则是在变换域（或频率域）内进行的。

变换编码用到的算法：如离散傅里叶变换（DFT）、离散余弦变换（DCT）、沃尔什变换（WHT）等，其中性能较接近KL变换的是离散余弦变换（DCT），某些情况下，DCT能获得与KL变换相同的性能，因此DCT也被称为准最佳变换。

三、子带编码

子带编码是一种在频率域中进行数据压缩的算法。其指导思想是首先在发送端将图像信号在频率域分成若干子带，然后分别对这些子带信号进行频带搬移，将其转换成基带信号，再根据奈奎斯特定理对各基带信号进行取样、量化和编码，最后合并成为一个数据流进行传送。