霍夫曼编码

霍夫曼编码HuffmanCoding长春理工大学080212418高延邦Yourcompanyslogan目录一、什么是编码二、霍夫曼编码简介三、霍夫曼编码的熵四、霍夫曼编码（一）霍夫曼编码过程（二）霍夫曼树的构建（三）霍夫曼表五、霍夫曼编码特点Yourcompanyslogan一.什么是编码编码是将源对象内容按照一种标准转换为一种标准格式内容。源对象标准编码后GooddayG112237456o2d3d4a5y67Yourcompanyslogan二.霍夫曼编码简介霍夫曼编码是不定长编码，即代表各元素的码字长度不等。该方法完全依据字符出现概率来构造平均长度最短的码字，有时称之为最佳编码。该编码是基于不同符号的概率分布，在信息源中出现概率越大的符号，相应的码越短；出现概率越小的符号，其码越长，从而达到用尽可能少的码符号表示源数据。它在变长编码中是最佳的。在计算机信息处理中，“霍夫曼编码”是一种一致性编码法（又称熵编码法）。DavidAlbertHuffman戴维·霍夫曼Yourcompanyslogan三、霍夫曼编码的熵一个事件集合x1,x2,……xn,处于一个基本概率空间，其相应概率为p1,p2,……pn,且p1,p2,……pn之和为1，每一个事件的信息量为I(xk)=-logn(pk),如定义在空间中的每一事件的概率不相等的平均不肯定程度或平均信息量叫做熵H，则H=E{I(xk)}=∑pkI(xk)=-∑pkloga(pk)。对于图像来说，n=2m个灰度级xi,则p(xi)为各灰度级出现的概率，熵即表示平均信息量为多少比特，换句话说，熵是编码所需比特数的下限，即编码所需的最少比特。编码一定要用不比熵少的比特数编码才能完全保持原图像的信息，这是图像压缩的下限。当a=2是，H的单位是比特。Yourcompanyslogan四、霍夫曼编码设信息源空间为[A*P]:{A:a1a2……an}{P(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序列（从码数的根到终节点）。创建霍夫曼表。压缩编码时，将码值用码字代替。（一）霍夫曼编码过程Yourcompanyslogan（二）霍夫曼树的构建霍夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束。这里举个例子说明如何生成霍夫曼树。假设对由a1、a2、a3、a4、a5、a6、a7、a8八个信源符号组成的源信息字符串:“a1a1a2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8”进行霍夫曼编码。首先应对信息中各数字出现的次数进行统计如下：码值a1a2a3a4a5a6a7a8次数22343331概率0.10.10.150.20.150.150.10.05熵H＝-0.1*log2(0.1)-0.1*log2(0.1)-0.15*log2(0.15)-0.2*log2(0.2)-0.15*log2(0.15)-0.15*log2(0.15)-0.1*log2(0.1)-0.05*log2(0.05)=2.9087(bit)Yourcompanyslogan具体过程是这样的，先将所有符号排成一行，构成8个最底层节点。首先将这些节点中最小两个概率值相加：0.05+0.1=0.15,得到新的节点这时拥有的概率值为0.2,0.1,0.1,0.15,0.15,0.15,0.15。Yourcompanyslogan再将两个最小的概率值相加得到新的节点......直到得到根节点概率为1.0为止。相加时，对于概率值相等的多个节点，可以任意选取。除根节点外，设节点左边分支为0，右边分支为1（也可以反过来）。这样，生成的霍夫曼树如下图所示：Yourcompanyslogan对于各值（码值）的代码（码字）就是从根节点出发到底层节点所经历的分支序列。如a4的代码（码字）为00，a6的码字为111......通常a4和a6等称为码值，00和111等称为码字。所有码值和码字对应关系如下表所示：Yourcompanyslogan（三）霍夫曼表将所有码值和码字的关系整理成一张表，为了整字节输出码字，表中还含有各码字的长度。这种表就称为霍夫曼表。本例霍夫曼表如表所示：Yourcompanyslogan进行压缩编码时，只要将码值用码字代替即可。所以源符a1a1a2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8编码为：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%Yourcompanyslogan五、霍夫曼编码的特点1.霍夫曼方法构造出来的码不是唯一的。原因：①在给两个分支赋值时,可以是左支(或上支)为0,也可以是右支(或下支)为0,造成编码的不唯一。②当两个消息的概率相等时,谁前谁后也是随机的,构造出来的码字就不是唯一的。2.霍夫曼编码码字字长参差不齐。3.霍夫曼编码对不同的信源的编码效率是不同的。当信源概率相等时,其编码效率最低。只有在概率分布很不均匀时,霍夫曼编码才会收到显著的效果。4.解码时,必须参照霍夫曼编码表才能正确译码。在信源的存储与传输过程中必须首先存储或传输这一霍夫曼编码表，在实际计算压缩效果时,必须考虑霍夫曼编码表占有的比特数。在某些应用场合,信源概率服从于某一分布或存在一定规律(这主要由大量的统计得到),这样就可以在发送端和接收端固定霍夫曼编码表,在传输数据时就省去了传输霍夫曼编码表,这种方法称为霍夫曼编码表缺省使用。Yourcompanyslogan谢谢大家!