《数据压缩与信源编码第3讲霍夫曼编码#高级教学》由会员分享，可在线阅读，更多相关《数据压缩与信源编码第3讲霍夫曼编码#高级教学（39页珍藏版）》请在金锄头文库上搜索。
1、数据压缩与信源编码第3讲 霍夫曼编码西安电子科技大学 电子工程学院主讲 ：林三虎1优质材料Huffman编码算法v基本规则基本规则出现概率越高的符号采用越短的编码。出现概率越高的符号采用越短的编码。出现概率最低的两个符号采用相同长度的编码。出现概率最低的两个符号采用相同长度的编码。v具体步骤具体步骤将符号出现概率从高到低排序。将符号出现概率从高到低排序。将概率最低的两个符号合并成一个符号，它们概率之将概率最低的两个符号合并成一个符号，它们概率之和为新符号的概率。和为新符号的概率。重复上面两个步骤，直到概率为重复上面两个步骤，直到概率为1。每次合并符号，用每次合并符号，用0和和1区分两个符号。区
2、分两个符号。从根节点开始搜索每个符号，记录其从根节点开始搜索每个符号，记录其0，1序列即为该序列即为该符号的编码。符号的编码。2优质材料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编码100110111011113优质材料Huffman编码算法符号a1a2a3a4a5Huffman编码1001101
3、1101111编码示例：信源输出符号序列a1,a2,a3,a4,a5,a2,a1,a2Huffman编码输出为1001101110111101004优质材料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
4、倍。倍。5优质材料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编码树编码树6优质材料Huffman编码算法符号a1a2a3a4a5概率0.20.40.20
5、.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编码没有达到压缩能力的极限，仍存在继续压缩编码没有达到压缩能力的极限，仍存在继续压缩的可能。的可能。7优质材料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)a
6、1(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的分配是任意的的分配是任意的8优质材料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
7、.20.10.05符号a1a2a3a4a5编码110011011101111编码201100100010000因此，霍夫曼编码不唯一因此，霍夫曼编码不唯一9优质材料Huffman编码算法霍夫曼编码不唯一，什么样的霍夫曼编码最好呢？霍夫曼编码不唯一，什么样的霍夫曼编码最好呢？答案是：最小方差霍夫曼编码答案是：最小方差霍夫曼编码最小方差霍夫曼编码在合并两个符号时，如果有最小方差霍夫曼编码在合并两个符号时，如果有3个或个或以上的符号概率都最小，则将刚合并的符号放在概率相以上的符号概率都最小，则将刚合并的符号放在概率相同的符号的最上面。同的符号的最上面。10优质材料最小方差Huffman编码算法a2(
8、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编码310001101001111优质材料最小方差Huffman编码算法符号a1a2a3a4a5编码110011011101111编码201100100010000编码3100011010011Huffman编码编码1和和2码字长度在码字长度在14之间，码长方差较大，编之间，码长方差较大，编码
9、码3的码字长度在的码字长度在23之间，码长方差较小。之间，码长方差较小。为什么码长方差小的编码最佳？为什么码长方差小的编码最佳？对于一定速率的信源，例如对于一定速率的信源，例如1000symbol/秒，秒， Huffman编编码平均码长为码平均码长为2.2bits，则平均编码码流输出为，则平均编码码流输出为2200bit/秒，秒，假定信道带宽为假定信道带宽为2200bit/秒，能够满足传输要求。秒，能够满足传输要求。12优质材料最小方差Huffman编码算法符号a1a2a3a4a5编码110011011101111编码201100100010000编码3100011010011对于一定速率的信
10、源，例如对于一定速率的信源，例如1000symbol/秒，秒， Huffman编编码平均码长为码平均码长为2.2bits，则平均编码码流输出为，则平均编码码流输出为2200bit/秒，秒，假定信道带宽为假定信道带宽为2200bit/秒，能够满足传输要求。秒，能够满足传输要求。如果信源连续输出如果信源连续输出a2，则编码，则编码1码流输出为码流输出为1000bit/秒，浪秒，浪费信道带宽。费信道带宽。如果信源连续输出如果信源连续输出a5，则编码，则编码1码流输出为码流输出为4000bit/秒，信秒，信道带宽又不足。道带宽又不足。13优质材料最小方差Huffman编码算法符号a1a2a3a4a5编
11、码110011011101111编码201100100010000编码3100011010011为了充分利用信道带宽，必须对编码输出的码流进行缓冲，为了充分利用信道带宽，必须对编码输出的码流进行缓冲，在信道带宽不足时将码流存储起来，在信道带宽富裕时进在信道带宽不足时将码流存储起来，在信道带宽富裕时进行传送。行传送。如果信源连续输出如果信源连续输出a2，则编码，则编码1码流输出为码流输出为1000bit/秒，浪秒，浪费信道带宽。费信道带宽。如果信源连续输出如果信源连续输出a5，则编码，则编码1码流输出为码流输出为4000bit/秒，信秒，信道带宽又不足。道带宽又不足。14优质材料最小方差Huff
12、man编码算法符号a1a2a3a4a5编码110011011101111编码201100100010000编码310001101001111a51111a51，11，1111111a501111a21，11，101011a11，11000symbol/s2200bit/s15优质材料最小方差Huffman编码算法符号a1a2a3a4a5编码110011011101111编码201100100010000编码3100011010011编码的码长方差越大，缓冲必须越大；编码的码长方差越大，缓冲必须越大；编码的码长方差越小，缓冲可以越小；编码的码长方差越小，缓冲可以越小；因此，最佳的因此，最佳的Hu
13、ffman编码为最小方差编码为最小方差Huffman编码。编码。如果信源连续输出如果信源连续输出a2，则编码，则编码1码流输出为码流输出为1000bit/秒，浪秒，浪费信道带宽。费信道带宽。如果信源连续输出如果信源连续输出a5，则编码，则编码1码流输出为码流输出为4000bit/秒，信秒，信道带宽又不足。道带宽又不足。16优质材料Huffman编码特点哈夫曼编码方法构造出来的码不是惟一的。哈夫曼编码方法构造出来的码不是惟一的。 符号a1a2a3a4a5编码110011011101111编码201100100010000编码310001101001117优质材料Huffman编码特点Huffma
14、n编码的码长虽然是可变的，但却不需要另外附加同编码的码长虽然是可变的，但却不需要另外附加同步代码。步代码。符号a1a2a3a4a5编码110011011101111编码201100100010000编码3100011010011例如，例如，10011011101111按照编码按照编码1可解释为可解释为a1a2a3a4a5。 又如，又如，100011010011按照编码按照编码3可解释为可解释为a1a2a3a4a5。18优质材料规范Huffman码字规范的霍夫曼码字是从规范的霍夫曼码字是从Huffman码字从特意挑选出来的，码字从特意挑选出来的，目的是便于在译码时检测码字的长度。目的是便于在译码
15、时检测码字的长度。下面两个编码中，编码下面两个编码中，编码2为规范的为规范的Huffman码字。码字。符号符号12345678编码编码100000101001110000100011001010011编码编码201110010111000100001010011000111符号符号910111213141516编码编码110100101010101011101100101101101110101111110000编码编码20100000000000000100001000001100010000010100011019优质材料规范Huffman码字码长码长Length123456码字个数码字个
16、数Numl004057起始编码起始编码first243540规范的规范的Huffman码字这样产生码字这样产生first6=0;for x:=5 downto 1 do firstx=(firstx+1+numlx+1)/2其中，其中，y表示取不小于表示取不小于y的最小整数。的最小整数。符号符号12345678编码编码201110010111000100001010011000111符号符号910111213141516编码编码20100000000000000100001000001100010000010100011020优质材料规范Huffman码字码长码长Length123456码字个
17、数码字个数Numl004057起始编码起始编码first243540符号符号12345678编码编码100000101001110000100011001010011编码编码201110010111000100001010011000111符号符号910111213141516编码编码110100101010101011101100101101101110101111110000编码编码20100000000000000100001000001100010000010100011021优质材料规范Huffman码字码长码长Length123456码字个数码字个数Numl004057起始编码起始
18、编码first243540规范的规范的Huffman码字可以这样解码码字可以这样解码x:=1; input v;while vfirstx append next input bit to v; x := x + 1;end while;例如码流例如码流00110v=0,first1=2;v=00,first2=4;v=001,first3=3;v=0011,first4=5;v=00110,first5=4;码长为码长为5，v-first5=2,符符号为码长为号为码长为5的第的第2个符号个符号(以以0开始开始)，即符号，即符号722优质材料Huffman编码编程实现方法编码开始编码开始概率统
19、计概率统计建立码树建立码树/码表码表传送码表传送码表编码编码-传送压缩码流传送压缩码流编码结束编码结束解码开始解码开始接收码表接收码表恢复码树恢复码树/码表码表接收压缩码流接收压缩码流解码解码-恢复原码恢复原码解码结束解码结束23优质材料Huffman编码编程编码开始编码开始概率统计概率统计建立码树建立码树/码表码表传送码表传送码表编码编码-传送压缩码流传送压缩码流编码结束编码结束对原始数据出现次数进行统计，将次对原始数据出现次数进行统计，将次数存储在数组数存储在数组counter中。中。符号a1a2a3a4a5权值100283528312概率0.2180.0610.0760.6180.026
20、24优质材料Huffman编码编程编码开始编码开始概率统计概率统计建立码树建立码树/码表码表传送码表传送码表编码编码-传送压缩码流传送压缩码流编码结束编码结束利用统计结果利用统计结果counter和链表和链表typedef struct int weit; /权值权值int lchd; /左孩子左孩子int rchd; /右孩子右孩子int part; /父节点父节点hufmtree;hufmtree *htree; 建立建立Huffman码树和码表。码树和码表。25优质材料Huffman编码编程编码开始编码开始概率统计概率统计建立码树建立码树/码表码表传送码表传送码表编码编码-传送压缩码流传
21、送压缩码流编码结束编码结束码表的传送可以有多种形式，比如传码表的传送可以有多种形式，比如传送统计数组送统计数组counter，传送，传送Huffman码树，传送码树，传送Huffman码表都可以。码表都可以。26优质材料Huffman编码编程编码开始编码开始概率统计概率统计建立码树建立码树/码表码表传送码表传送码表编码编码-传送压缩码流传送压缩码流编码结束编码结束每个字节原始数据用一个长度不同的每个字节原始数据用一个长度不同的0、1序列表示，序列表示，8个个0、1要打包成要打包成1个字节，如个字节，如abcde压缩后为压缩后为101,10,1111,110，0110则打包成则打包成0xB7,0
22、xE627优质材料Huffman编码编程编码开始编码开始概率统计概率统计建立码树建立码树/码表码表传送码表传送码表编码编码-传送压缩码流传送压缩码流编码结束编码结束每个字节原始数据用一个长度不同的每个字节原始数据用一个长度不同的0、1序列表示，序列表示，8个个0、1要打包成要打包成1个字节，如个字节，如abcde压缩后为压缩后为101,10,1111,110，0110则打包成则打包成0xB7,0xE6整个压缩后的码流长度不一定能够被整个压缩后的码流长度不一定能够被8整除，必须加以处理。整除，必须加以处理。28优质材料Huffman编码编程压缩压缩对对abc.txt进行压缩，压缩结果存储在进行压
23、缩，压缩结果存储在abc_code.txt中。中。解压解压对对abc_code.txt进行解压，恢复结果存储在进行解压，恢复结果存储在abc_decode.txt中。中。评价评价对比对比abc.txt和和abc_decode.txt，如果完全一致，表明，如果完全一致，表明压缩压缩/解压过程正确，反之不正确。解压过程正确，反之不正确。对比对比abc.txt和和abc_decode.txt文件大小，计算压缩比。文件大小，计算压缩比。29优质材料自适应Huffman编码 Adaptive Huffman coding ( Dynamic Huffman coding )对信源进行哈夫曼编码后形成了一
24、个哈夫曼编码表，若要对信源进行哈夫曼编码后形成了一个哈夫曼编码表，若要正确解码必须依照此表。于是在信源存储与传输过程中，正确解码必须依照此表。于是在信源存储与传输过程中，必须首先考虑此表的存储与传输，故此表也占有一定的比必须首先考虑此表的存储与传输，故此表也占有一定的比特数。一种解决方法是使用默认的哈夫曼编码表特数。一种解决方法是使用默认的哈夫曼编码表Huffman编码需要实现知道输入符号集的概率分布，为了编码需要实现知道输入符号集的概率分布，为了进行编码需要先对数据计算概率分布，然后再对数据进行进行编码需要先对数据计算概率分布，然后再对数据进行编码，需要对数据扫描两遍。编码，需要对数据扫描两
25、遍。自适应自适应Huffman编码编码自适应自适应Huffman编码不需要事先计算概率分布，能够在编编码不需要事先计算概率分布，能够在编码码/解码过程中自动建立解码过程中自动建立Huffman编码树，只需要对数据编码树，只需要对数据扫描一遍因而得到了广泛应用。扫描一遍因而得到了广泛应用。 ，而更，而更好的方法是好的方法是30优质材料自适应Huffman编码 Adaptive Huffman coding ( Dynamic Huffman coding ) 自适应自适应Huffman编码的思想是从一编码的思想是从一个空的个空的Huffman编码树开始，空的编码树开始，空的Huffman编码树仅
26、包含一个空节点编码树仅包含一个空节点NYT(Not Yet Transmitted)，表示，表示还没有开始数据传送。还没有开始数据传送。NYT31优质材料自适应Huffman编码 Adaptive Huffman coding ( Dynamic Huffman coding ) 自适应自适应Huffman编码的思想是从一编码的思想是从一个空的个空的Huffman编码树开始，空的编码树开始，空的Huffman编码树仅包含一个空节点编码树仅包含一个空节点NYT(Not Yet Transmitted)，表示，表示还没有开始数据传送。还没有开始数据传送。NYT读入的第读入的第1个符号，不做压缩直接
27、个符号，不做压缩直接进入输出码流，同时将其添加进树进入输出码流，同时将其添加进树中赋予码字。中赋予码字。1110a输入输入a，输出，输出0110000132优质材料自适应Huffman编码 Adaptive Huffman coding ( Dynamic Huffman coding ) NYT2110a每读入每读入1个新的符号，输出个新的符号，输出NYT，然，然后将新符号不做压缩直接进入输出后将新符号不做压缩直接进入输出码流，同时将其添加进树中赋予码码流，同时将其添加进树中赋予码字。字。输入输入b，输出，输出00110001011b10NYT1110a33优质材料自适应Huffman编码
28、Adaptive Huffman coding ( Dynamic Huffman coding ) 如果读入一个已有的符号，则直接如果读入一个已有的符号，则直接输出编码，实现数据压缩。输出编码，实现数据压缩。NYT2110a输入输入b，输出，输出0111b1034优质材料自适应Huffman编码 Adaptive Huffman coding ( Dynamic Huffman coding ) 如果读入一个已有的符号，则直接如果读入一个已有的符号，则直接输出编码，实现数据压缩。输出编码，实现数据压缩。NYT3110a22b10每读入一个已有的符号，需要修改每读入一个已有的符号，需要修改权值
29、，更新码树。权值，更新码树。NYT3210b11a1035优质材料自适应Huffman编码 Adaptive Huffman coding ( Dynamic Huffman coding ) 每读入每读入1个新的符号，输出个新的符号，输出NYT，然，然后将新符号不做压缩直接进入输出后将新符号不做压缩直接进入输出码流，同时将其添加进树中赋予码码流，同时将其添加进树中赋予码字。字。NYT3210b11a10NYT4210b21a10输入输入c，输出，输出00011000101c1036优质材料自适应Huffman编码 Adaptive Huffman coding ( Dynamic Huffm
30、an coding ) 如果读入一个已有的符号，则直接如果读入一个已有的符号，则直接输出编码，实现数据压缩。同时修输出编码，实现数据压缩。同时修改权值，更新码树。改权值，更新码树。NYT5210b32a10输入输入a，输出，输出011c10NYT4210b21a101c1037优质材料自适应Huffman编码 Adaptive Huffman coding ( Dynamic Huffman coding ) 数据数据abbca的自适应的自适应Huffman编码为编码为01100001,001100010,01,0001100011,010以字节表示为以字节表示为0x61,0x31,0x23,
31、0x1c38优质材料大作业1编写编写Huffman压缩程序压缩程序Huffman_Code对对*.txt进行压缩，压缩结果存储在进行压缩，压缩结果存储在*_code.txt中。中。编写编写Huffman解压缩程序解压缩程序Huffman_Decode对对*_code.txt进行解压，恢复结果存储在进行解压，恢复结果存储在*_decode.txt中。中。编写试验报告编写试验报告1.试验目的；试验目的；2.试验内容。试验内容。3.算法流程。算法流程。4.程序设计说明。程序设计说明。5.程序压缩性能评价。程序压缩性能评价。6.程序源代码。程序源代码。7.测试数据文件。测试数据文件。作业要求作业要求时间：时间：4月月22日前提交至日前提交至39优质材料
