文档介绍：第四章无损数据压缩
本章学习目标
掌握数据压缩的基本概念
掌握几种常见的数据压缩方法
香农-范诺编码
算术编码
RLE编码
词典编码
霍夫曼编码
数据压缩基本概念
数据压缩基础
无损压缩
压缩后的数据进行重构(或者叫做还原,解压缩),重构后的数据与原来的数据完全相同;
无损压缩用于要求重构的信号与原始信号完全一致的场合。如,磁盘文件的压缩。
有损压缩
压缩后的数据进行重构,重构后的数据与原来的数据有所不同,但不影响人对原始资料表达的信息造成误解。
有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。如,图像、声音的压缩。
主要介绍目前用得最多和技术最成熟的无损压缩编码技术,包括:
香农-范诺和霍夫曼编码
算术编码
RLE编码
词典编码
数据压缩基本概念
无损数据压缩
无损压缩
数据压缩方法
基本概念:熵
编码器
信源(消息集)
X={x1,…,xn}
编码输出集
Z={z1,…,zn}
符号集Am={a1,…,am}
熵(Entropy)的概念
熵是信息量的度量方法,它表示某一事件出现的消息越多,事件发生的可能性就越小,数学上就是概率越小。
某个事件的信息量用表示, 其中Pi为第i个事件的概率,0<Pi1。
如:一幅用256级灰度表示的图像,如果每一个像素点灰度的概率均为pi=1/256,编码每一个像素就需要8位。 log2(1/ pi)= log2256=8
数据压缩方法
香农-范诺
按照香农(Shannon)的理论,信源S的熵定义为
即信源X发出的xi共n个随机事件的自信息统计平均(数学期望)
其含义:信源X发出任意一个随机变量的平均信息量。其中pi是符号Si在S中出现的概率;log2(1/ pi)表示包含在si中的信息量,也就是编码si所需要的位数。
Shannon(1948年)、Fano(1949年)
采用从上到下的方法进行编码
;
,每部分具有近似相同的次数;
数据压缩方法
香农-范诺
A 15
B 7
C 7
D 6
E 5
按符号出现的频率或概率排序A、B、C、D、E;
按递归方法分成两部分,每部分具有近似相同的次数;
总位数:2×15+2×7+2×7+3×6+3×5=91
压缩比:120/91=:1
1
A
B
C
D
E
0
0
0
0
1
1
1
数据压缩方法
香农-范诺举例
例:有一幅40个像素组成的灰度图象,灰度共有5级,分别用符号A,B,C,D,E表示,如果用3个位表示5个等级的灰度值,则编码这幅图像总共需120位。
霍夫曼(Huffman) 1952年,从下到上的编码方法。
,根据概率大小由大到小顺序对符号进行排序

,分别进行编码
霍夫曼码的码长虽然是可变的,但却不需要另外附加同步代码。
几个问题值得注意:
;
,因此很难随意查找或调用压缩文件中间的内容,然后再译码;
。
数据压缩方法
霍夫曼编码
A()
B()
C()
D()
E()
0
1
0
1
0
1
0
1
数据压缩方法
霍夫曼编码举例1
,根据概率大小按由大到小的顺序对符号进行排序;

,直到形成一棵完整的数
(0或1)