資源描述:
《哈夫曼樹和哈夫曼編碼》由會員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、哈夫曼樹和哈夫曼編碼本節(jié)初賽復(fù)賽都會考。初學(xué)數(shù)據(jù)結(jié)構(gòu)的讀者可以在本節(jié)領(lǐng)略到數(shù)據(jù)結(jié)構(gòu)的奧妙。在學(xué)習(xí)本節(jié)內(nèi)容之前,我們先跳過概念學(xué)習(xí)怎樣構(gòu)造一棵哈夫曼樹。一、如何構(gòu)造一棵哈夫曼樹?(哈夫曼樹也是一棵二叉樹)給n個點(diǎn),每個點(diǎn)都有權(quán)值,構(gòu)造一棵哈夫曼樹。每次選剩下的兩棵根權(quán)值最小的樹合并成一棵新樹,新樹的根權(quán)值等于兩棵合并前樹的根權(quán)值和。(一開始一個點(diǎn)也看成一棵樹,只不過這棵樹沒有孩子節(jié)點(diǎn))例1:4個點(diǎn),a、b、c、d,權(quán)值分別為7、5、2、4。構(gòu)樹過程:因?yàn)?個點(diǎn),所以合并3次(n個點(diǎn),合并n-1次)第一步:選根權(quán)值最小的兩棵樹2(c)和4(d)合并,新樹的根節(jié)點(diǎn)為6,
2、如圖(b);第二步:選根權(quán)值最小的兩棵樹5(b)和6合并,新樹的根節(jié)點(diǎn)為11,如圖(c);第二步:選根權(quán)值最小的兩棵樹7(a)和11合并,新樹的根節(jié)點(diǎn)為18,如圖(c);例2:6個點(diǎn),a、b、c、d、e、f,權(quán)值分別為0.4、0.3、0.1、0.1、0.02、0.08。構(gòu)圖過程同例1。(如下圖)二、基本概念樹的路徑長度PL:從樹根到樹的每個節(jié)點(diǎn)的路徑長度(每條邊長度為1)之和(完全二叉樹為這種路徑長度最短的二叉樹)。樹的帶權(quán)路徑長度WPL:樹的所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度(該節(jié)點(diǎn)到根節(jié)點(diǎn)路徑長度與節(jié)點(diǎn)上權(quán)的乘積)之和。透徹理解樹的路徑長度和樹的帶權(quán)路徑長度這兩個概念
3、非常重要。哈夫曼樹:帶權(quán)路徑長度WPL最短的二叉樹(最優(yōu)二叉樹)構(gòu)造這種樹的算法最早是由哈夫曼(Huffman)1952年提出,這種樹在信息檢索中很有用。???????????????????????????????例如例1,構(gòu)造哈夫曼樹的WPL為35是最小的。具體比較如下圖:三、哈夫曼編碼一篇電文,原文為:AMCADEDDMCCAD?,F(xiàn)在要把原文轉(zhuǎn)換成01串發(fā)送給對方。為了節(jié)省資源,我們當(dāng)然希望翻譯好的01串長度盡量的短。怎么辦?研究發(fā)現(xiàn):1、只有5個字母E,M,C,A,D;2、這5個字母的使用頻度分別為{E,M,C,A,D}={1,2,3,3,4}。用頻度為權(quán)
4、值生成哈夫曼樹,并在葉子上標(biāo)注對應(yīng)的字母,在樹枝上標(biāo)注分配碼“0”或“1”(注:分配碼不是邊的長度,而是區(qū)分左右孩子代表方向):哈夫曼編碼原則:n個節(jié)點(diǎn)的哈夫曼樹含有2n-1個節(jié)點(diǎn),沒有度為1的節(jié)點(diǎn)編碼從葉子節(jié)點(diǎn)到根節(jié)點(diǎn),譯碼從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)。從哈夫曼樹根節(jié)點(diǎn)開始,對左子樹分配碼“0”,右子樹分配碼“1”,一直到達(dá)葉子節(jié)點(diǎn)為止,然后將從樹根沿每條路徑到達(dá)葉子結(jié)點(diǎn)的代碼排列起來,便得到了哈夫曼編碼。各字母的編碼即為哈夫曼編碼:EMCAD所有編碼長度和為12位,即PL=12,此時的PL并不是最小的,但此時的WPL一定是最小的。WPL最小才能使得密報翻譯的01串長度最
5、短。例3:對原電文進(jìn)行哈夫曼編碼,如上圖,則哈夫曼編碼的WPL=1*3+2*3+3*2+3*2+4*2=29。例4:對原電文進(jìn)行等長編碼,則:等長編碼的WPL=1*3+2*3+3*3+3*3+4*3=39所以哈夫曼編碼可以節(jié)省空間。??原電文AMCADEDDMCCAD翻譯成01串后為:10001011011000111100101011011。對方根據(jù)事先構(gòu)造好的哈夫曼樹編碼表可以還原原電文。問題:為什么根據(jù)哈夫曼編碼可以還原原電文而沒有出現(xiàn)某一串01串可以翻譯成兩個字母串呢?原因:在編碼中任何一字符的編碼不是另一字符編碼的前綴。這點(diǎn)很重要,也需要讀者花時間理解。
6、練習(xí)1、6個點(diǎn)a、b、c、d、e、f,權(quán)值分別為0.5、0.6、0.15、0.1、0.05、0.09,求PL=(),WPL=()。2、文章中只出現(xiàn)五個字母ABCDE,出現(xiàn)頻率={6,2,1,2,5},求PL=(),WPL=(),其中各個字母的哈夫曼編碼為A(),B(),C(),D(),E()。3、下面哈夫曼編碼組合哪一組不是合法的前綴編碼()A.(00,1,10,11)B.(01,10,00,11)C.(0,10,110,111)D.(1,01,000,001)歷年題目2009提高7、最優(yōu)前綴編碼,也稱Huffman編碼。這種編碼組合的特點(diǎn)是對于較頻繁使用的元素給
7、與較短的唯一編碼,以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼()A.(00,01,10,11)B.(0,1,00,11)C.(0,10,110,111)D.(1,01,000,001)答案:2009提高:7B