数据压缩基础
主要内容
z数据压缩概述
z经典数据压缩理论
z香农－范诺与霍夫曼编码z算术编码z行程编码z词典编码z预测编码z
变换编码
2
什么是数据压缩
•少的数码表示信源所发出的信号
信源
信源信道编码编码信道
信宿
信源信道译码译码
3
数据压缩技术的分类
无损压缩是指使用压缩后的数据进行重构(或者
叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。
有损压缩是指使用压缩后的数据进行重构，重构
后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。
5
熵（Entropy）
z
事件集合（样本空间）X中每个事件的自信息量是定义在这个样本空间上的一个随机变量，所以我们要研究它的统计特性。其数学期望为：
H(X)=
(x)∗I(x)=−x∑p∈X
∑p(x)∗logp(x)
x∈X
z
H(X)表明了集合X中随机事件的平均不确定性，或者说平均信息量。
z
称H(X)为一阶信息熵或者简称为熵(Entropy)
7
统计编码方法
1 霍夫曼编码
这种编码方法是根据信源数据符号发生的概率进行编码的。思想：在信源数据中出现概率越大的符号，编码以后相应的码长越短；出现概率越小的符号，其码长越长。（理论最佳）。
设输入编码为，其频率分
}X={x2,x2,x3,x4,x,x布分别为P(x1)=0.4 ，P(x)=0.1，P(x1)=0.3，P(x5634)
=0.1，P(x5)=0.06，P(x6)=0.04。求其最佳霍夫曼编码
W={w1,w2,w3,w4,w5,w6}
8
霍夫曼编码算法基于一种称为“编码树”（）的技术。算法步骤如下：
（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。
（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。
（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。
（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。
在上述工作完毕之后，从最后两个概率开始逐步向前进行编码。对于概率大的消息赋予0，小的赋予1。
9
画出霍夫曼树，给出霍夫曼编码并计算熵和平均码长。
12
13
14
霍夫曼编码的特点：
(1) 概率为’1’，小概率为’0’，也可相反）
(2) 当概率分布很不均匀时，霍夫曼编码的效率就高，反之，编码效率低。
(3) 霍夫曼编码必须先计算出数据概率形成编码后，才能对数据进行编码，必须通过查表方法建立对应关系。
15
3算术编码
候不能得到最佳的压缩效果。
与前述的变长编码不同，算术编码生的是非块码。算术编码给整个信源符号序列分配一个单一的算术码字。这个码字本身定义了一个介于0和1之间的实数间隔。
16
Arithmetic coding encoder
19
4 行程编码基本方法（RLE）（run length）
当在数据集中存在相同数据连续出现时，行程编码是一种大胆有效的方法。
例如，对于数据
d=5 5 5 5 5 5 5 19 19 19 19 19 19 19 19 19 19 19 19 0 0 0 0 0 0 0 0 7 9 9 9 9 9 9
通过行程编码后为（5，7）（19，12）（0，8）（7，1）（9，6）。
20
对于二值图像，采用行程编码的编码效率很高。
D=0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 ，（43bit）
采用行程编码可表示为（7，8，8，2，
如果每个行程长度由3位表示：
( [***********]）（18bit），7）
211
数据压缩基础
主要内容
z数据压缩概述
z经典数据压缩理论
z香农－范诺与霍夫曼编码z算术编码z行程编码z词典编码z预测编码z
变换编码
2
什么是数据压缩
•少的数码表示信源所发出的信号
信源
信源信道编码编码信道
信宿
信源信道译码译码
3
数据压缩技术的分类
无损压缩是指使用压缩后的数据进行重构(或者
叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。
有损压缩是指使用压缩后的数据进行重构，重构
后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。
5
熵（Entropy）
z
事件集合（样本空间）X中每个事件的自信息量是定义在这个样本空间上的一个随机变量，所以我们要研究它的统计特性。其数学期望为：
H(X)=
(x)∗I(x)=−x∑p∈X
∑p(x)∗logp(x)
x∈X
z
H(X)表明了集合X中随机事件的平均不确定性，或者说平均信息量。
z
称H(X)为一阶信息熵或者简称为熵(Entropy)
7
统计编码方法
1 霍夫曼编码
这种编码方法是根据信源数据符号发生的概率进行编码的。思想：在信源数据中出现概率越大的符号，编码以后相应的码长越短；出现概率越小的符号，其码长越长。（理论最佳）。
设输入编码为，其频率分
}X={x2,x2,x3,x4,x,x布分别为P(x1)=0.4 ，P(x)=0.1，P(x1)=0.3，P(x5634)
=0.1，P(x5)=0.06，P(x6)=0.04。求其最佳霍夫曼编码
W={w1,w2,w3,w4,w5,w6}
8
霍夫曼编码算法基于一种称为“编码树”（）的技术。算法步骤如下：
（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。
（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。
（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。
（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。
在上述工作完毕之后，从最后两个概率开始逐步向前进行编码。对于概率大的消息赋予0，小的赋予1。
9
画出霍夫曼树，给出霍夫曼编码并计算熵和平均码长。
12
13
14
霍夫曼编码的特点：
(1) 概率为’1’，小概率为’0’，也可相反）
(2) 当概率分布很不均匀时，霍夫曼编码的效率就高，反之，编码效率低。
(3) 霍夫曼编码必须先计算出数据概率形成编码后，才能对数据进行编码，必须通过查表方法建立对应关系。
15
3算术编码
候不能得到最佳的压缩效果。
与前述的变长编码不同，算术编码生的是非块码。算术编码给整个信源符号序列分配一个单一的算术码字。这个码字本身定义了一个介于0和1之间的实数间隔。
16
Arithmetic coding encoder
19
4 行程编码基本方法（RLE）（run length）
当在数据集中存在相同数据连续出现时，行程编码是一种大胆有效的方法。
例如，对于数据
d=5 5 5 5 5 5 5 19 19 19 19 19 19 19 19 19 19 19 19 0 0 0 0 0 0 0 0 7 9 9 9 9 9 9
通过行程编码后为（5，7）（19，12）（0，8）（7，1）（9，6）。
20
对于二值图像，采用行程编码的编码效率很高。
D=0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 ，（43bit）
采用行程编码可表示为（7，8，8，2，
如果每个行程长度由3位表示：
( [***********]）（18bit），7）
211