第二章 信息熵与Huffman编码

多媒体技术信息熵与Huffman编码徐家臻本章内容Huffman编码算法信息论的一些基础知识编码(Code)定长编码ASCII–每个字母8位‘A’:01000001变长编码a:0b:1c:00d:11平均编码长度)()()(xLxpxLcx其中，x表示各种符号p(x)表示该符号出现的概率(频率)L(x)表示该符号对应码字的长度(位数)唯一可解码编码是唯一可解的吗？a:0b:1c:00d:11接收到00011唯一可译码接收到11000000010110-00-00-00-10前缀码定义如果没有一个码字是另一个码字的前缀，则该码称为前缀码特点唯一可译即时可译，译码不需要等待后续码字为什么唯一即时可译？xabcdC(x)010110111最优编码最优编码的定义最小的唯一可解码两个问题最优的前缀码设计方法是什么？最优的前缀码是不是最优编码？)()()(xLxpxLcxHuffman编码给定m个权值{w1,w2,…,wm}①构造由m棵二叉树组成的树林F={T1,T2,…,Tm}，其中每棵树Ti只有一个根结点，且根结点的权值为wi；②在树林中选取两棵根结点权值最小的和次小的二叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。③将新的二叉树加入到树林F中，去除原两棵权值最小的树；④重复2、3步骤，直至F中只剩一棵树为止。Huffman编码举例a2字母abcde频率24211b4c2d1e1Huffman编码举例字母abcde频率24211d1e12Huffman编码举例字母abcd+e频率2422d1e12a2c24Huffman编码举例字母a+cbd+e频率442d1e12a2c24Huffman编码举例字母a+c+d+eb频率64d1e12a2c246Huffman编码举例字母all频率10d1e12a2c246b410Huffman编码举例d1e12a2c246b41001001011字母编码a100b0c101d110e111Huffman编码步骤给定m个权值{w1,w2,…,wm}①构造由m棵二叉树组成的树林F={T1,T2,…,Tm}，其中每棵树Ti只有一个根结点，且根结点的权值为wi；②在树林中选取两棵根结点权值最小的和次小的二叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。③将新的二叉树加入到树林F中，去除原两棵权值最小的树；④重复2、3步骤，直至F中只剩一棵树为止。最优前缀码必要条件与Huffman树的构造方式最优前缀码应具有的性质出现频率高的符号的码字长度比出现频率低的符号的码字长度短出现频率最低的两个符号，码字长度相等最优编码对应的树的中间节点必有左右两个分支如果把中间节点的所有叶子节点对应的符号看成一个符号组合，把中间节点改成组合对应的叶子结点，那么若原来的树是最优的，修改后的树也是最优的。最优编码最优编码的定义最小的唯一可解码两个问题最优的前缀码设计方法是什么？最优的前缀码是不是最优编码？)()()(xLxpxLcx√？Kraft-McMillan不等式McMillan定理假定C是由N个长度为l1,l2,…,lN码字组成的编码表，如果C是唯一可解码的，那么必有12)(1NiliCKKraft定理假定N个整数l1,l2,…,lN满足不等式12)(1NiliCK那么必定可以找到一种N个码字组成的前缀码，其码字长度分别为l1,l2,…,lNMcMillan定理证明看K(C)的n次方NiNiNinlllNinlNilNilnNiliniiiniii11121)...(11211121212...2...222),...,,max(,2)(21NnlnkkknllllACK其中McMillan定理证明Ak表示n个C中的码字可以组合成长度k的串数目对于2进制串，只可能有2k种取值，由于C是唯一可解码的，所以每个取值对应唯一的C中码字的组合因此，Ak2k),...,,max(,2)(21NnlnkkknllllACK其中nlnkkknlnkkknnnlACK1222)(如果K(C)1，当n充分大时，左边右边。所以K(C)≤1从Kraft-McMillan定理得到的结论假定C是由N个长度为l1,l2,…,lN码字组成的编码表，如果C是唯一可解码的，那么必有12)(1NiliCK假定N个整数l1,l2,…,lN满足不等式12)(1NiliCK那么必定可以找到一种N个码字组成的前缀码，其码字长度分别为l1,l2,…,lN结论：对于任意唯一可解码，都可以找到对应的前缀码，其码字长度完全相同。最优的前缀码是最优编码。统计编码压缩的上限Huffman编码可以产生最优编码最优编码的平均长度是多少？或者说，统计编码压缩的上限是多少？信息量与信息熵用什么作为信息的量度?信息的不确定程度信息带来的“惊奇”程度信息量与信息描述的事件产生的概率密切相关Shannon认为x事件的信息量I(x)应该具有的性质（用p(x)代表x事件发生的概率）I(x)0p(x)越小，I(x)越大如果事件x，y独立同分布，即p(x,y)=p(x)p(y)时，I(x,y)=I(x)+I(y)I(x)=-logp(x)对于二进制编码：I(x)=-log2p(x)，单位是bit信息熵信息熵是所有可能事件的信息量的期望（平均）H与p的关系假设有N个事件，当每个事件发生的概率相等，即p(x1)=p(x2)=…=p(xN)时，H最大，为log2N证明：利用Jensen不等式)(log)())(()(2xpxpxIExHx信息熵的性质)()1()())1((bfafbaf均相等时取等号，当且仅当其中iMiiiMiiiMiiixfxf1,0)()(111凸函数的定义Jensen不等式所以NxpxpxpxpxpxpxHNiiiNiiiNiiilog)(1)(log)(1log)()(log)()(111最优编码平均长度和信息熵的关系1HLcH21121211()log()()2()log()log20iiNNiiiiiilNiiiNliHLcpxpxlpxpxpx证明左半部分(Kraft-McMillan不等式)最优编码平均长度和信息熵的关系1HLcH1)(1log)(1log22iiixplxp证明右半部分定义一组整数)(1log2iixpl那么NiiNilxpi111)(2最优编码平均长度和信息熵的关系1)1)(1)(log()(121HxpxplxpLcNiiiNiii根据Kraft-McMillan定理，存在码字长度为{li}的唯一可解码，其平均长度1HLcH因此最优编码平均长度和信息熵举例概率码字1/201/4101/41101/8111熵=Huffman平均编码长度=1.75Huffman编码缺点没有纠错功能。如果码串有错误，会引起一连串的错误，造成错误传播(errorpropagation)很难随意查找中间的内容优点简单、高效模型无关广泛应用于各种压缩领域Huffman编码的其他变体自适应Huffman编码统计和编码同时进行扩展Huffman编码对符号组而不是单个符号编码下次课的内容Huffman编码的C语言实现二叉树优先级队列（堆排序）