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

数据压缩与信源编码第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),0,1,0,1,0,1,0,1,Huffman编码算法,编码示例：信源输出符号序列a1,a2,a3,a4,a5,a2,a1,a2Huffman编码输出为100110111011110100,Huffman编码算法,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倍。,Huffman编码算法,Huffman编码平均码长=0.2*2+0.4*1+0.2*3+0.1*4+0.1*4=2.2bits,假定以每个内节点的所有孩子节点的概率之和表示该节点的值，Huffman编码树的内节点之和等于平均码长。,1.0,a2,a1,0.6,0.4,0,1,1,0,a3,0.2,a4,a5,1,1,0,0,Huffman编码树,Huffman编码算法,Huffman编码平均码长=0.2*2+0.4*1+0.2*3+0.1*4+0.1*4=2.2bits,信源的熵,Huffman编码冗余度=Huffman编码平均码长-信源的熵=0.078bits/symbol,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),1,0,1,0,1,0,1,0,霍夫曼编码中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),1,0,1,0,1,0,1,0,因此，霍夫曼编码不唯一,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),0,1,0,1,0,1,0,1,最小方差Huffman编码算法,Huffman编码1和2码字长度在14之间，码长方差较大，编码3的码字长度在23之间，码长方差较小。,为什么码长方差小的编码最佳？,对于一定速率的信源，例如1000symbol/秒，Huffman编码平均码长为2.2bits，则平均编码码流输出为2200bit/秒，假定信道带宽为2200bit/秒，能够满足传输要求。,最小方差Huffman编码算法,对于一定速率的信源，例如1000symbol/秒，Huffman编码平均码长为2.2bits，则平均编码码流输出为2200bit/秒，假定信道带宽为2200bit/秒，能够满足传输要求。,如果信源连续输出a2，则编码1码流输出为1000bit/秒，浪费信道带宽。如果信源连续输出a5，则编码1码流输出为4000bit/秒，信道带宽又不足。,最小方差Huffman编码算法,为了充分利用信道带宽，必须对编码输出的码流进行缓冲，在信道带宽不足时将码流存储起来，在信道带宽富裕时进行传送。,如果信源连续输出a2，则编码1码流输出为1000bit/秒，浪费信道带宽。如果信源连续输出a5，则编码1码流输出为4000bit/秒，信道带宽又不足。,最小方差Huffman编码算法,1,1,a5,1,1,1,1,a5,1，1,1，1,1,1,1,1,1,1,a5,0,1,1,1,1,a2,1，1,1，1,0,1,0,1,1,a1,1，1,1000symbol/s,2200bit/s,最小方差Huffman编码算法,编码的码长方差越大，缓冲必须越大；编码的码长方差越小，缓冲可以越小；因此，最佳的Huffman编码为最小方差Huffman编码。,如果信源连续输出a2，则编码1码流输出为1000bit/秒，浪费信道带宽。如果信源连续输出a5，则编码1码流输出为4000bit/秒，信道带宽又不足。,Huffman编码特点,哈夫曼编码方法构造出来的码不是惟一的。,Huffman编码特点,Huffman编码的码长虽然是可变的，但却不需要另外附加同步代码。,例如，10011011101111按照编码1可解释为a1a2a3a4a5。又如，100011010011按照编码3可解释为a1a2a3a4a5。,规范Huffman码字,规范的霍夫曼码字是从Huffman码字从特意挑选出来的，目的是便于在译码时检测码字的长度。,下面两个编码中，编码2为规范的Huffman码字。,规范Huffman码字,规范的Huffman码字这样产生first6=0;forx:=5downto1dofirstx=(firstx+1+numlx+1)/2其中，y表示取不小于y的最小整数。,规范Huffman码字,规范Huffman码字,规范的Huffman码字可以这样解码x:=1;inputv;whilevfirstxappendnextinputbittov;x:=x+1;endwhile;,例如码流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开始)，即符号7,Huffman编码编程实现方法,编码开始,概率统计,建立码树/码表,传送码表,编码-传送压缩码流,编码结束,解码开始,接收码表,恢复码树/码表,接收压缩码流,解码-恢复原码,解码结束,Huffman编码编程,编码开始,概率统计,建立码树/码表,传送码表,编码-传送压缩码流,编码结束,对原始数据出现次数进行统计，将次数存储在数组counter中。,Huffman编码编程,编码开始,概率统计,建立码树/码表,传送码表,编码-传送压缩码流,编码结束,利用统计结果counter和链表typedefstructintweit;/权值intlchd;/左孩子intrchd;/右孩子intpart;/父节点hufmtree;hufmtree*htree;建立Huffman码树和码表。,Huffman编码编程,编码开始,概率统计,建立码树/码表,传送码表,编码-传送压缩码流,编码结束,码表的传送可以有多种形式，比如传送统计数组counter，传送Huffman码树，传送Huffman码表都可以。,Huffman编码编程,编码开始,概率统计,建立码树/码表,传送码表,编码-传送压缩码流,编码结束,每个字节原始数据用一个长度不同的0、1序列表示，8个0、1要打包成1个字节，如abcde压缩后为101,10,1111,110，0110则打包成0 xB7,0 xE6,Huffman编码编程,编码开始,概率统计,建立码树/码表,传送码表,编码-传送压缩码流,编码结束,每个字节原始数据用一个长度不同的0、1序列表示，8个0、1要打包成1个字节，如abcde压缩后为101,10,1111,110，0110则打包成0 xB7,0 xE6,整个压缩后的码流长度不一定能够被8整除，必须加以处理。,Huffman编码编程,压缩对abc.txt进行压缩，压缩结果存储在abc_code.txt中。解压对abc_code.txt进行解压，恢复结果存储在abc_decode.txt中。评价对比abc.txt和abc_decode.txt，如果完全一致，表明压缩/解压过程正确，反之不正确。对比abc.txt和abc_decode.txt文件大小，计算压缩比。,自适应Huffman编码AdaptiveHuffmancoding(DynamicHuffmancoding),对信源进行哈夫曼编码后形成了一个哈夫曼编码表，若要正确解码必须依照此表。于是在信源存储与传输过程中，必须首先考虑此表的存储与传输，故此表也占有一定的比特数。一种解决方法是使用默认的哈夫曼编码表,Huffman编码需要实现知道输入符号集的概率分布，为了进行编码需要先对数据计算概率分布，然后再对数据进行编码，需要对数据扫描两遍。,自适应Huffman编码,自适应Huffman编码不需要事先计算概率分布，能够在编码/解码过程中自动建立Huffman编码树，只需要对数据扫描一遍因而得到了广泛应用。,，而更好的方法是,自适应Huffman编码AdaptiveHuffmancoding(DynamicHuffmancoding),自适应Huffman编码的思想是从一个空的Huffman编码树开始，空的Huffman编码树仅包含一个空节点NYT(NotYetTransmitted)，表示还没有开始数据传送。,NYT,自适应Huffman编码AdaptiveHuffmancoding(DynamicHuffmancoding),自适应Huffman编码的思想是从一个空的Huffman编码树开始，空的Huffman编码树仅包含一个空节点NYT(NotYetTransmitted)，表示还没有开始数据传送。,NYT,读入的第1个符号，不做压缩直接进入输出码流，同时将其添加进树中赋予码字。,1,1,1,0,a,输入a，输出01100001,自适应Huffman编码AdaptiveHuffmancoding(DynamicHuffmancoding),NYT,2,1,1,0,a,每读入1个新的符号，输出NYT，然后将新符号不做压缩直接进入输出码流，同时将其添加进树中赋予码字。,输入b，输出001100010,1,1,b,1,0,NYT,1,1,1,0,a,自适应Huffman编码AdaptiveHuffmancoding(DynamicHuffmancoding),如果读入一个已有的符号，则直接输出编码，实现数据压缩。,NYT,2,1,1,0,a,输入b，输出01,1,1,b,1,0,自适应Huffman编码AdaptiveHuffmancoding(DynamicHuffmancoding),如果读入一个已有的符号，则直接输出编码，实现数据压缩。,NYT,3,1,1,0,a,2,2,b,1,0,每读入一个已有的符号，需要修改权值，更新码树。,NYT,3,2,1,0,b,1,1,a,1,0,自适应Huffman编码AdaptiveHuffmancoding(DynamicHuffmancoding),每读入1个新的符号，输出NYT，然后将新符号不做压缩直接进入输出码流，同时将其添加进树中赋予码字。,NYT,3,2,1,0,b,1,1,a,1,0,NYT,4,2,1,0,b,2,1,a,1,0,输入c，输出0001100010,1,c,1,0,自适应Huffman编码AdaptiveHuffmancoding(DynamicHuffmancoding),如果读入一个已有的符号，则直接输出编码，实现数据压缩。同时修改权值，更新码树。,NYT,5,2,1,0,b,3,2,a,1,0,输入a，输出01,1,c,1,0,NYT,4,2,1,0,b,2,1,a,1,0,1,c,1,0,自适应Huffman编码AdaptiveHuffmancoding(DynamicHuffmancoding),数据abbca的自适应Huffman编码为