哈夫曼樹(shù)和哈夫曼編碼

《哈夫曼樹(shù)和哈夫曼編碼》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、哈夫曼樹(shù)和哈夫曼編碼本節(jié)初賽復(fù)賽都會(huì)考。初學(xué)數(shù)據(jù)結(jié)構(gòu)的讀者可以在本節(jié)領(lǐng)略到數(shù)據(jù)結(jié)構(gòu)的奧妙。在學(xué)習(xí)本節(jié)內(nèi)容之前，我們先跳過(guò)概念學(xué)習(xí)怎樣構(gòu)造一棵哈夫曼樹(shù)。一、如何構(gòu)造一棵哈夫曼樹(shù)？（哈夫曼樹(shù)也是一棵二叉樹(shù)）給n個(gè)點(diǎn)，每個(gè)點(diǎn)都有權(quán)值，構(gòu)造一棵哈夫曼樹(shù)。每次選剩下的兩棵根權(quán)值最小的樹(shù)合并成一棵新樹(shù)，新樹(shù)的根權(quán)值等于兩棵合并前樹(shù)的根權(quán)值和。（一開(kāi)始一個(gè)點(diǎn)也看成一棵樹(shù)，只不過(guò)這棵樹(shù)沒(méi)有孩子節(jié)點(diǎn)）例1：4個(gè)點(diǎn)，a、b、c、d，權(quán)值分別為7、5、2、4。構(gòu)樹(shù)過(guò)程：因?yàn)?個(gè)點(diǎn)，所以合并3次（n個(gè)點(diǎn)，合并n-1次）第一步：選根權(quán)值最小的兩棵樹(shù)2（c）和4（d）合并，新樹(shù)的根節(jié)點(diǎn)為6，

2、如圖(b)；第二步：選根權(quán)值最小的兩棵樹(shù)5（b）和6合并，新樹(shù)的根節(jié)點(diǎn)為11，如圖(c)；第二步：選根權(quán)值最小的兩棵樹(shù)7（a）和11合并，新樹(shù)的根節(jié)點(diǎn)為18，如圖(c)；例2：6個(gè)點(diǎn)，a、b、c、d、e、f，權(quán)值分別為0.4、0.3、0.1、0.1、0.02、0.08。構(gòu)圖過(guò)程同例1。（如下圖）二、基本概念樹(shù)的路徑長(zhǎng)度PL：從樹(shù)根到樹(shù)的每個(gè)節(jié)點(diǎn)的路徑長(zhǎng)度（每條邊長(zhǎng)度為1）之和（完全二叉樹(shù)為這種路徑長(zhǎng)度最短的二叉樹(shù)）。樹(shù)的帶權(quán)路徑長(zhǎng)度WPL：樹(shù)的所有葉子節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度（該節(jié)點(diǎn)到根節(jié)點(diǎn)路徑長(zhǎng)度與節(jié)點(diǎn)上權(quán)的乘積）之和。透徹理解樹(shù)的路徑長(zhǎng)度和樹(shù)的帶權(quán)路徑長(zhǎng)度這兩個(gè)概念

3、非常重要。哈夫曼樹(shù)：帶權(quán)路徑長(zhǎng)度WPL最短的二叉樹(shù)（最優(yōu)二叉樹(shù)）構(gòu)造這種樹(shù)的算法最早是由哈夫曼(Huffman)1952年提出，這種樹(shù)在信息檢索中很有用。???????????????????????????????例如例1，構(gòu)造哈夫曼樹(shù)的WPL為35是最小的。具體比較如下圖：三、哈夫曼編碼一篇電文，原文為：AMCADEDDMCCAD?，F(xiàn)在要把原文轉(zhuǎn)換成01串發(fā)送給對(duì)方。為了節(jié)省資源，我們當(dāng)然希望翻譯好的01串長(zhǎng)度盡量的短。怎么辦？研究發(fā)現(xiàn)：1、只有5個(gè)字母E,M,C,A,D；2、這5個(gè)字母的使用頻度分別為｛E,M,C,A,D｝=｛1,2,3,3,4｝。用頻度為權(quán)

4、值生成哈夫曼樹(shù)，并在葉子上標(biāo)注對(duì)應(yīng)的字母，在樹(shù)枝上標(biāo)注分配碼“0”或“1”（注：分配碼不是邊的長(zhǎng)度，而是區(qū)分左右孩子代表方向）:哈夫曼編碼原則：n個(gè)節(jié)點(diǎn)的哈夫曼樹(shù)含有2n-1個(gè)節(jié)點(diǎn)，沒(méi)有度為1的節(jié)點(diǎn)編碼從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)，譯碼從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)。從哈夫曼樹(shù)根節(jié)點(diǎn)開(kāi)始，對(duì)左子樹(shù)分配碼“0”，右子樹(shù)分配碼“1”，一直到達(dá)葉子節(jié)點(diǎn)為止，然后將從樹(shù)根沿每條路徑到達(dá)葉子結(jié)點(diǎn)的代碼排列起來(lái)，便得到了哈夫曼編碼。各字母的編碼即為哈夫曼編碼：EMCAD所有編碼長(zhǎng)度和為12位，即PL=12，此時(shí)的PL并不是最小的，但此時(shí)的WPL一定是最小的。WPL最小才能使得密報(bào)翻譯的01串長(zhǎng)度最

5、短。例3：對(duì)原電文進(jìn)行哈夫曼編碼，如上圖，則哈夫曼編碼的WPL=1*3+2*3+3*2+3*2+4*2=29。例4：對(duì)原電文進(jìn)行等長(zhǎng)編碼，則：等長(zhǎng)編碼的WPL=1*3+2*3+3*3+3*3+4*3=39所以哈夫曼編碼可以節(jié)省空間。??原電文AMCADEDDMCCAD翻譯成01串后為：10001011011000111100101011011。對(duì)方根據(jù)事先構(gòu)造好的哈夫曼樹(shù)編碼表可以還原原電文。問(wèn)題：為什么根據(jù)哈夫曼編碼可以還原原電文而沒(méi)有出現(xiàn)某一串01串可以翻譯成兩個(gè)字母串呢？原因：在編碼中任何一字符的編碼不是另一字符編碼的前綴。這點(diǎn)很重要，也需要讀者花時(shí)間理解。

6、練習(xí)1、6個(gè)點(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)五個(gè)字母ABCDE，出現(xiàn)頻率=｛6,2,1,2,5｝，求PL=()，WPL=()，其中各個(gè)字母的哈夫曼編碼為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)前綴編碼，也稱(chēng)Huffman編碼。這種編碼組合的特點(diǎn)是對(duì)于較頻繁使用的元素給

7、與較短的唯一編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼（）A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）答案：2009提高：7B