霍夫曼编码.pptx

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版标题样式,Click to edit Master text styles,#,单击此处编辑母版标题样式,Click to edit Master text styles,#,单击此处编辑母版标题样式,Click to edit Master text styles,#,单击此处编辑母版文本样式,第二级,第三级,第四级第五级,单击此处编辑母版标题样式,Your company slogan,霍夫曼编码,Huffman Coding,长春理工大学,080212418,高延邦,图像无损压缩,目录,一、,什么是编码,二、,霍夫曼编码简介,三、,霍夫曼编码的熵,四、,霍夫曼编码,（一）,霍夫曼编码过程,（二）,霍夫曼树的构建,（三）,霍夫曼表,五、,霍夫曼编码特点,一,.,什么是编码,编码是将源对象内容按照一种标准转换为一种标准格式内容。,源对象,标准,编码后,Good day,G,1,12237456,o,2,d,3,d,4,a,5,y,6,7,二,.,霍夫曼编码简介,霍夫曼编码是不定长编码，即代表各元素的码字长度不等。,该方法完全依据字符出现概率来构造平均长度最短的码字，有时称之为最佳编码。,该编码是基于不同符号的概率分布，在信息源中出现概率越大的符号，相应的码越短；出现概率越小的符号，其码越长，从而达到用尽可能少的码符号表示源数据。它在变长编码中是最佳的。在计算机信息处理中，“霍夫曼编码”是一种一致性编码法（又称,熵编码法,）。,David Albert Huffman,戴维,霍夫曼,三、,霍夫曼编码,的熵,一个事件集合,x,1,x,2,x,n,处于一个基本概率空间，其相应概率为,p,1,p,2,p,n,且,p,1,p,2,p,n,之和为,1,，每一个事件的信息量为,I(x,k,)=-log,np,k,),如定义在空间中的每一事件的概率不相等的平均不肯定程度或平均信息量叫做熵,H,，则,H=EI(x,k,)=p,k,I(x,k,)=-p,k,log,a(,p,k),。,对于图像来说，,n=2,m,个灰度级,x,i,则,p(x,i,),为各灰度级出现的概率，熵即表示平均信息量为多少比特，换句话说，熵是编码所需比特数的下限，即编码所需的最少比特。编码一定要用不比熵少的比特数编码才能完全保持原图像的信息，这是图像压缩的下限。当,a=2,是，,H,的单位是比特。,四、,霍夫曼编码,设信息源空间为,A*P:A:a1 a2 anP(A):P(a1)P(a2)P(a3)P(an),其中,P(ak)=1,先用,r,个码的号码符号集,X:x1,x2,xr,对信源,A,中的每一个符号,ak,进行编码。编码过程如下：,把信源符号,ai,按其出现的概率的大小顺序排列起来；,把最末两个具有最小概率的元素之概率加起来；,把该概率之和同其余概率由大到小排队，然后再把两个最小概率加起来，再排队；,重复步骤,(2),、,(3),直到概率和达到,1,为止,;,在每次合并消息时，将被合并的消息赋以,1,和,0,或,0,和,1,；,寻找从每个信源符号到概率为,1,处的路径，记录下路径上的,1,和,0,；,对每个符号写出,1,、,0,序列（从码数的根到终节点）。,创建霍夫曼表。,压缩编码时，将码值用码字代替。一）霍夫曼编码过程,（二）,霍夫曼树的构建,霍夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束。这里举个例子说明如何生成霍夫曼树。假设对由,a,1,、,a,2,、,a,3,、,a,4,、,a,5,、,a,6,、,a,7,、,a,8,八个信源符号组成的源信息字符串,:,“,a,1,a,1,a,2,a,2,a,3,a,3,a,3,a,4,a,4,a,4,a,4,a,5,a,5,a,5,a,6,a,6,a,6,a,7,a,7,a,8,”,进行霍夫曼编码。首先应对信息中各数字出现的次数进行统计,如下：,码值,a,1,a,2,a,3,a,4,a,5,a,6,a,7,a,8,次数2,2,3,4,3,3,3,1,概率,0.1,0.1,0.15,0.2,0.15,0.15,0.1,0.05,熵,H,-0.1*log,2,(0.1)-0.1*log,2,(0.1)-0.15*log,2,(0.15)-0.2*log,2,(0.2)-0.15*log,2,(0.15)-0.15*log,2,(0.15)-0.1*log,2,(0.1)-0.05*log,2,(0.05)=2.9087(bit),具体过程是这样的，先将所有符号排成一行，构成,8,个最底层,节点。首先将这些节点中最小两个概率值相加：,0.05+0.1=0.15,得到新的,节点这时拥有的概率值为,0.2,0.1,0.1,0.15,0.15,0.15,0.15,。,再将两个最小的概率值相加得到新的节点,.,直到得到根节点概率为,1.0,为止。相加时，对于概率值相等的多个节点，可以任意选取。除根节点外，设节点左边分支为,0,，右边分支为,1,（也可以反过来）。这样，生成的霍夫曼树如下图所示：,对于各值（码值）的代码（码字）就是从根节点出发到底层节点所经历的分支序列。如,a,4,的代码（码字）为,00,，,a,6,的码字为,111.,通常,a,4,和,a,6,等称为码值，,00,和,111,等称为码字。所有码值和码字对应关系如下表所示：,（三）,霍夫曼表,将所有码值和码字的关系整理成一张表，为了整字节输出码字，表中还含有各码字的长度。这种表就称为霍夫曼表。本例霍夫曼表如表所示,：,进行压缩编码时，只要将码值用码字代替即可。所以源符,a1 a1 a2 a2 a3 a3 a3 a4 a4 a4 a4 a5 a5 a5 a6 a6 a6 a7 a7 a8,编码为：,0100100110111011011010000000011011011010000100001001,。,平均码长,B=0.1*3+0.1*3+0.15*3+0.2*2+0.15*3+0.15*3+0.1*4+0.05*4,2.95(b),熵,H,2.9087,编码效率,N=H/B=2.9087/2.95=98.6%,五、,霍夫曼编码的特点,1.,霍夫曼方法构造出来的码不是唯一的。,原因：,在给两个分支赋值时,可以是左支,(,或上支,),为,0,也可以是右支,(,或下支,),为,0,造成编码的不唯一。,当两个消息的概率 相等时,谁前谁后也是随机的,构造出来的码字就不是唯一的。,2.,霍夫曼编码码字字长参差不齐,。,3.,霍夫曼编码对不同的信源的编码效率是不同的。,当信源概率相等时,其编码效率最低。只有在概率分布很不均匀时,霍夫曼编码才会收到显著的效果,。,4.,解码时,必须参照霍夫曼编码表才能正确译码。,在信源的存储与传输过程中必须首先存储或传输这一霍夫曼编码表,，,在实际计算压缩效果时,必须考虑霍夫曼编码表占有的比特数。在某些应用场合,信源概率服从于某一分布或存在一定规律,(,这主要由大量的统计得到,),这样就可以在发送端和接收端固定霍夫曼编码表,在传输数据时就省去了传输霍夫曼编码表,这种方法称为霍夫曼编码表缺省使用。,谢谢大家,!,