文档介绍：ch数据无损压缩演示(yǎnshì)文稿
1页，共40页，星期日。
优选ch数据(shùjù)无损压缩
2页，共40页，星期日。
第2章 数据(shùjù)无损压缩目录
数据(shùjù)的冗余
举例：假设X={a,b,c}是由3个事件构成的集合，p(a)=，p(b)=，p(b)=, b和c出现的概率，这些事件的信息量分别为，
I(a)=log2(1/)=1 sh
I(b)=log2(1/)=2 sh
I(c)=log2(1/)=2 sh
一个等概率事件的集合，每个事件的信息量等于该集合的决策量
9页，共40页，星期日。
数据(shùjù)的冗余(续3)
熵(entropy)
按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量(mean information content)
用数学(shùxué)表示为
10页，共40页，星期日。
数据(shùjù)的冗余(续4)
数据(shùjù)的冗余量
11页，共40页，星期日。
统计(tǒngjì)编码
统计编码
给已知统计信息的符号分配代码的数据无损压缩方法
编码方法
香农-范诺编码
霍夫曼编码
算术编码
编码特性
香农-范诺编码和霍夫曼编码的原理(yuánlǐ)相同，都是根据符号集中各个符号出现的频繁程度来编码，出现次数越多的符号，给它分配的代码位数越少
算术编码使用0和1之间的实数的间隔长度代表概率大小，概率越大间隔越长，编码效率可接近于熵
12页，共40页，星期日。
统计(tǒngjì)编码——香农-范诺编码
香农-范诺编码(Shannon–Fano coding)
在香农的源编码理论中，熵的大小表示非冗余的不可压缩(yā suō)的信息量
在计算熵时，如果对数的底数用2，熵的单位就用“香农(Sh)”，也称“位(bit)” 。“位”是1948年Shannon首次使用的术语。例如
最早阐述和实现“从上到下”的熵编码方法的人是Shannon(1948年)和Fano(1949年)，因此称为香农-范诺(Shannon- Fano)编码法
13页，共40页，星期日。
香农-范诺编码(biān mǎ)
香农-范诺编码举例
有一幅40个像素组成的灰度图像，灰度共有5级，分别用符号A，B，C，D和E表示。40个像素中出现灰度A的像素数有15个，出现灰度B的像素数有7个，出现灰度C的像素数有7个，其余(qíyú)情况见表2-1
(1) 计算该图像可能获得的压缩比的理论值
(2) 对5个符号进行编码
(3) 计算该图像可能获得的压缩比的实际值
表2-1 符号在图像中出现的数目
符号
A
B
C
D
E
出现的次数
15
7
7
6
5
出现的概率
15/40
7/40
7/40
6/40
5/40
14页，共40页，星期日。
香农-范诺编码(biān mǎ)(续1)
(1) 压缩比的理论值
按照常规的编码方法，表示5个符号最少需要3位，如用000表示A，001表示B，…，100表示E，其余3个代码 (101，110，111)不用。这就意味每个像素用3位，编码这幅图像总共(zǒnggòng)需要120位。按照香农理论，这幅图像的熵为
这个数值表明，每个符号不需要用3位构成的代码表示，，，因此在理论上，这幅图像的的压缩比为120:≈:1，实际上就是3:≈
15页，共40页，星期日。
香农-范诺编码(biān mǎ)(续2)
(2) 符号编码
对每个符号进行编码时采用“从上到下”的方法。首先按照符号出现的频度或概率(gàilǜ)排序，如A，B，C，D和E，见表2-2。然后使用递归方法分成两个部分，每一部分具有近似相同的次数，如图2-1所示
16页，共40页，星期日。
香农-范诺编码(biān mǎ)(续3)
（3）压缩比的实际值
按照这种方法(fāngfǎ)进行编码需要的总位数为30+14+14+18+15＝91，实际的压缩比为120:91≈ : 1
图2-1 香农-范诺算法编码举例
17页，共40页，星期日。
统计(tǒngjì)编码——霍夫曼编码
霍夫曼编码(Huffman coding)
霍夫曼(. Huffman)在1952年提出和描述的“从下到上”的熵编码