《霍夫曼编码学习.pptx》由会员分享,可在线阅读,更多相关《霍夫曼编码学习.pptx(14页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、目录一、什么是编码二、霍夫曼编码简介三、霍夫曼编码的熵四、霍夫曼编码(一)霍夫曼编码过程(二)霍夫曼树的构建(三)霍夫曼表五、霍夫曼编码特点第1页/共14页一.什么是编码 编码是将源对象内容按照一种标准转换为一种标准格式内容。源对象标准编码后Good dayG112237456o2d3d4a5y6 7第2页/共14页 二.霍夫曼编码简介 霍夫曼编码是不定长编码,即代表霍夫曼编码是不定长编码,即代表各元素的码字长度不等。各元素的码字长度不等。该方法完该方法完全依据字符出现概率来构造平均长全依据字符出现概率来构造平均长度最短的码字,有时称之为最佳编度最短的码字,有时称之为最佳编码。码。该编码是基于
2、不同符号的概率该编码是基于不同符号的概率分布,在信息源中出现概率越大的分布,在信息源中出现概率越大的符号,相应的码越短;出现概率越符号,相应的码越短;出现概率越小的符号,其码越长,从而达到用小的符号,其码越长,从而达到用尽可能少的码符号表示源数据。它尽可能少的码符号表示源数据。它在变长编码中是最佳的。在计算机在变长编码中是最佳的。在计算机信息处理中,信息处理中,“霍夫曼编码霍夫曼编码”是一是一种一致性编码法(又称种一致性编码法(又称 熵编码法熵编码法)。)。David Albert Huffman戴维霍夫曼第3页/共14页三、霍夫曼编码的熵 一个事件集合一个事件集合x x1 1,x,x2 2,
3、x,xn n,处于一个基本概率空间,其处于一个基本概率空间,其相应概率为相应概率为p p1 1,p,p2 2,p,pn n,且且p p1 1,p,p2 2,p,pn n之和为之和为1 1,每一,每一个事件的信息量为个事件的信息量为I(xI(xk k)=-log)=-logn n(p(pk k),),如定义在空间中的每如定义在空间中的每一事件的概率不相等的平均不肯定程度或平均信息量叫一事件的概率不相等的平均不肯定程度或平均信息量叫做熵做熵HH,则,则 H=EI(xH=EI(xk k)=p)=pk kI(xI(xk k)=-p)=-pk klogloga(a(p pk)k)。对于图像来说,对于图像
4、来说,n=2n=2mm个灰度级个灰度级x xi i,则则p(xp(xi i)为各灰度级出为各灰度级出现的概率,熵即表示平均信息量为多少比特,换句话说,现的概率,熵即表示平均信息量为多少比特,换句话说,熵是编码所需比特数的下限,即编码所需的最少比特。熵是编码所需比特数的下限,即编码所需的最少比特。编码一定要用不比熵少的比特数编码才能完全保持原图编码一定要用不比熵少的比特数编码才能完全保持原图像的信息,这是图像压缩的下限。当像的信息,这是图像压缩的下限。当a=2a=2是,是,HH的单位的单位是比特。是比特。第4页/共14页四、霍夫曼编码设信息源空间为设信息源空间为A*P:A:a1 a2 anP(A
5、):P(a1)A*P:A:a1 a2 anP(A):P(a1)P(a2)P(a3)P(an)P(a2)P(a3)P(an)其中其中 P(ak)=1,P(ak)=1,先用先用r r个码的号码个码的号码符号集符号集X:x1,x2,xrX:x1,x2,xr对信源对信源A A中的每一个符号中的每一个符号akak进行编进行编码。编码过程如下:码。编码过程如下:把信源符号把信源符号aiai按其出现的概率的大小顺序排列起来;按其出现的概率的大小顺序排列起来;把最末两个具有最小概率的元素之概率加起来;把最末两个具有最小概率的元素之概率加起来;把该概率之和同其余概率由大到小排队,然后再把两个把该概率之和同其余概
6、率由大到小排队,然后再把两个最小概率加起来,再排队;最小概率加起来,再排队;重复步骤重复步骤 (2)(2)、(3),(3),直到概率和达到直到概率和达到 1 1 为止为止 ;在每次合并消息时,将被合并的消息赋以在每次合并消息时,将被合并的消息赋以1 1和和0 0或或0 0和和1 1;寻找从每个信源符号到概率为寻找从每个信源符号到概率为1 1处的路径,记录下路径处的路径,记录下路径上的上的1 1和和0 0;对每个符号写出对每个符号写出11、00序列(从码数的根到终节点)。序列(从码数的根到终节点)。创建霍夫曼表。创建霍夫曼表。压缩编码时,将码值用码字代替。压缩编码时,将码值用码字代替。(一)霍夫
7、曼编码过程第5页/共14页(二)霍夫曼树的构建霍夫曼编码实际上构造了一个码树,码树从最上层的端点霍夫曼编码实际上构造了一个码树,码树从最上层的端点开始构造,直到树根结束。这里举个例子说明如何生成霍夫开始构造,直到树根结束。这里举个例子说明如何生成霍夫曼树。假设对由曼树。假设对由a a1 1、a a2 2、a a3 3、a a4 4、a a5 5、a a6 6、a a7 7、a a8 8八个信源八个信源符号组成的源信息字符串符号组成的源信息字符串:“a a1 1 a a1 1 a a2 2 a a2 2 a a3 3 a a3 3 a a3 3 a a4 4 a a4 4 a a4 4 a a4
8、 4 a a5 5 a a5 5 a a5 5 a a6 6 a a6 6 a a6 6 a a7 7 a a7 7 a a8 8”进行霍夫曼编码。首先应对进行霍夫曼编码。首先应对信息中各数字出现的次数进行统计信息中各数字出现的次数进行统计如下:如下:码值码值码值码值 a a1 1a a2 2a a3 3 a a4 4 a a5 5 a a6 6a a7 7 a a8 8次数次数次数次数 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)
9、-0.15*log2(0.15)-0.15*log2(0.15)-0.1*log2(0.1)-0.05*log2(0.05)=2.9087(bit)第6页/共14页具体过程是这样的,先将所有符号排成一行,构成具体过程是这样的,先将所有符号排成一行,构成具体过程是这样的,先将所有符号排成一行,构成具体过程是这样的,先将所有符号排成一行,构成8 8个最底层个最底层个最底层个最底层 节点。首先将这些节点中最小两个概率值节点。首先将这些节点中最小两个概率值节点。首先将这些节点中最小两个概率值节点。首先将这些节点中最小两个概率值相加:相加:相加:相加:0.05+0.1=0.15,0.05+0.1=0.1
10、5,得到新的得到新的得到新的得到新的 节点这时拥有的概节点这时拥有的概节点这时拥有的概节点这时拥有的概率值为率值为率值为率值为0.2,0.1,0.1,0.15,0.15,0.15,0.150.2,0.1,0.1,0.15,0.15,0.15,0.15。第7页/共14页 再将两个最小的概率值相加得到新的节点再将两个最小的概率值相加得到新的节点.直到得到根节点概率为直到得到根节点概率为1.01.0为止。为止。相加时,对于概率值相等的多个节点,可以任意选取。除根节点外,设节点左边相加时,对于概率值相等的多个节点,可以任意选取。除根节点外,设节点左边分支为分支为0 0,右边分支为,右边分支为1 1(也
11、可以反过来)。这样,生成的霍夫曼树如下图所示:(也可以反过来)。这样,生成的霍夫曼树如下图所示:第8页/共14页 对于各值(码值)的代码(码字)就是从根节点出发到底层节点所经历的分支序列。对于各值(码值)的代码(码字)就是从根节点出发到底层节点所经历的分支序列。如如a a4 4的代码(码字)为的代码(码字)为0000,a a6 6的码字为的码字为111.111.通常通常a a4 4和和a a6 6等称为码值,等称为码值,0000和和111111等称为码字。所有码值和码字对应关系如下表所示:等称为码字。所有码值和码字对应关系如下表所示:第9页/共14页(三)霍夫曼表将所有码值和码字的关系整理成一
12、张表,为了整将所有码值和码字的关系整理成一张表,为了整字节输出码字,表中还含有各码字的长度。这种表字节输出码字,表中还含有各码字的长度。这种表就称为霍夫曼表。本例霍夫曼表如表所示就称为霍夫曼表。本例霍夫曼表如表所示:第10页/共14页进行压缩编码时,只要将码值用码字代替即可。所以源符a1 a1 a2 a2 a3 a3 a3 a4 a4 a4 a4 a5 a5 a5 a6 a6 a6 a7 a7 a8编码为:。平均码长B=0.1*3+0.1*3+0.15*3+0.2*2+0.15*3+0.15*3+0.1*4+0.05*42.95(b)熵H 2.9087编码效率N=H/B=2.9087/2.95
13、=98.6%第11页/共14页五、霍夫曼编码的特点 1.1.霍夫曼方法构造出来的码不是唯一的霍夫曼方法构造出来的码不是唯一的 。原因:在给两个分支赋值时,可以是左支(或上支)为 0,也可以是右支(或下支)为 0,造成编码的不唯一。当两个消息的概率 相等时,谁前谁后也是随机的,构造出来的码字就不是唯一的。2.2.霍夫曼编码码字字长参差不齐霍夫曼编码码字字长参差不齐 。3.3.霍夫曼编码对不同的信源的编码效率是不同的。霍夫曼编码对不同的信源的编码效率是不同的。当信源概率相等时当信源概率相等时 ,其编码效率最低。只有在概率分其编码效率最低。只有在概率分布很不均匀时布很不均匀时 ,霍夫曼编码才会收到显著的效果霍夫曼编码才会收到显著的效果 。4.4.解码时解码时 ,必须参照霍夫曼编码表才能正确译码。必须参照霍夫曼编码表才能正确译码。在信源的存储与传输过程中必须首先存储或传输这一霍夫曼编码表,在实际计算压缩效果时,必须考虑霍夫曼编码表占有的比特数。在某些应用场合,信源概率服从于某一分布或存在一定规律(这主要由大量的统计得到),这样就可以在发送端和接收端固定霍夫曼编码表,在传输数据时就省去了传输霍夫曼编码表,这种方法称为霍夫曼编码表缺省使用。第12页/共14页谢谢大家!第13页/共14页感谢您的观看。第14页/共14页
限制150内