数据压缩与信源编码第3讲霍夫曼编码.pptVIP

数据压缩与信源编码

第3讲霍夫曼编码西安电子科技大学电子工程学院主讲：林三虎

Huffman编码算法根本规那么出现概率越高的符号采用越短的编码。出现概率最低的两个符号采用相同长度的编码。具体步骤将符号出现概率从高到低排序。将概率最低的两个符号合并成一个符号，它们概率之和为新符号的概率。重复上面两个步骤，直到概率为1。每次合并符号，用0和1区分两个符号。从根节点开始有哪些信誉好的足球投注网站每个符号，记录其0，1序列即为该符号的编码。

Huffman编码算法a2(0.4)a1(0.2)a3(0.2)a4(0.1)a5(0.1)a2(0.4)a1(0.2)a3(0.2)a4’(0.2)a2(0.4)a1(0.2)a3’(0.4)a2(0.4)a1‘(0.6)a2’(1.0号a1a2a3a4a5概率0.20.40.20.10.1符号a1a2a3a4a5Huffman编码10011011101111

Huffman编码算法符号a1a2a3a4a5Huffman编码10011011101111编码例如：信源输出符号序列a1,a2,a3,a4,a5,a2,a1,a2Huffman编码输出为

Huffman编码算法符号a1a2a3a4a5概率0.20.40.20.10.1Huffman编码10011011101111定长码000001010011100Huffman编码平均码长=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倍。

Huffman编码算法符号a1a2a3a4a5概率0.20.40.20.10.1编码10011011101111Huffman编码平均码长=0.2*2+0.4*1+0.2*3+0.1*4+0.1*4=2.2bits假定以每个内节点的所有孩子节点的概率之和表示该节点的值，Huffman编码树的内节点之和等于平均码长。1.0a2a10.60.40110a30.2a4a51100Huffman编码树

Huffman编码算法符号a1a2a3a4a5概率0.20.40.20.10.1Huffman编码10011011101111Huffman编码平均码长=0.2*2+0.4*1+0.2*3+0.1*4+0.1*4=2.2bits信源的熵Huffman编码冗余度=Huffman编码平均码长-信源的熵=0.078bits/symbolHuffman编码没有到达压缩能力的极限，仍存在继续压缩的可能。

Huffman编码算法a2(0.4)a1(0.2)a3(0.2)a4(0.1)a5(0.1)a2(0.4)a1(0.2)a3(0.2)a4’(0.2)a2(0.4)a1(0.2)a3’(0.4)a2(0.4)a1‘(0.6)a2’(1.0号a1a2a3a4a5概率0.250.40.20.10.05符号a1a2a3a4a5编码110011011101111编码201100100010000霍夫曼编码中0和1的分配是任意的

Huffman编码算法a2(0.4)a1(0.2)a3(0.2)a4(0.1)a5(0.1)a2(0.4)a1(0.2)a3(0.2)a4’(0.2)a2(0.4)a1(0.2)a3’(0.4)a2(0.4)a1‘(0.6)a2’(1.0号a1a2a3a4a5概率0.250.40.20.10.05符号a1a2a3a4a5编码110011011101111编码201100100010000因此，霍夫曼编码不唯一

Huffman编码算法霍夫曼编码不唯一，什么样的霍夫曼编码最好呢？答案是：最小方差霍夫曼编码最小方差霍夫曼编码在合并两个符号时，如果有3个或以上的符号概率都最小，那么将刚合并的符号放在概率相同的符号的最上面。

最小方差Huffman编码算法a2(0.4)a1(0.2)a3(0.2)a4(0.1)a5(0.1)a2(0.4)a1(0.2)a3(0.2)a4’(0.2)a2(0.4)a4’(0.2)a1’(0.4)a1‘(0.4)a2‘(0.6)a2’(1.0号a1a2a3a4a5概率0.250.40.20.10.05符号a1a2a3a4a5编码3100011010011

最小方差Huffman编码算法符号a1a2a3a4a5编码110011011101111编码201100100010000编码3100011010011Huffman编码1和2码字长度在1~4之间，码长方差较大，编码3的码字长度在2~3之间，码长方差较小。为什么码长方差小的编码最正确？对于一定速率的信源，例如1000symbol/秒，Huffm