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

数据压缩与信源编码第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)01010101符号a1a2a3a4a5概率0.20.40.20.10.1符号a1a2a3a4a5Huffman编码10011011101111Huffman编码算法符号a1a2a3a4a5Huffman编码10011011101111编码示例：信源输出符号序列a1,a2,a3,a4,a5,a2,a1,a2Huffman编码输出为100110111011110100Huffman编码算法符号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/symbolsymbolbitaPaPaiaPAHiiii/122.2)(log)()()()(Huffman编码没有达到压缩能力的极限，仍存在继续压缩的可能。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)10101010符号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)10101010符号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)01010101符号a1a2a3a4a5概率0.250.40.20.10.05符号a1a2a3a4a5编码3100011010011最小方差Huffman编码算法符号a1a2a3a4a5编码110011011101111编码201100100010000编码3100011010011Huffman编码1和2码字长度在1~4之间，码长方差较大，编码3的码字长度在2~3之间，码长方差较小。为什么码长方差小的编码最佳？对于一定速率的信源，例如1000symbol/秒，Huffman编码平均码长为2.2bits，则平均编码码流输出为2200bit/秒，假定信道带宽为2200bit/秒，能够满足传输要求。最小方差Huffman编码算法符号a1a2a3a4a5编码110011011101111编码201100100010000编码3100011010011对于一定速率的信源，例如1000symbol/秒，Huffman编码平均码长为2.2bits，则平均编码码流输出为2200bit/秒，假定信道带宽为2200bit/秒，能够满足传输要求。如果信源连续输出a2，则编码1码流输出为1000bit/秒，浪费信道带宽。如果信源连续输出a5，则编码1码流输出为4000bit/秒，信道带宽又不足。最小方差Huffman编码算法符号a1a2a3a4a5编码110011011101111编码201100100010000编码3100011010011为了充分利用信道带宽，必须对编码输出的码流进行缓冲，在信道带宽不足时将码流存储起来，在信道带宽富裕时进行传送。如果信源连续输出a2，则编码1码流输出为1000bit/秒，浪费信道带宽。如果信源连续输出a5，则编码1码流输出为4000bit/秒，信道带宽又不足。最小方差Huffman编码算法符号a1a2a3a4a5编码110011011101111编码201100100010000编码310001101001111a51111a51，11，1111111a501111a21，11，101011a11，11000symbol/s2200bit/s最小方差Huffman编码算法符号a1a2a3a4a5编码110011011101111编码201100100010000编码3100011010011编码的码长方差越大，缓冲必须越大；编码的码长方差越小，缓冲可以越小；因此，最佳的Huffman编码为最小方差Huffman编码。如果信源连续输出a2，则编码1码流输出为1000bit/秒，浪费信道带宽。如果信源连续输出a5，则编码1码流输出为4000bit/秒，信道带宽又不足。Huffman编码特点哈夫曼编码方法构造出来的码不是惟一的。符号a1a2a3a4a5编码110011011101111编码201100100010000编码3100011010011Huffman编码特点Huffman编码的码长虽然是可变的，但却不需要另外附加同步代码。符号a1a2a3a4a5编码110011011101111编码201100100010000编码3100011010011例如，10011011101111按照编码1可解释为a1a2a3a4a5。又如，100011010011按照编码3可解释为a1a2a3a4a5。规范Huffman码字规范的霍夫曼码字是从Huffman码字从特意挑选出来的，目的是便于在译码时检测码字的长度。下面两个编码中，编码2为规范的Huffman码字。符号12345678编码100000101001110000100011001010011编码201110010111000100001010011000111符号910111213141516编码110100101010101011101100101101101110101111110000编码201000000000000001000010000011000100000101000110规范Huffman码字码长Length123456码字个数Numl004057起始编码first243540规范的Huffman码字这样产生first[6]=0;forx:=5downto1dofirst[x]=[(first[x+1]+numl[x+1])/2]其中，[y]表示取不小于y的最小整数。符号12345678编码201110010111000100001010011000111符号910111213141516编码201000000000000001000010000011000100000101000110规范Huffman码字码长Length123456码字个数Numl004057起始编码first243540符号12345678编码100000101001110000100011001010011编码201110010111000100001010011000111符号910111213141516编码110100101010101011101100101101101110101111110000编码201000000000000001000010000011000100000101000110规范Huffman码字码长Length123456码字个数Numl004057起始编码first243540规范的Huffman码字可以这样解码x:=1;inputv;whilevfirst[x]appendnextinputbittov;x:=x+1;endwhile;例如码流00110v=0,first[1]=2;v=00,first[2]=4;v=001,first[3]=3;v=0011,first[4]=5;v=00110,first[5]=4;码长为5，v-first[5]=2,符号为码长为5的第2个符号(以0开始)，即符号7Huffman编码编程实现方法编码开始概率统计建立码树/码表传送码表编码-传送压缩码流编码结束解码开始接收码表恢复码树/码表接收压缩码流解码-恢复原码解码结束Huffman编码编程编码开始概率统计建立码树/码表传送码表编码-传送压缩码流编码结束对原始数据出现次数进行统计，将次数存储在数组counter中。符号a1a2a3a4a5权值100283528312概率0.2180.0610.0760.6180.026Huffman编码编程编码开始概率统计建立码树/码表传送码表编码-传送压缩码流编码结束利用统计结果counter和链表typedefstruct{intweit;//权值intlchd;//左孩子intrchd;//右孩子intpart;//父节点}hufmtree;hufmtree*htree;建立Huffman码树和码表。Huffman编码编程编码开始概率统计建立码树/码表传送码表编码-传送压缩码流编码结束码表的传送可以有多种形式，比如传送统计数组counter，传送Huffman码树，传送Huffman码表都可以。Huffman编码编程编码开始概率统计建立码树/码表传送码表编码-传送压缩码流编码结束每个字节原始数据用一个长度不同的0、1序列表示，8个0、1要打包成1个字节，如abcde压缩后为101,10,1111,110，0110则打包成0xB7,0xE6Huffman编码编程编码开始概率统计建立码树/码表传送码表编码-传送压缩码流编码结束每个字节原始数据用一个长度不同的0、1序列表示，8个0、1要打包成1个字节，如abcde压缩后为101,10,1111,110，0110则打包成0xB7,0xE6整个压缩后的码流长度不一定能够被8整除，必须