Huffman霍夫曼编码

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2014/4/15,#,4.2,霍夫曼编码,霍夫曼编码,(Huffman Coding),是一种编码方法，霍夫曼编码是可变字长编码,(VLC),的一种。,1952,年，,David A.Huffman,在麻省理工攻读博士时所提出一种编码方法，并发表于,一种构建极小多余编码的方法,（,A Method for the Construction of Minimum-Redundancy Codes）,一文,。,霍夫曼编码介绍,David A.Huffman,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作,Huffman,编码。,在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。,1951,年，霍夫曼和他在,MIT,信息论的同学需要选择是完成学期报告还是期末考试。,导师,RobertM.Fano,给他们的学期报告的题目是，查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者克劳德,香农共同研究过类似编码的导师。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法,Shannon-Fano,编码的最大弊端自顶向下构建树,。,霍夫曼（,Huffman,）编码是一种统计编码。属于无损（,lossless,）压缩编码。,以霍夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。,根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素,(,如字母,),出现的次数越多，其编码的位数就越少。,广泛用在,JPEG,MPEG,H.2X,等各种信息编码标准中。,霍夫曼编码的步骤,霍夫曼编码的具体步骤如下：,）将信源符号的概率按减小的顺序排队。,）把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在上部，直到最后变成概率。,3,）将每对组合的上边一个指定为,1,，下边一个指定为,0,（或相反）。,）画出由概率处到每个信源符号的路径，顺序记下沿路径的和，所得就是该符号的霍夫曼码字。,信源熵的定义：,概率空间中每个事件所含有的自信息量的数学期望称信源熵或简称熵,(entropy),，,记为：,单位,:,以,2,为底的对数时是比特,/,符号,(bit/symbol);,以,e,为底的对数时是奈特,/,符号,(nat/symbol);,以,10,为底的对数时是哈特,/,符号,(hart/symbol),其中 表示某个事件,x,i,的信息量。,I(x,i,)=,logp(x,i,),平均码长,编码效率,例：现有一个由,5,个不同符号组成的,30,个符号的字,符串：,BABACACADADABBCBABEBEDDABEEEBB,计算,(1),该字符串的霍夫曼码,(2),该字符串的熵,(3),该字符串的平均码长,H(S),=(8/30)log,2,(30/8)+(10/30)log,2,(30/10)+(3/30)log,2,(30/3)+(4/30)log,2,(30/4)+(5/30)log,2,(30/5)=(44.3136,24.5592)/9.0308,2.1874 (Sh),例：,平均码长：,(2,8,2,10,3,3,3,4,2,5)/30,2.233,位,/,符号,类似书中例,4-6,0,0,0,0,1,1,1,1,霍夫曼编码的主要特点：,1.,霍夫曼编码构造的码字不唯一；,2.,霍夫曼编码是变长编码，硬件实现比较困难；,3.,采用霍夫曼编码，要传送编码表，占用传送时间；,4.,霍夫曼编码是变长编码，出错时难以识别；霍夫曼编码方法不唯一，因为编码时的,0,和,1,是任意给的，另外在两个符号有相同概率时的编码过程不唯一，造成编码结果不同，但平均码长相同。其次对信源进行缩减时两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者,在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的霍夫曼码此时将影响码字的长度，一般将合并的概率放在上面，这样可以获得较小的码方差。,霍夫曼树,1,、有关霍夫曼树的相关概念,霍夫曼树：指所有叶子结点的二叉树中带权路径长度最小的二叉树。,节点的带权路径长度：从树的根节点到该节点的路径长度与该节点权的乘积。,树的带权路径长度：树中所有叶子结点的带权路径长度之和。,2,、霍夫曼算法,（,1,）根据给定的,n,个权值,w1,w2,.,wn,构造,n,棵二叉树的集合,F=T1,T2,.,Tn,，其中每棵二叉树,Ti,中只有一个带权为,wi,的根结点，其左右子树均空。,（,2,）在,F,中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。,（,3,）在,F,中删除这两棵树，同时将新得到的二叉树加入,F,中。,（,4,）重复（,2),和（,3),，直到,F,中只含一棵树为止。这棵树便是最优二叉树。,当信源符号的出现概率为,2,的整数次幂时霍夫曼编码的效率才能达到,100%,。当符号出现概率不是,2,的整数次幂时编码效率下降,。,香,农第一定理：（又称为变长编码定理）,设离散无记忆信源,S,包含,r,个符号，信源发出,N,重符号序列 ，则此信源可发出 个不同的符号序列消息，其中第,j,个符号序列消息的出现概率为 ，其信源编码后所得,的,信源编码基本定理,二进制代码组长度为 ，代码组的平均长度为,它满足,当,N,趋于无限大时，和,H(S),之间的关系为,书中例,4-8,JEPEG,采用将码字截断为“前缀码（,SSSS,）,+,尾码”的方法，对码表进行了简化：,霍夫曼编码不仅适用于压缩文本文件，经过符号合并后也可用于二进制文件。但在实用中，霍夫曼编码的输入符号数常受限于可实现的码表大小。,截断霍夫曼编码,尾码为,DIFF,的,B,位,原码，若,DIFF,0,反码，若,DIFF,0,前缀码用来指明尾码的有效位数（设为,B,位），用标准的霍夫曼编码；尾码则直接采用,B,位自然二进码（对于给定的前缀码它为定长码，高位在前）。对于,8,位量化的图像，,SSSS,值的范围为,011,，故其码表只有,12,项。根据,DIFF,的幅度范围由表,4.2,查出前缀码字和尾码的位数后，则可按以下规则直接写出尾码的码字,即,在静态霍夫曼编码中，要构造编码树必须提前统计被编码对象中的符号出现概率，因此必须对输入符号流进行两遍扫描，第一遍统计符号出现概率并构造编码树，第二遍进行编码，这在很多实际应用的场合中之不能接受的。,其次，在存储和传送霍夫曼,按此规则，当,DIFF,0,时，尾码的最高位是“,1,”；而当,DIFF0,时则为“,0,”。解码时则可借此来判断,DIFF,的正负。,书中例,49,自适应霍夫曼编码提出的目的和意义：,编码时，必须先存储和传送霍夫曼编码树。再次，静态编码树构造方案不能对输入符号流的局部统计规律变化做出反应。这些问题使得静态霍夫曼编码在实际中并未得到广泛的应用。为了解决静态,Huffman,编码的缺点，人们提出了自适应,Huffman,编码这种方案不需要事先扫描输入符号流，而是随着编码的进行同时构造,Huffman,树，因此，只需要进行一次扫描即可。在接收端伴随着解码过程同时进行着编码树的构造。自适应霍夫曼编码解决了静态编码树所面临的主要问题，因此在实际领域比如在高质量的图像和视频流传输中中获得了广泛的应用。,自适应霍夫曼编码的原理：,这种方案在不需要事先构,Huffman,树，而是随着编码的进行，逐步构造,Huffman,树。同时，这种编码方案对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）。,由于自适应,Huffman,编码算法采用了先编码，后调整编码树的方案，相应的解码算法比较简单。解码算法也使用仅有唯一的,NYT,节点的编码树作为初始状态，然后根据,Huffman,编码数据流，对符号进行还原。每次处理完一个符号，就使用这个符号调整编码树。这样，在每一次输入新的符号,之前，,Huffman,树都处于与进行编码时使用的的,Huffman,树完全相同的状态，保证了解码的正确性。,自适应霍夫曼编码是一种扩展的熵编码方法，相比于先前的静态霍夫曼编码，自适应霍夫曼编码具有仅需单遍扫描、无需传送编码树、能够对输入符号流的局部统计规律变化做出反应等一系列优点，具有更高的压缩效率。这些优点使得它在一些实时性、可靠性要求比较高的场合得到了广泛的应用，被称为近代压缩算法的灵魂。,利用霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负,n,次方的形式，则无法达到熵极限。,输入符号数受限于可实现的码表尺寸,译码复杂,需要实现知道输入符号集的概率分布,没有错误保护功能,霍夫曼编码的局限性,THANK,YOU!,