第三章：Huffman编码 信源概率模型已知的Huffman编码 信源概率模型未知的Huffman编码 Huffman编码中的码字设计

Presentation on theme: "第三章：Huffman编码 信源概率模型已知的Huffman编码 信源概率模型未知的Huffman编码 Huffman编码中的码字设计"— Presentation transcript:

1 第三章：Huffman编码 信源概率模型已知的Huffman编码 信源概率模型未知的Huffman编码 Huffman编码中的码字设计
应用：文本、图像、语音 对离散无记忆信源，其冗余度表现在各信源符号出现的概率不相等。通过去除或减少这种冗余，达到数据压缩的目的。

2 Shannon-Fano 编码 第一个基于Shannon理论的编码 算法 次优码（其研究生David Huffman 改进成了最优码）
以空码开始 计算所有符号的频率/概率 对所有符号按其概率排序 将符号集合划为为两个概率差异最小集合 在第一个集合的码字前加‘0’，在第二个集合的码字前加‘1’ 对划分得到的两个子集递归编码，知道每个集合不能被再划分

3 Shannon-Fano 编码 (2) a b c d e f a b c d e f 1 1 9 8 6 5 4 2 9 8 6 5 4
1 a b c d e f 9 8 6 5 4 2 a b 9 8 c d e f 6 5 4 2 1

4 Shannon-Fano 编码 (3) a b c d e f a b c d e f 1 1 1 1 1 9 8 6 5 4 2 9 8
1 1 1 1 a b c d e f 9 8 6 5 4 2 a b 9 8 c d e f 6 5 4 2 1

5 Shannon-Fano 编码 (4) a b c d e f c d e f a b 1 1 00 01 1 1 1 1 9 8 6 5
2 1 c d e f 6 5 4 2 1 a b 9 8

6 Shannon-Fano 编码 (5) a b c d e f c d e f a b 1 1 00 01 1 1 1 1 9 8 6 5
4 2 c d e f 6 5 4 2 1 1 a b 9 8

7 Shannon-Fano 编码 (6) a b c d e f a b c d e f 1 1 1 00 01 10 10 11 11 9
8 6 5 4 2 1 1 1 a b c d e f 9 8 6 5 4 2

8 Shannon-Fano 编码 (7) a b c d e f c d a b e f 1 1 1 1 00 01 10 10 11 11
9 8 6 5 4 2 1 1 c d 6 5 1 1 a b e f 9 8 4 2

9 Shannon-Fano 编码 (8) a b c d e f a b e f c d 1 1 1 1 00 01 100 101 11
9 8 6 5 4 2 1 1 1 a b e f 1 9 8 4 2 c d 6 5

10 Shannon-Fano 编码 (9) a b c d e f e f a b c d 1 1 1 1 00 01 100 101 11
8 6 5 4 2 1 1 1 e f 4 2 a b 1 9 8 c d 6 5

11 Shannon-Fano 编码 (10) a b c d e f a b c d e f 1 1 1 1 1 00 01 100 101
110 111 a b c d e f 9 8 6 5 4 2 1 1 1 a b 1 1 9 8 c d e f 6 5 4 2

12 Huffman编码 由David Huffman提出：Robert Fano的信息论作业 Shannon-Fano 编码的改进
对离散无记忆信源，其冗余度表现在各信源符号出现的概率不相等。通过去除或减少这种冗余，达到数据压缩的目的。 David. Huffman. A Method for the Construction of Minimum Redundancy Codes. Proceeding of the IRE, 40(9):

13 最优前缀码 最优码的一些重要性质 证明 则 !!! 这与最优码相矛盾 !!! 出现频率越高的符号的码长应该越短
出现频率最低的两个符号其长度应该相等 证明 假设相反—该编码肯定是次优的 假设相反 令X, Y 表示出现频率最低的两个符号，且 |code(X)| = k, |code(Y)| = k+1 则 由于是前缀码，code(X) 不能为code(Y)的前缀 同时，所有其他的码字更短  去掉|code(Y)| 的最后一个比特将产生一个新的、更短的前缀码 !!! 这与最优码相矛盾 !!!

14 Huffman Coding by Example
初始化：为每个字符创建一个集合 字母 码字 概率 集合 集合的概率 a 0.2 b 0.4 c d 0.1 e 字母 码字 概率 集合 集合的概率 a 0.2 b 0.4 c d 0.1 e

15 Huffman Coding by Example
根据集合的概率对集合进行排序（升序） 字母 码字 概率 集合 集合的概率 a 0.2 d 0.1 b 0.4 e c 字母 码字 概率 集合 集合的概率 a 0.2 b 0.4 c d 0.1 e

16 Huffman Coding by Example
对最前面集合的字母的码字中插入前缀 ‘1’ 字母 码字 概率 集合 集合的概率 a 0.2 d 0.1 b 0.4 e c 1 字母 码字 概率 集合 集合的概率 a 0.2 d 0.1 b 0.4 e c

17 Huffman Coding by Example
对第二个集合中字母的码字中插入前缀‘0’ 字母 码字 概率 集合 集合的概率 a 0.2 d 0.1 b 0.4 e c 1 字母 码字 概率 集合 集合的概率 a 0.2 d 0.1 b 0.4 e c 1

18 Huffman Coding by Example
合并最前面的两个集合 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 1 0.1 e 字母 码字 概率 集合 集合的概率 a 0.2 d 0.1 b 0.4 e c 1

19 Huffman Coding by Example
根据集合的概率对集合进行排序（升序） 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 1 0.1 e

20 Huffman Coding by Example
对最前面集合的字母的码字中插入前缀 ‘1’ 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 1 0.1 e 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 11 0.1 e 10

21 Huffman Coding by Example
对第二个集合中字母的码字中插入前缀‘0’ 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 11 0.1 e 10 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 11 0.1 e 10

22 Huffman Coding by Example
合并前两个集合 字母 码字 概率 集合 集合的概率 a 0.2 dea 0.4 b c d 11 0.1 e 10 字母 码字 概率 集合 集合的概率 a 0.2 de b 0.4 c d 11 0.1 e 10

23 Huffman Coding by Example
根据集合的概率对集合进行排序（升序） 字母 码字 概率 集合 集合的概率 a 0.2 dea 0.4 b c d 11 0.1 e 10 字母 码字 概率 集合 集合的概率 a 0.2 c b 0.4 dea d 11 0.1 e 10

24 Huffman Coding by Example
对最前面集合的字母的码字中插入前缀 ‘1’ 字母 码字 概率 集合 集合的概率 a 0.2 c b 0.4 dea d 11 0.1 e 10 字母 码字 概率 集合 集合的概率 a 0.2 c b 0.4 dea 1 d 11 0.1 e 10

25 Huffman Coding by Example
对第二个集合中字母的码字中插入前缀‘0’ 字母 码字 概率 集合 集合的概率 a 0.2 c b 0.4 dea 1 d 11 0.1 e 10 字母 码字 概率 集合 集合的概率 a 00 0.2 c b 0.4 dea 1 d 011 0.1 e 001

26 Huffman Coding by Example
合并前两个集合 字母 码字 概率 集合 集合的概率 a 00 0.2 cdea 0.6 b 0.4 c 1 d 011 0.1 e 010 字母 码字 概率 集合 集合的概率 a 00 0.2 c b 0.4 dea 1 d 011 0.1 e 010

27 Huffman Coding by Example
根据集合的概率对集合进行排序（升序） 字母 码字 概率 集合 集合的概率 a 00 0.2 b 0.4 cdea 0.6 c 1 d 011 0.1 e 010 字母 码字 概率 集合 集合的概率 a 00 0.2 cdea 0.6 b 0.4 c 1 d 011 0.1 e 010

28 Huffman Coding by Example
对最前面集合的字母的码字中插入前缀 ‘1’ 字母 码字 概率 集合 集合的概率 a 00 0.2 b 0.4 cdea 0.6 c 1 d 011 0.1 e 010 字母 码字 概率 集合 集合的概率 a 00 0.2 b 0.4 1 cdea 0.6 c d 011 0.1 e 010

29 Huffman Coding by Example
对第二个集合中字母的码字中插入前缀‘0’ 字母 码字 概率 集合 集合的概率 a 00 0.2 b 0.4 1 cdea 0.6 c d 011 0.1 e 010 字母 码字 概率 集合 集合的概率 a 000 0.2 b 0.4 1 cdea 0.6 c 01 d 0011 0.1 e 0010

30 Huffman Coding by Example
合并前两个集合 字母 码字 概率 集合 集合的概率 a 000 0.2 b 0.4 1 cdea 0.6 c 01 d 0011 0.1 e 0010 字母 码字 概率 集合 集合的概率 a 000 0.2 abcde 1.0 b 1 0.4 c 01 d 0011 0.1 e 0010 The END

31 例：总结 平均码长 l = 0.4x x x x x4 = 2.2 bits/symbol 熵 H = s=a..eP(s) log2P(s) = bits/symbol 冗余 l - H = bits/symbol

32 Huffman 树 b c a e d 1 字母 码字 a 000 b 1 c 01 d 0011 e 0010 1 1 1 0.4 0.2
1 字母 码字 a 000 b 1 c 01 d 0011 e 0010 b 1 0.4 c 1 0.2 Huffman: 第一次在数据结构中讲二叉树的时候 为什么压缩领域中的编码方法总和二叉树联系在一起呢？原因非常简单，回忆一下我们介绍过的“前缀编码”：为了使用不固定的码长表示单个字符，编码必须符合“前缀编码”的要求，即较短的编码决不能是较长编码的前缀。要构造符合这一要求的二进制编码体系，二叉树是最理想的选择。 a 1 0.2 e d 0.1 0.1

33 构建Huffman树 b c a e d 字母 码字 a b c d 1 e 字母 码字 a b c d e 1 0.4 0.2 0.2
字母 码字 a b c d e b 0.4 c 0.2 a 1 0.2 0.2 e d 0.1 0.1

34 构建Huffman树 (2) b c a e d 字母 码字 a b c d 11 e 10 字母 码字 a b c d 1 e 1 1
b c d 11 e 10 字母 码字 a b c d 1 e b 0.4 1 0.4 c 0.2 a 1 0.2 0.2 e d 0.1 0.1

35 构建Huffman树 (3) b c a e d 字母 码字 a b c d 11 e 10 字母 码字 a 00 b c 1 d 011
b c d 11 e 10 字母 码字 a 00 b c 1 d 011 e 010 1 0.6 b 0.4 c 1 0.4 0.2 a 1 0.2 0.2 e d 0.1 0.1

36 构建Huffman树 (4) a b e c d 1 字母 码字 a 00 b c 1 d 011 e 010 字母 码字 a 000 b
1 0.1 0.2 0.4 0.6 1.0 字母 码字 a 00 b c 1 d 011 e 010 字母 码字 a 000 b 1 c 01 d 0011 e 0010

37 另一棵Huffman树 b a c e d 字母 码字 a b c d e 字母 码字 a b c d 1 e 1 0.4 0.2 0.2
b 0.4 1 0.2 a c e d 0.2 0.2 0.1 0.1

38 另一棵Huffman树 (2) b a c e d 字母 码字 a b c 1 d e 字母 码字 a b c d 1 e 1 1 0.4
b c 1 d e 字母 码字 a b c d 1 e b 0.4 1 0.4 1 0.2 a c e d 0.2 0.2 0.1 0.1

39 另一棵Huffman树 (3) b a c e d 字母 码字 a 00 b c 01 d 11 e 10 字母 码字 a b c 1 d
b c 1 d e 0.6 1 b 0.4 1 1 0.4 0.2 a c e d 0.2 0.2 0.1 0.1

40 另一棵Huffman树 (4) b e d 0.1 0.4 1 0.2 a c 0.6 字母 码字 a 00 b c 01 d 11 e 10 字母 码字 a 000 b 1 c 001 d 011 e 010 平均码长 l = 0.4x1 + ( )x3= 2.2 bits/symbol

41 再一棵Huffman树 b e d 0.1 0.4 1 0.2 a c 0.6 字母 码字 a 00 b 11 c 01 d 101 e 100 平均码长 l = 0.4x2+ ( )x2 + ( )x3= 2.2 bits/symbol

42 最小方差Huffman树 Huffman编码不惟一 我们应该选择哪一个呢？ 为什么？ 怎样达到？ 但所有编码的平均码长相同
答案：方差最小者为佳（码字长度方差最小) 即高度最小的树 为什么？ 编码流中的编码变化最小 怎样达到？ 在排序时，将较小的集合（元素数目少）尽可能放在上面 也可以将新合并的集合尽可能放在下面（即认为它们的码长应该更短一些）

43 最小方差Huffman树 (2) 码字长度的方差 ：长度 与平均码长 之差的平方的数学期望，即 编码一码字长度方差： a b e c d 1
码字长度的方差 ：长度 与平均码长 之差的平方的数学期望，即 编码一码字长度方差： 合并后的新符号排在其它相同概率符号的前面 a b e c d 1 0.1 0.2 0.4 0.6 1.0

44 最小方差Huffman树 (2) 编码二码字长度方差： 编码三码字长度方差： b e d a c
0.1 0.4 1 0.2 a c 0.6 编码二码字长度方差： 编码三码字长度方差： 采用第三种编码方法：码长变化较小（比较接近于平均码长） 第一种方法编出的5个码字有4种不同的码长； 第三种方法编出的码长只有两种不同的码长； 显然，第三 种编码方法更简单、更容易实现。 b e d 0.1 0.4 1 0.2 a c 0.6 合并后的新符号排在其它相同概率符号的前面

45 最小方差Huffman树 (3) a b e c d 1 0.1 0.2 0.4 0.6 1.0 由于码位要以固定的速率传输，所以编码器要用缓冲器平滑比特产生率的变化。码字的方差越大，码位进入缓冲器的速率越不稳定，因而编码器需要的缓冲器也越大 例：假设传输字符的速率固定，如10,000字符/秒，平均码长为2.2 bits/字符，则接收方每秒将平均收到22,000比特 几秒内一直产生包含a4,a5的字符串 采用第一种编码方式，这样产生的比特率为40,000比特/秒，缓冲区每秒需保存18,000比特 采用第三种编码方式，比特率为30,000比特/秒，缓冲区每秒需保存8,000比特 几秒内一直产生包含a1的字符串 采用第一种编码方式，这样产生的比特率为10,000比特/秒，传输带宽浪费12,000比特/秒 采用第三种编码方式，比特率为20,000比特/秒，传输带宽浪费2000比特/秒 方差大的代码将导致编码器的输出码率不断变化 由于比特产生率会在22,000比特/秒，编码器的输出通常被送到缓冲区，以平滑比特产生率的变化。但是缓冲区的大小总是固定的，而码字大的变化对使得缓冲区设计变得更难 b e d 0.1 0.4 1 0.2 a c 0.6

46 自适应Huffman编码 Huffman编码需要各符号的概率。概率来源： 静态概率模型 ：根据训练数据得到，然后不同信源利用同一个概率表
半自适应统计模型： 必须传送Huffman码表和压缩流 需2遍扫描 但在很多情况下不实用：如压缩网络传输 自适应/动态概率模型： 1遍扫描 开始时认为是等概率 根据前k (k = 1, 2, …)个符号统计重新产生码字并编码第k+1st 个字符 Unix系统对程序的压缩：基于单词的自适应Huffman编码 在实际中太昂贵

47 Huffman解码 在开始压缩之前，编码器必须根据符号的概率（或出现的频率）确定码字
解码器利用这些信息对压缩流进行解码，所以应该将这些信息也写入压缩流中，以便解码器能解码该压缩流 变长码：不好，因为码长不同 写入频率/概率：将频率/概率标定为整数，然后解码器利用该频率信息构造Huffman树通常只会在压缩流中增加几百字节 写入Huffman树：比只写频率花费的字节数更多

48 Huffman解码 一. 比特串行解码（固定输入比特率——可变输出符号率(假定二进制码树在解码器端可得)
1. 逐个比特读入输入压缩流，并遍历树，直到到达一个叶节点。 2. 输入流的每个比特用过后即丢弃。当到达叶节点时，Huffman解码器输出叶节点处的符号。即完成该符号的解码。 3. 重复步骤1和2，直到所有的输入都解完。 由于所有码字长度不同，解码比特率对所有符号并不相同。

49 Huffman解码 二. 基于查找表的解码：对所有符号解码率恒定 1. 构造查找表：
在解码端从符号—码字映射表中构建查找表。如果表中的最长码字为l比特，则需要一个2l个入口的查找表。 空间限制：图象/视频最长的l=16~20 1. 构造查找表： 设 对应的码字为 ，假定 有 比特。构造一个l比特地址，前 个比特是 ，后 个比特取任意0和1的组合。所以，对符号 有 个地址。 在每个入口形成

50 Huffman解码 2. 解码步骤： 从压缩输入比特流中，读l个比特到缓冲区中;
重复步骤2和3，直到所有的符号都解码。

51 规范Huffman编码 并非只有使用二叉树建立的前缀编码才是 Huffman 编码，只要符合
(1) 是前缀编码 (2) 某一字符编码长度和使用二叉树建立的该字符的编码长度相同 这两个条件的编码都可以叫做 Huffman 编码。 规范(Canonical)：简单快速

52 规范Huffman编码 编码步骤： 统计每个符号的频率 根据这些频率信息求出该符号所需的位数/编码长度
关心的仅仅是该符号在树中的深度，完全没有必要构造二叉树，仅用一个数组就可以模拟二叉树的创建过程并得到符号的深度 （详见《数据压缩原理与应用》2.8.5节） 统计从最大编码长度到1的每个长度对应多少个符号，然后为每个符号递增分配编码 编码输出压缩信息

53 规范Huffman编码 例：一组16个字符 3比特：4个字符；5比特：5个字符；6比特：7个字符 (b)：规范Huffman编码 可能码长：
每个码长的码字： 每组的第一个码字：

54 规范Huffman编码 例1：（续） 3比特：4个字符；5比特：5个字符；6比特：7个字符 (b)为规范Huffman编码 可能码长：
每个码长的码字： 每组的第一个码字： 保证所有长于l位的码字的前l位前缀小于first[l]，满足前缀码的要求

55 规范Huffman编码 对大字母表且必须快速解码时，规范Huffman编码特别有用 解码规则： 解码器很容易逐个读入和检测输入位来识别码长
知道码长，即可进一步解码读出符号 解码规则： 所有长于l位的码字的前l位前缀小于first[l] 例：输入：00110 v：0，00=0，001=1，0011=3；00110=6 l: 1， ， ， ， first[l]： 2， ， ， ， 码长为l=5， v-first[5] = 6-4=2，即符号为码长为5的3个字符（编号从0开始）

56 规范Huffman编码 码长的确定：用最小堆实现
满二叉树：除叶子节点外的所有节点都有两个分支的二叉树 平衡二叉树：底部有些节点缺少右分支的满二叉树 堆（heap）：为平衡二叉树，且树中每个叶子都包含一个有序数据，使得从叶子到根的每条路径都已排序 最小堆：非增序的堆 堆筛选：将堆底部最右边节点的值作为新的树根保证筛选后的数仍是一课平衡二叉树，然后对堆排序，使得其为最小堆

57 规范Huffman编码 平衡：不用额外的指针就可将其保存在数组中 码长的确定：用一个长度为2m的数组A，其中m为信源符号的数目
数组第i节点的两个分支分别置于第2i和第2i+1位置 数组第j个节点的父亲节点第 位置 码长的确定：用一个长度为2m的数组A，其中m为信源符号的数目 将m个符号出现的频率放在数组的高半段A[m+1]到A [2m]中 将最小堆放在A [1]到A [m]中，堆中的数据项则指向数组高半段频率的指针 然后算法进入循环，在每次迭代中，用堆来找出两个频率最小的数据项，并用其和来替代它们；将和保存在前一个堆的位置A [h]中，这样堆就可以收缩一个位置 重复循环，直到堆中只剩下一个指针

58 规范Huffman编码 可以不依赖任何树结构进行高速解压缩 而且在整个压缩、解压缩过程中需要的空间比传统 Huffman 编码少得多

59 Huffman编码的局限性 当符号集较大且概率分布不是很悬殊时，Huffman的平均码长可接近于熵
对于概率分布悬殊的消息集合，上限可能很大，意味着编码冗余度较大 一个极端的例子：黑白传真 采用Huffman编码，得到 ，都需要l=1位，没起到压缩的作用。编码效率仅为 这是因为Huffman编码只能为每个信源符号分配整数个比特，只有当每个符号的概率是2的负整数倍时，才能达到熵值。

60 Huffman编码的局限性 Huffman编码的平均码长满足平均码长界定定理： 对Huffman编码，更紧致的上界：
令 表示最大概率，若 ，则平均码长满足： 若 ，则平均码长满足： 所以最大概率比较大（概率不均衡）时，上界离熵值相差较大，编码效率不高。

61 扩展Huffman编码 考虑信源： Huffman 编码： Q：能做得更好吗？
A = {a, b, c}, P(a) = 0.8, P(b) = 0.02, P(c) = 0.18 H = bits/symbol Huffman 编码： a 0 b 11 c 10 l = 1.2 bits/symbol 冗余 = b/sym (47%!) Q：能做得更好吗？

62 扩展Huffman编码 (2) 思想 考虑对两个字母序列编码，而不是单个字母 l = 1.7228/2 = 0.8614
合并信源符号（联合熵） 字母 概率 码字 aa 0.6400 ab 0.0160 10101 ac 0.1440 11 ba 101000 bb 0.0004 bc 0.0036 ca 100 cb cc 0.0324 1011 l = /2 = 冗余 = 比特/字符

63 扩展Huffman编码 (3) 该思想还可以扩展 设码符号集 信源符号的k次扩展： ，其平均长度为 如果要求 为唯一可译码，则
考虑所有mk 的序列 设码符号集 信源符号的k次扩展： ，其平均长度为 如果要求 为唯一可译码，则 每个信源符号的平均码长 当k足够大时，平均码长l可以无限接近下界值，从而在一定程度上提高了编码的有效性

64 扩展Huffman编码 (4) 理论上，通过考虑更多序列可以改进编码 实践中，字母表随序列长度指数增长使得它不现实 大多数序列的频率为0
如，对长度为3的ASCII序列：2563 = 224 = 16M 大多数序列的频率为0  需要其他方法

65 例： 离散无记忆信源 X： x1 x2 P(X): 0.2 0.8 则：
H(X) = －0.2 log 0.2 －0.8 log 0.8 ＝ 比特/信符 用二进制符号集A:{0，1}进行无失真信源编码：   x1 → w1＝0； x2 → w2＝1；

66 例： 对其二次扩展信源进行编码： X2 p(wi) wi x1x1 1/25 000 x1x2 4/25 001 x2x1 4/25 01

67 Huffman编码的应用 在实际应用中， Huffman编码通常与其他编码技术一起使用 例：无损图像压缩
Gray images (0~255), Image size: 256*256 Sensin Sena Omaha Earth

68 在图像压缩中的应用 直接对像素用Huffman编码进行压缩 压缩率不是很高，平均每个像素约减少1比特 更实用的技术：与预测模型一起使用
Image Name Bits/Pexel Total Size (bytes) Compression Ratio Sena 7.01 57,504 1.14. Sensin 7.49 61,430 1.07 Eartch 4.94 40,534 1.62 Omaha 7.12 58.374 1.12

69 在图像压缩中的应用 对像素差分用Huffman编码进行压缩 利用预测模型 ，然后对预测残差，即像素差分进行编码，带来压缩率的提高
利用预测模型 ，然后对预测残差，即像素差分进行编码，带来压缩率的提高 对像素差分用Huffman编码进行压缩 Image Name Bits/Pexel Total Size (bytes) Compression Ratio Sena 4.02 32, 968 1.99 Sensin 4.70 38,541 1.70 Eartch 4.13 33,880 1.93 Omaha 6.42 52.643 1.24

70 在文本压缩中的应用 文本压缩比较适合Huffman编码 字母表是离散的，而且概率模型基本稳定
教材3.8.2节中Table 3.26和Table 3.27中不同文本的字母概率很相似 用Huffman编码对教材第三章进行编码，文件大小从70,000字节下降到43,000个字节 可以利用其他技术进一步去除文本中的相关性（教材第五章和第六章）

71 Estimated Compression
在音频压缩中的应用 CD质量的音频： 采样频率：44.1kHz；每个样本16比特 数据量巨大 对16比特的CD质量音频用Huffman编码进行压缩 File Name Original File Size (Bytes) Entropy (bits) Estimated Compression File Size (bytes) Compression Ratio Mozart 939,862 12.8 725,420 1.30 Cohn 402,442 13.8 349,300 1.15 Mir 13.7 759,540 1.16

72 Estimated Compression
在音频压缩中的应用 利用预测模型 ，然后对预测残差，即像素差分进行编码，带来压缩率的提高 对16比特的CD质量音频差分用Huffman编码进行压缩 File Name Original File Size (Bytes) Entropy (bits) Estimated Compression File Size (bytes) Compression Ratio Mozart 939,862 9.7 569,792 1.65 Cohn 402,442 10.4 261,590 1.54 Mir 10.9 602,240 1.47

73 小结 最早的Shannon—Fano 编码 Huffman编码 其他 考虑了信源的统计特性：经常出现的信源符号对应较短的码字
编码方法不惟一，码长方差较小的编码更好 对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单 其他 Huffman Optimality of Huffman Codes /3.2.2/ Non-binary Huffman Codes /3.3/ 相关编码 Golomb /3.5/ Rice /3.6/ Tunstall /3.7/

74 下节课内容： 作业：第三章2、3、4、5 2(c)不做 算术编码/自适应算术编码