发布时间 : 星期日 文章算术编码与哈夫曼编码更新完毕开始阅读
1 引言
1.1 数据压缩概念及技术分类
数据压缩，就是将信息的一种表示方式转换为另一种表示方式，信息的新的表示方式与原有表示方式相比较所含的信息量相同或是在可以承受的范围内有所损失，但是新的表示方式所用到的符号数量要比原有表示方式要尽可能的少。
数据压缩是必要的，不管是在生物系统中还是在人工系统中都存在数据压缩。尤其是处在这个信息爆炸的时代，怎样更有效的存储信息和传递信息对于文明进步的作用都是显而易见的。从不同视角看到的数据压缩的益处有：在通信信道上更快的传输信息，这就相应的减少了信道的占有时间，这可看作在时间上进行了压缩；在同一通信信道上并行的传输各种频率的互不干扰的信息，如xDSL技术在普通电话线上实现把低端频谱留给传统电话使用，把高端频谱留给上网用户使用，这可看作在频率域上进行了压缩；传输信号当然需要能量消耗，因此对数据进行压缩也就间接地减少了能量消耗，这可看作是在能量上进行了压缩；各种存储系统的存储空间都不是无限的，对数据进行压缩后，就可以在同样的存储空间存储更多的数据，这可看作是空间上的压缩。任何系统，尤其在活动时，都同时涉及到时间、空间和能量上的消耗，所以数据压缩就是从这三方面同时进行了压缩，这样就使得系统更加的有效的运行。
既然数据压缩是必要的，那么就要考虑从哪些方面来说数据可以被压缩，一般可从以下几方面考察：
一是，数据中通常存在着多余成分，即允余度。例如，存储在计算机上的一份文本文件，内容可假设是一部英文小说，可以想象，26个英文字母重复出现，各个字母出现的频率有大有小，而且不仅字母重复出现，字母组成的单词也重复出现，进一步，某些字母总是在某单词的一定位置上以高概率重复出现，某些单词也总是在一个特定句式的特定位置以高概率重复出现等等，计算机是以二进制形式存储文件的，那么用二进制符号怎样有效的表示这个由英文字符、各种标点符号和控制字符组成的文本文件就是怎样对数据进行压缩的问题，而压缩显然就要利用这些允余度的不同类型，例如，我们赋予高概率字符以相对少的二进制位数，赋予低概率字符以相对多的的二进制位数，那么这样表示后所得的总的二进制位数肯定比不考虑各个字符出现概率，而给不同字符按照ASCII码分配二进制位数所得的总的二进制位数要少很多。
二是，数据中的各个部分前后之间总是存在着相关性。例如，电视上显示的动态画面，实际上是由离散的不同画面(帧)组成的，之所以看似是连续的只是因为帧的播放速度超过了人类的反应速度并且利用了人类的视觉暂留效应，但为使
1
画面看似连续，不仅要利用人类本身的生物特性，还要保证帧之间的过渡是相对平滑的，也就是相邻两帧之间只有动态上的细微变化，而大部分画面在两帧之间是相同的，很显然，这种相关性是可以很好的加以利用的。
三是，对于人而言，我们的感受器只能接受外界中很小一部分的信息。例如，人眼只能感受阳光中的可见光，而对紫外光不可见，但一些昆虫如蜜蜂却能感受紫外光，如果人为的屏蔽掉紫外光部分，对人眼而言，我们并不能对屏蔽前与屏蔽后的阳光加以区分，但蜜蜂就不同了，可能就因为无法感受紫外光，就找不到花蜜了，所以，对于人而言，并不是数据中所有的信息对我们都是必要的，不必要的部分就可以屏蔽掉。
数据压缩可分为无损压缩和有损压缩，下面分别简要的介绍可逆压缩和不可逆压缩：
可逆压缩，是利用数据的统计特性，即数据的允余度进行压缩的一类方法，允余度的去除或是减少并不影响原始数据无失真的恢复，即是一个可逆的过程。但从编码效率上来讲，可逆压缩受到待编码数据本身的信息熵的限制，无法达到更高的编码效率。也就是由于这样的限制，仅使用可逆压缩方法是不可能解决多媒体的存储和传输的所有问题的，因此，这类方法一般适用于在压缩过程中不允许有丝毫损失的情况，如在计算机磁盘上存储文件，数据通信等领域。
常用的可逆压缩方法有：哈夫曼编码、算术编码、LZW编码等。
不可逆压缩，是利用人类对图像或声波中的某些频率成分的不敏感特性，允许压缩过程中损失一定的信息，虽然不能完全恢复原始数据，但是所损失的部分对人类理解理解原始数据的影响可承受，好处就是与可逆压缩相比，能够获得更高的编码效率，因此，广泛适用与语音、图像和视频数据的压缩。
不可逆压缩的方法有很多，这里不列举。
1.2 统计编码的数学准备
统计编码某种程度上与可逆压缩同义，因此可混用。在1.1节中，我们用到了允余度和信息熵的概念，这两个概念都由信息论的开创者香农(Claude E.shannon)首次提出，因此这一小节主要介绍信息论中的一些概念，这些概念有助于我们更好的理解统计编码。
信源空间概念： 信源空间表示为：
X:a1a2p(a2)a3??amp(a3)??p(am)P(X):p(a1)
2
其中，0?p(ai)?1(i?1,2,?,m) ?p(am)?1
i?1m(1)符号ai代表信源可能发出的符号，p(ai)发符号ai的先验概率。
(2)用信源空间表示信源X的必要前提，就是信源可能发出的各种不同符号的概率先验可知，或事先可测定，测定信源的概率空间是构建信源空间的关键。
信源符号的自信息量：
数学上定义为：I(ai)??logrp(ai) 说明：
(1) ai为信源所发符号，p(ai)为信源发符号ai的概率，概率越大，不确定性越
小，概率越小，不确定性越大。
(2) 而自信息量I(ai)既表示收信者确切无误收到信源符号ai后，从ai中获得的信息量，同时也表示收到符号ai之前，收信者对于信源所发符号ai存在的不确定性的度量。
(3) 自信息量I(ai)的单位取决于对数的底，即r值，若r=2,则自信息量的单位为比特(bit),不指明正整数r具体值时，则自信息量的单位为r进制信息单位。
信源的信息熵：
数学上定义为： r进制形式 Hr(X)???p(ai)logrp(ai)
i?1mm 2进制形式 H2(X)???p(ai)log2p(ai) 说明：
i?1(1) 运用对数换底公式，可得：Hr(X)?H2(X)log2r
(2) 信息熵作为信源X的总体信息测度，表示信源每发一个符号所能提供的平均信息量，同时也表示收信者在接收到符号之前，对信源X存在的平均不确定性的度量。
最大离散熵定理：
H(p1,p2,?,pm)?Hmax(p1,p2?pm)
m11111其中，Hmax(p1,p2,?,pm)?H(,,?,)???log2?log2m 说明：
mmmmi?1m(1) 熵函数H(p1,p2,?,pm)是信源X的信息熵的另一种表示方法，其中pi代表
p(ai)。
3
(2) 熵函数具有上凸性，所以熵函数具有极大值，此极大值就是其最大值Hmax，最大值在pi=1/m时，即信源符号等概率分布时取得。
(3) 离散信源信息熵的最大值只取决于信源的符号种类数m值，m值越大，其信息熵的最大值越大。
信源X所含有的允余度：
??Hmax(X)?H(X)?log2m?H(X) 说明：
，允余度??0，(1) 信源符号等概率分布时因此离散独立信源的允余度隐含在信源符号的非等概率分布之中。也就是说，只要信源符号不是等概率分布，就存在能够对信源数据进行数据压缩的可能性，允余度的存在是能够进行统计编码的前提。
对信源编码所得平均码长：
n?n1p(a1)?n2p(a2)???nmp(am)??nip(ai) 说明：
i?1m(1) ni是信源符号ai的码字长度。
(2) 平均码长n是各个信源符号的码字长度ni在信源X的概率空间 ?p(a1),p(a2),?,p(am)?上的统计平均值。
编码效率：
??H(X)n 说明：
(1) ?值越大，表示每一个码符号所携带的平均信息量越多，反之，就越少。 (2) 对于给定的待编码信源，由于各个信源符号的概率已经经过统计确定，所以 信源熵的值也就固定不变了，所以编码效率的高低只取决于平均码长n，所 以提高信源编码的效率，就是要设法减小平均码长n。
平均码长n存在下限：
n?Hr(X) 说明：
(1) 在证明过程中，得到：当且仅当对所有i(i?1,2,?,m),都有p(ai)?1rni时，
n?Hr(X)才成立，其中ni是信源符号ai的码字长度。
(2) 单义可译码的平均码长n，再小也不会小于信源熵。所以一旦信源确定，其信源熵也就随之确定，平均码长的下限值也随之确定，在这个范畴内编码效率不可能超过1（100%），要想进一步提高编码效率，只有通过改变信源本身才能做到。
4