哈夫曼编码讲解课件

Huffman树及其应用、最优二叉树(霍夫曼树)预备知识:若干术语路径:由一结点到另一结点间的分支所构成路径长度:路径上的分支数目a→e的路径长度=2树的路径长度:从树根到每一结点的路径长度之和。树长度0带权路径长度:结点到根的路径长度与结点上权的乘积树的带权路径长度:树中所有叶子结点的带权路径长度之和霍夫曼树:带权路径长度最小的树。Huffman树及其应用1Huffman树简介:WeightedPathLength树的带权路径长度如何计算?mPL=∑啊哈夫曼树则是:mL最小的树。经典之例:Huffman4d)75WPL=36WPL=46WPL=35Huffman树简介:2构造霍夫曼树的基本思想:权值大的结点用短路径,权值小的结点用长路径。构造Huffman树的步骤(即Huffman算法)(1)由给定的n个权值{wpm1v23…,wn1},构造具有n棵扩充二叉树的森林F={TT1,T23…,Tn1},其中每一棵扩充二叉树T只有一个带有权值v的根结点,其左、右子树均为空。(2)重复以下步骤,直到F中仅剩下一棵树为止:①在F中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和②在F中删去这两棵二叉树。③把新的二叉树加入F。先举例!构造霍夫曼树的基本思想:3例1:设有4个字符d,i,a,n,出现的频度分别为7,5,2,4,怎样编码才能使它们组成的报文在网络中传得最快?法1:等长编码。例如用二进制编码来实现。取d=00,i=01,a=10,n=11法2:不等长编码,例如用哈夫曼编码来实现。取d=0;i=10,a=110,n=111最快的编码是哪个?是非等长的Huffman码!怎样实现Huffman编码?先要构造Huffman树!例1:设有4个字符d,i,a,n,出现的频度分别为7,5,24构造Huffman树的步骤:操作要点1:对权值的合并、删除与替换在权值集合{7,5,2,4}中,总是合并当前值最小的两个权F:{7}5}{2}{4}F:(7}{5}(6}F:{7}{11F:{18}(a)初始(b)合并{2}{4(c)合并{5}{6}(d)合并(7}11注:方框表示外结点(叶子,字符对应的权值),圆框表示内结点(合并后的权值)。构造Huffman树的步骤:5操作要点2:按左0右1对Huffman树的所有分支编号!将Huffman树与Huffman编码挂钩Huffman编码结果:d=0,i=10,a=110,n=11lWPL=1bit×7+2bit×5+3bit(2+4)=35特点:每一码都不是另一码的前缀,绝不会错译!称为前缀码操作要点2:按左0右1对Huffman树的所有分支编号!6霍夫曼编码的基本思想是:概率大的字符用短码,概率小的用「长码。由于霍夫曼树的班最小,说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。例2:假设用于通信的电文仅由8个字母{a,b,c,d,e,f,g,h}构成,它们在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10},试为这8个字母设计哈夫曼编码。如果用0~7的二进制编码方案又如何?解:先将概率放大100倍,以方便构造哈夫曼树。权值集合w={7,19,2,6,32,3,21,10}按哈夫曼树构造规则(合并、删除、替换),可得到哈夫曼树。霍夫曼编码的基本思想是:概率大的字符用短码,概率小的用7为清晰起见,重新排序为W=义,6,7,10,19,21,32}W1=8,6,7,10,19,21,32}w2=x1,11,19,21,32}W3={×,ⅸ,19,21,32}W4={,,28,32}w5={28,82,40}W6={40,0o}W7={100哈夫曼树为清晰起见,重新排序为8对应的哈夫曼编码(左0右1):符编码频率符「编码」频率1100007a000|007000190010.1911100.02c010002d11100.06d0110.06100.32100|0.32111110031010.03g011021g11002111010101110.10Huffman码的wPL=2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.031.44+0.92+0.25=2.61二进制码WPL=3(0.19+0.32+0.21+007+0.06+0.10+002+003)=3对应的哈夫曼编码(左0右1):9另一种结果表示:1.000400.6000.280.320.210.19○0.170.110.050.100.070.06①哈夫曼编码树0.030.02另一种结果表示:10哈夫曼编码讲解课件11哈夫曼编码讲解课件12哈夫曼编码讲解课件13哈夫曼编码讲解课件14哈夫曼编码讲解课件15哈夫曼编码讲解课件16哈夫曼编码讲解课件17哈夫曼编码讲解课件18哈夫曼编码讲解课件19哈夫曼编码讲解课件20哈夫曼编码讲解课件21哈夫曼编码讲解课件22哈夫曼编码讲解课件23哈夫曼编码讲解课件24哈夫曼编码讲解课件25哈夫曼编码讲解课件26哈夫曼编码讲解课件27哈夫曼编码讲解课件28哈夫曼编码讲解课件29哈夫曼编码讲解课件30哈夫曼编码讲解课件31哈夫曼编码讲解课件32哈夫曼编码讲解课件33哈夫曼编码讲解课件34哈夫曼编码讲解课件35哈夫曼编码讲解课件36哈夫曼编码讲解课件37哈夫曼编码讲解课件38哈夫曼编码讲解课件39哈夫曼编码讲解课件40哈夫曼编码讲解课件41哈夫曼编码讲解课件42哈夫曼编码讲解课件43哈夫曼编码讲解课件44哈夫曼编码讲解课件45哈夫曼编码讲解课件46哈夫曼编码讲解课件47哈夫曼编码讲解课件48哈夫曼编码讲解课件49哈夫曼编码讲解课件50哈夫曼编码讲解课件51哈夫曼编码讲解课件52哈夫曼编码讲解课件53哈夫曼编码讲解课件54哈夫曼编码讲解课件55哈夫曼编码讲解课件56Huffman树及其应用、最优二叉树(霍夫曼树)预备知识:若干术语路径:由一结点到另一结点间的分支所构成路径长度:路径上的分支数目a→e的路径长度=2树的路径长度:从树根到每一结点的路径长度之和。树长度0带权路径长度:结点到根的路径长度与结点上权的乘积树的带权路径长度:树中所有叶子结点的带权路径长度之和霍夫曼树:带权路径长度最小的树。Huffman树及其应用57Huffman树简介:WeightedPathLength树的带权路径长度如何计算?mPL=∑啊哈夫曼树则是:mL最小的树。经典之例:Huffman4d)75WPL=36WPL=46WPL=35Huffman树简介:58构造霍夫曼树的基本思想:权值大的结点用短路径,权值小的结点用长路径。构造Huffman树的步骤(即Huffman算法)(1)由给定的n个权值{wpm1v23…,wn1},构造具有n棵扩充二叉树的森林F={TT1,T23…,Tn1},其中每一棵扩充二叉树T只有一个带有权值v的根结点,其左、右子树均为空。(2)重复以下步骤,直到F中仅剩下一棵树为止:①在F中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和②在F中删去这两棵二叉树。③把新的二叉树加入F。先举例!构造霍夫曼树的基本思想:59例1:设有4个字符d,i,a,n,出现的频度分别为7,5,2,4,怎样编码才能使它们组成的报文在网络中传得最快?法1:等长编码。例如用二进制编码来实现。取d=00,i=01,a=10,n=11法2:不等长编码,例如用哈夫曼编码来实现。取d=0;i=10,a=110,n=111最快的编码是哪个?是非等长的Huffman码!怎样实现Huffman编码?先要构造Huffman树!例1:设有4个字符d,i,a,n,出现的频度分别为7,5,260构造Huffman树的步骤:操作要点1:对权值的合并、删除与替换在权值集合{7,5,2,4}中,总是合并当前值最小的两个权F:{7}5}{2}{4}F:(7}{5}(6}F:{7}{11F:{18}(a)初始(b)合并{2}{4(c)合并{5}{6}(d)合并(7}11注:方框表示外结点(叶子,字符对应的权值),圆框表示内结点(合并后的权值)。构造Huffman树的步骤:61操作要点2:按左0右1对Huffman树的所有分支编号!将Huffman树与Huffman编码挂钩Huffman编码结果:d=0,i=10,a=110,n=11lWPL=1bit×7+2bit×5+3bit(2+4)=35特点:每一码都不是另一码的前缀,绝不会错译!称为前缀码操作要点2:按左0右1对Huffman树的所有分支编号!62霍夫曼编码的基本思想是:概率大的字符用短码,概率小的用「长码。由于霍夫曼树的班最小,说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。例2:假设用于通信的电文仅由8个字母{a,b,c,d,e,f,g,h}构成,它们在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10},试为这8个字母设计哈夫曼编码。如果用0~7的二进制编码方案又如何?解:先将概率放大100倍,以方便构造哈夫曼树。权值集合w={7,19,2,6,32,3,21,10}按哈夫曼树构造规则(合并、删除、替换),可得到哈夫曼树。霍夫曼编码的基本思想是:概率大的字符用短码,概率小的用63为清晰起见,重新排序为W=义,6,7,10,19,21,32}W1=8,6,7,10,19,21,32}w2=x1,11,19,21,32}W3={×,ⅸ,19,21,32}W4={,,28,32}w5={28,82,40}W6={40,0o}W7={100哈夫曼树为清晰起见,重新排序为64对应的哈夫曼编码(左0右1):符编码频率符「编码」频率1100007a000|007000190010.1911100.02c010002d11100.06d0110.06100.32100|0.32111110031010.03g011021g11002111010101110.10Huffman码的wPL=2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.031.44+0.92+0.25=2.61二进制码WPL=3(0.19+0.32+0.21+007+0.06+0.10+002+003)=3对应的哈夫曼编码(左0右1):65另一种结果表示:1.000400.6000.280.320.210.19○0.170.110.050.100.070.06①哈夫曼编码树0.030.02另一种结果表示:66哈夫曼编码讲解课件67哈夫曼编码讲解课件68哈夫曼编码讲解课件69哈夫曼编码讲解课件70哈夫曼编码讲解课件71哈夫曼编码讲解课件72哈夫曼编码讲解课件73哈夫曼编码讲解课件74哈夫曼编码讲解课件75哈夫曼编码讲解课件76哈夫曼编码讲解课件77哈夫曼编码讲解课件78哈夫曼编码讲解课件79哈夫曼编码讲解课件80哈夫曼编码讲解课件81哈夫曼编码讲解课件82哈夫曼编码讲解课件83哈夫曼编码讲解课件84哈夫曼编码讲解课件85哈夫曼编码讲解课件86哈夫曼编码讲解课件87哈夫曼编码讲解课件88哈夫曼编码讲解课件89哈夫曼编码讲解课件90哈夫曼编码讲解课件91哈夫曼编码讲解课件92哈