哈夫曼編碼講解課件

Huffman樹及其應(yīng)用、最優(yōu)二叉樹(霍夫曼樹)預(yù)備知識(shí):若干術(shù)語(yǔ)路徑:由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成路徑長(zhǎng)度:路徑上的分支數(shù)目a→e的路徑長(zhǎng)度=2樹的路徑長(zhǎng)度:從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。樹長(zhǎng)度0帶權(quán)路徑長(zhǎng)度:結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積樹的帶權(quán)路徑長(zhǎng)度:樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和霍夫曼樹:帶權(quán)路徑長(zhǎng)度最小的樹。Huffman樹及其應(yīng)用1Huffman樹簡(jiǎn)介:WeightedPathLength樹的帶權(quán)路徑長(zhǎng)度如何計(jì)算?mPL=∑啊哈夫曼樹則是:mL最小的樹。經(jīng)典之例:Huffman4d)75WPL=36WPL=46WPL=35Huffman樹簡(jiǎn)介:2構(gòu)造霍夫曼樹的基本思想:權(quán)值大的結(jié)點(diǎn)用短路徑,權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑。構(gòu)造Huffman樹的步驟(即Huffman算法)(1)由給定的n個(gè)權(quán)值{wpm1v23…,wn1},構(gòu)造具有n棵擴(kuò)充二叉樹的森林F={TT1,T23…,Tn1},其中每一棵擴(kuò)充二叉樹T只有一個(gè)帶有權(quán)值v的根結(jié)點(diǎn),其左、右子樹均為空。(2)重復(fù)以下步驟,直到F中僅剩下一棵樹為止:①在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹,做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和②在F中刪去這兩棵二叉樹。③把新的二叉樹加入F。先舉例!構(gòu)造霍夫曼樹的基本思想:3例1:設(shè)有4個(gè)字符d,i,a,n,出現(xiàn)的頻度分別為7,5,2,4,怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快?法1:等長(zhǎng)編碼。例如用二進(jìn)制編碼來(lái)實(shí)現(xiàn)。取d=00,i=01,a=10,n=11法2:不等長(zhǎng)編碼,例如用哈夫曼編碼來(lái)實(shí)現(xiàn)。取d=0;i=10,a=110,n=111最快的編碼是哪個(gè)?是非等長(zhǎng)的Huffman碼!怎樣實(shí)現(xiàn)Huffman編碼?先要構(gòu)造Huffman樹!例1:設(shè)有4個(gè)字符d,i,a,n,出現(xiàn)的頻度分別為7,5,24構(gòu)造Huffman樹的步驟:操作要點(diǎn)1:對(duì)權(quán)值的合并、刪除與替換在權(quán)值集合{7,5,2,4}中,總是合并當(dāng)前值最小的兩個(gè)權(quán)F:{7}5}{2}{4}F:(7}{5}(6}F:{7}{11F:{18}(a)初始(b)合并{2}{4(c)合并{5}{6}(d)合并(7}11注:方框表示外結(jié)點(diǎn)(葉子,字符對(duì)應(yīng)的權(quán)值),圓框表示內(nèi)結(jié)點(diǎn)(合并后的權(quán)值)。構(gòu)造Huffman樹的步驟:5操作要點(diǎn)2:按左0右1對(duì)Huffman樹的所有分支編號(hào)!將Huffman樹與Huffman編碼掛鉤Huffman編碼結(jié)果:d=0,i=10,a=110,n=11lWPL=1bit×7+2bit×5+3bit(2+4)=35特點(diǎn):每一碼都不是另一碼的前綴,絕不會(huì)錯(cuò)譯!稱為前綴碼操作要點(diǎn)2:按左0右1對(duì)Huffman樹的所有分支編號(hào)!6霍夫曼編碼的基本思想是:概率大的字符用短碼,概率小的用「長(zhǎng)碼。由于霍夫曼樹的班最小,說(shuō)明編碼所需要的比特?cái)?shù)最少。這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。例2:假設(shè)用于通信的電文僅由8個(gè)字母{a,b,c,d,e,f,g,h}構(gòu)成,它們?cè)陔娢闹谐霈F(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10},試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。如果用0~7的二進(jìn)制編碼方案又如何?解:先將概率放大100倍,以方便構(gòu)造哈夫曼樹。權(quán)值集合w={7,19,2,6,32,3,21,10}按哈夫曼樹構(gòu)造規(guī)則(合并、刪除、替換),可得到哈夫曼樹?；舴蚵幋a的基本思想是:概率大的字符用短碼,概率小的用7為清晰起見,重新排序?yàn)閃=義,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哈夫曼樹為清晰起見,重新排序?yàn)?對(duì)應(yīng)的哈夫曼編碼(左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二進(jìn)制碼WPL=3(0.19+0.32+0.21+007+0.06+0.10+002+003)=3對(duì)應(yīng)的哈夫曼編碼(左0右1):9另一種結(jié)果表示:1.000400.6000.280.320.210.19○0.170.110.050.100.070.06①哈夫曼編碼樹0.030.02另一種結(jié)果表示: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樹及其應(yīng)用、最優(yōu)二叉樹(霍夫曼樹)預(yù)備知識(shí):若干術(shù)語(yǔ)路徑:由一結(jié)點(diǎn)到另一結(jié)點(diǎn)間的分支所構(gòu)成路徑長(zhǎng)度:路徑上的分支數(shù)目a→e的路徑長(zhǎng)度=2樹的路徑長(zhǎng)度:從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。樹長(zhǎng)度0帶權(quán)路徑長(zhǎng)度:結(jié)點(diǎn)到根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積樹的帶權(quán)路徑長(zhǎng)度:樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和霍夫曼樹:帶權(quán)路徑長(zhǎng)度最小的樹。Huffman樹及其應(yīng)用57Huffman樹簡(jiǎn)介:WeightedPathLength樹的帶權(quán)路徑長(zhǎng)度如何計(jì)算?mPL=∑啊哈夫曼樹則是:mL最小的樹。經(jīng)典之例:Huffman4d)75WPL=36WPL=46WPL=35Huffman樹簡(jiǎn)介:58構(gòu)造霍夫曼樹的基本思想:權(quán)值大的結(jié)點(diǎn)用短路徑,權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑。構(gòu)造Huffman樹的步驟(即Huffman算法)(1)由給定的n個(gè)權(quán)值{wpm1v23…,wn1},構(gòu)造具有n棵擴(kuò)充二叉樹的森林F={TT1,T23…,Tn1},其中每一棵擴(kuò)充二叉樹T只有一個(gè)帶有權(quán)值v的根結(jié)點(diǎn),其左、右子樹均為空。(2)重復(fù)以下步驟,直到F中僅剩下一棵樹為止:①在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹,做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和②在F中刪去這兩棵二叉樹。③把新的二叉樹加入F。先舉例!構(gòu)造霍夫曼樹的基本思想:59例1:設(shè)有4個(gè)字符d,i,a,n,出現(xiàn)的頻度分別為7,5,2,4,怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快?法1:等長(zhǎng)編碼。例如用二進(jìn)制編碼來(lái)實(shí)現(xiàn)。取d=00,i=01,a=10,n=11法2:不等長(zhǎng)編碼,例如用哈夫曼編碼來(lái)實(shí)現(xiàn)。取d=0;i=10,a=110,n=111最快的編碼是哪個(gè)?是非等長(zhǎng)的Huffman碼!怎樣實(shí)現(xiàn)Huffman編碼?先要構(gòu)造Huffman樹!例1:設(shè)有4個(gè)字符d,i,a,n,出現(xiàn)的頻度分別為7,5,260構(gòu)造Huffman樹的步驟:操作要點(diǎn)1:對(duì)權(quán)值的合并、刪除與替換在權(quán)值集合{7,5,2,4}中,總是合并當(dāng)前值最小的兩個(gè)權(quán)F:{7}5}{2}{4}F:(7}{5}(6}F:{7}{11F:{18}(a)初始(b)合并{2}{4(c)合并{5}{6}(d)合并(7}11注:方框表示外結(jié)點(diǎn)(葉子,字符對(duì)應(yīng)的權(quán)值),圓框表示內(nèi)結(jié)點(diǎn)(合并后的權(quán)值)。構(gòu)造Huffman樹的步驟:61操作要點(diǎn)2:按左0右1對(duì)Huffman樹的所有分支編號(hào)!將Huffman樹與Huffman編碼掛鉤Huffman編碼結(jié)果:d=0,i=10,a=110,n=11lWPL=1bit×7+2bit×5+3bit(2+4)=35特點(diǎn):每一碼都不是另一碼的前綴,絕不會(huì)錯(cuò)譯!稱為前綴碼操作要點(diǎn)2:按左0右1對(duì)Huffman樹的所有分支編號(hào)!62霍夫曼編碼的基本思想是:概率大的字符用短碼,概率小的用「長(zhǎng)碼。由于霍夫曼樹的班最小,說(shuō)明編碼所需要的比特?cái)?shù)最少。這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。例2:假設(shè)用于通信的電文僅由8個(gè)字母{a,b,c,d,e,f,g,h}構(gòu)成,它們?cè)陔娢闹谐霈F(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10},試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。如果用0~7的二進(jìn)制編碼方案又如何?解:先將概率放大100倍,以方便構(gòu)造哈夫曼樹。權(quán)值集合w={7,19,2,6,32,3,21,10}按哈夫曼樹構(gòu)造規(guī)則(合并、刪除、替換),可得到哈夫曼樹。霍夫曼編碼的基本思想是:概率大的字符用短碼,概率小的用63為清晰起見,重新排序?yàn)閃=義,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哈夫曼樹為清晰起見,重新排序?yàn)?4對(duì)應(yīng)的哈夫曼編碼(左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二進(jìn)制碼WPL=3(0.19+0.32+0.21+007+0.06+0.10+002+003)=3對(duì)應(yīng)的哈夫曼編碼(左0右1):65另一種結(jié)果表示:1.000400.6000.280.320.210.19○0.170.110.050.100.070.06①哈夫曼編碼樹0.030.02另一種結(jié)果表示: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哈