编码开始 解码开始 概率统计 接收码表
建立码树/码表
恢复码树/码表
传送码表
接收压缩码流
编码-传送压缩码流
解码-恢复原码
编码结束
解码结束
Huffman编码编程
编码开始 对原始数据出现次数进行统计，将次 数存储在数组counter中。 概率统计
a2(0.4) a4
’(0.2)
符号 编码3
a1 10
a2 00
a3 11
a4 010
a5 011
最小方差Huffman编码算法
符号 编码1
编码2 编码3
a1 10
01 10
a2 0
1 00
a3 110
001 11
a4 1110
0001 010
a5 1111
0000 011
Huffman编码1和2码字长度在1~4之间，码长方差较大， 编码3的码字长度在2~3之间，码长方差较小。 为什么码长方差小的编码最佳？ 对于一定速率的信源，例如1000symbol/秒， Huffman编 码平均码长为2.2bits，则平均编码码流输出为2200bit/秒， 假定信道带宽为2200bit/秒，能够满足传输要求。
最小方差Huffman编码算法
符号 编码1
编码2 编码3
a1 10
01 10
a2 0
1 00
a3 110
001 11
a4 1110
0001 010
a5 1111
0000 011
对于一定速率的信源，例如1000symbol/秒， Huffman编 码平均码长为2.2bits，则平均编码码流输出为2200bit/秒， 假定信道带宽为2200bit/秒，能够满足传输要求。 如果信源连续输出a2，则编码1码流输出为1000bit/秒，浪 费信道带宽。 如果信源连续输出a5，则编码1码流输出为4000bit/秒，信 道带宽又不足。
Huffman编码算法
符号 概率 Huffman编 码 定长码 a1 0.2 10 000 a2 0.4 0 001 a3 0.2 110 010 a4 0.1 1110 011 a5 0.1 1111 100
Huffman编码平均码长 =0.2*2+0.4*1+0.2*3+0.1*4+0.1*4=2.2bits 如果使用定长码，每个符号需要3bits，Huffman编码平均 每符号节约0.8bits，压缩比3:2.2=1.36倍。
0000 011
2200bit/s 1，1 1，1 1，1 1，1 1，1
最小方差Huffman编码算法
符号 编码1
编码2 编码3
a1 10
01 10
a2 0
1 00
a3 110
001 11
a4 1110
0001 010
a5 1111
0000 011
如果信源连续输出a2，则编码1码流输出为1000bit/秒，浪 费信道带宽。 如果信源连续输出a5，则编码1码流输出为4000bit/秒，信 道带宽又不足。 编码的码长方差越大，缓冲必须越大； 编码的码长方差越小，缓冲可以越小； 因此，最佳的Huffman编码为最小方差Huffman编码。
0.6
1 0.4 1
0 a3
0
a4 Huffman编码树
0.2 1 a5
Huffman编码算法
符号 概率 Huffman编 码 a1 0.2 10 a2 0.4 0 a3 0.2 110 a4 0.1 1110 a5 0.1 1111
Huffman编码平均码长 =0.2*2+0.4*1+0.2*3+0.1*4+0.1*4=2.2bits 信源的熵 H ( A) P(ai )i(ai ) P(ai ) log P(ai ) 2.122bit / symbol Huffman编码冗余度=Huffman编码平均码长-信源的熵 =0.078bits/symbol Huffman编码没有达到压缩能力的极限，仍存在继续压缩 的可能。
a5 0.1
0 1 a2’(1.0)
0 1
a3
’(0.4)
符号 Huffman 编码
a1 10
a2 0
a3 110
a4 1110
a5 1111
Huffman编码算法
符号 Huffman 编码 a1 10 a2 0 a3 110 a4 1110 a5 1111
编码示例： 信源输出符号序列a1,a2,a3,a4,a5,a2,a1,a2 Huffman编码输出为100110111011110100
Huffman编码算法
符号 概率
a2(0.4) a1(0.2) a3(0.2) a4(0.1) a5(0.1) 0 1
a1 0.2
a2(0.4) a1(0.2) a3(0.2) a4’(0.2)
a2 0.4
a2(0.4)
a3 0.2
0 a1(0.2)
a4 0.1
a2(0.4) 1 a1
‘(0.6)
1 00
110
001 11
1110
0001 010
1111
0000 011
Huffman编码的码长虽然是可变的，但却不需要另外附加同 步代码。 例如，10011011101111按照编码1可解释为a1a2a3a4a5。 又如，100011010011按照编码3可解释为a1a2a3a4a5。
规范Huffman码字
a5 0.05
1 0 a2’(1.0)
1 0
a3
’(0.4)
霍夫曼编码中0和1的分配是任意的
a1 a2 a3 a4 a5
符号
编码1
编码2
10
01
0
1
110
001
1110
0001
1111
0000
Huffman编码算法
符号 概率
a2(0.4) a1(0.2) a3(0.2) a4(0.1) a5(0.1) 1 0
Huffman编码特点
符号 a1 a2 a3 a4 a5
编码1
编码2 编码3
10
01 10
0
1 00
110
001 11
1110
0001 010
1111
0000 011
哈夫曼编码方法构造出来的码不是惟一的。
Huffman编码特点
符号 a1 a2 a3 a4 a5
编码1
编码2 编码3
10
01 10
0
规范的Huffman码字这样产生 first[6]=0; for x:=5 downto 1 do first[x]=[(first[x+1]+numl[x+1])/2] 其中，[y]表示取不小于y的最小整数。
码长 Length
码字个数 Numl
1
0
2
0
3
4
4
0
5
5
6
7
起始编码 first
2
4
3
5
4
Huffman编码算法
符号
概率 编码
a1
0.2 10
a2
0.4 0
a3
0.2 110
a4
0.1 1110
0 1.0 1 0 a1
a5
0.1 1111
Huffman编码平均码长 =0.2*2+0.4*1+0.2*3+0.1*4+0.1*4 a2 =2.2bits 假定以每个内节点的所有孩子节点的概率 之和表示该节点的值，Huffman编码树的 内节点之和等于平均码长。
数据压缩与信源编码 第3讲 霍夫曼编码
西安电子科技大学 电子工程学院 主讲 ：林三虎
Huffman编码算法

基本规则
① 出现概率越高的符号采用越短的编码。 ② 出现概率最低的两个符号采用相同长度的编码。

具体步骤
① 将符号出现概率从高到低排序。
② 将概率最低的两个符号合并成一个符号，它们概率之
和为新符号的概率。 ③ 重复上面两个步骤，直到概率为1。 ④ 每次合并符号，用0和1区分两个符号。 ⑤ 从根节点开始搜索每个符号，记录其0，1序列即为该 符号的编码。
规范的霍夫曼码字是从Huffman码字从特意挑选出来的， 目的是便于在译码时检测码字的长度。 下面两个编码中，编码2为规范的Huffman码字。
符号 编码1 编码2 符号 编码1 编码2 1 000 011 9 10100 01000 2 001 100 10 101010 000000 3 010 101 11 101011 000001 4 011 110 12 101100 000010 5 10000 00100 13 101101 000011 6 10001 00101 14 101110 000100 7 10010 00110 15 101111 000101 8 10011 00111 16 110000 000110
最小方差Huffman编码算法
符号 编码1
编码2 编码3
1000symbol/s a5 a5 a5 a2 a1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
a1 10
01 10
a2 0
1 00
a3 110
001 11
a4 1110
0001 010
a5 1111
码长 Length 码字个数 Numl 起始编码 first
1 0 2
2 0 4
3 4 3
4 0 5
5 5 4
6 7 0
规范Huffman码字
码长 Length 码字个数 Numl 起始编码 first 1 0 2 2 0 4 3 4 3 4 0 5 5 5 4 6 7 0