哈夫曼編碼課程設(shè)計(jì)

1、<p><b>　　摘要</b></p><p>　　哈夫曼編碼是廣泛用于數(shù)據(jù)文件壓縮的十分有效的編碼方法，其在電子計(jì)算機(jī)、電視、遙控和通訊等方面廣泛使用。其壓縮通常在20%~90%之間。哈夫曼編碼算法使用字符在文件中出現(xiàn)的頻率表來建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。</p><p>　　哈夫曼算法構(gòu)造的擴(kuò)充二叉樹稱為哈夫曼編碼樹或哈夫曼樹。當(dāng)然，還

2、有編碼和譯碼部分。本系統(tǒng)的前端開發(fā)工具是MATLAB 7.0 。用預(yù)先規(guī)定的方法將文字、數(shù)字或其他對(duì)象編成數(shù)碼，或?qū)⑿畔?、?shù)據(jù)轉(zhuǎn)換成規(guī)定的電脈沖信號(hào),通過本次實(shí)驗(yàn),了解編碼的具體過程,通過編程實(shí)現(xiàn)編碼,利用matlab實(shí)現(xiàn)哈弗曼編碼。具有輸入字符集大小及權(quán)值大小，構(gòu)造哈夫曼樹，并對(duì)用戶輸入的字符串進(jìn)行編碼以及譯碼兩種功能。本程序經(jīng)過測試后，功能均能實(shí)現(xiàn)，運(yùn)行穩(wěn)定。</p><p>　　關(guān)鍵詞：哈夫曼樹，編碼，譯碼

3、，權(quán)值</p><p><b>　　目 錄</b></p><p><b>　　1 問題描述1</b></p><p><b>　　2 問題分析2</b></p><p><b>　　3 算法設(shè)計(jì)3</b></p><p>

4、<b>　　4 算法實(shí)現(xiàn)4</b></p><p><b>　　5測試分析7</b></p><p><b>　　結(jié) 論9</b></p><p><b>　　參考文獻(xiàn)10</b></p><p><b>　　1 問題描述</b&

5、gt;</p><p>　　哈夫曼在上世紀(jì)五十年代初就提出這種編碼時(shí)，根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的編碼。它是一種變長的編碼。哈夫曼編碼應(yīng)用廣泛，如JPEG中就應(yīng)用了哈夫曼編碼。在編碼中，若各碼字長度嚴(yán)格按照碼字所對(duì)應(yīng)符號(hào)出現(xiàn)概率的大小的逆序排列，則編碼的平均長度是最小的。構(gòu)造好哈夫曼樹后，就可根據(jù)哈夫曼樹進(jìn)行編碼。然而怎樣構(gòu)造一棵哈夫曼樹呢？最具有一般規(guī)律的構(gòu)造方法就是哈夫曼算法。字符根據(jù)其出現(xiàn)的概率作

6、為權(quán)值構(gòu)造一棵哈夫曼樹后，經(jīng)哈夫曼編碼得到的對(duì)應(yīng)的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字符。顯然哈夫曼編碼是前綴編碼，即任一個(gè)字符的編碼都不是另一個(gè)字符的編碼的前綴，否則，編碼就不能進(jìn)行翻譯。</p><p>　　利用哈夫曼算法的編碼和譯碼功能，重復(fù)地顯示并處理以下項(xiàng)目，即構(gòu)造哈夫曼樹，實(shí)現(xiàn)編碼及譯碼幾項(xiàng)功能。本次設(shè)計(jì)就是為這樣的一個(gè)哈夫曼的編、譯碼器。</p><p>

7、　　哈夫曼編碼所以能產(chǎn)生較短的碼文，是因?yàn)楣蚵鼧渚哂凶钚〖訖?quán)路徑長度的二叉樹。如果葉結(jié)點(diǎn)的權(quán)值恰好是某個(gè)需編碼的文本中各字符出現(xiàn)的次數(shù)，則編碼后文本的長度就是該哈夫曼樹的加權(quán)路徑長度。譯碼過程為自做向右逐一掃描碼文，并從哈夫曼樹的根開始，將掃到的二進(jìn)制位串中的相鄰位與哈夫曼樹上標(biāo)的0，1相匹配，以確定一條從根到葉子結(jié)點(diǎn)的路徑，一旦到達(dá)葉子，則譯出了一個(gè)字符。再回到樹根，從二進(jìn)位串的下一位開始繼續(xù)譯碼。軟件運(yùn)行環(huán)境及開發(fā)工具是MATLA

8、B 7.0。</p><p><b>　　2 問題分析</b></p><p>　　為了建立哈夫曼樹以及實(shí)現(xiàn)哈夫曼編碼以及譯碼，因此我們選擇了結(jié)點(diǎn)結(jié)構(gòu)體，利用這一結(jié)構(gòu)體，我們定義了一個(gè)結(jié)構(gòu)體數(shù)組和一個(gè)樹根指針，數(shù)組用來紀(jì)錄輸入數(shù)據(jù)的多少，樹根指針用來連接哈夫曼樹。從程序中可以看到使用哈夫曼算法構(gòu)造哈夫曼樹過程，是從n棵知識(shí)一個(gè)根結(jié)點(diǎn)的樹組成的森林開始的。在算法執(zhí)行中，

9、哈夫曼樹是由若干棵樹組成的森林，通過不斷地合作樹，最后得到一棵哈夫曼樹。為了便于實(shí)現(xiàn)哈夫曼樹的建樹運(yùn)算，定義程序的哈夫曼樹類HfmTree，它包括如下兩個(gè)私有數(shù)據(jù)成員tree和weight：其中，tree是一個(gè)二叉樹BinaryTree類型對(duì)象，是一棵哈夫曼樹，weight是tree所代表的哈夫曼樹的權(quán)值。</p><p>　　在本課程設(shè)計(jì)中構(gòu)造哈弗曼編碼。構(gòu)造哈夫曼樹算法：（1）用給定的一組權(quán)值{W1,W2,…

10、,Wn},生成一個(gè)有n棵樹組成的森林F={T1,T2,…Tn},其中每棵二叉樹Ti只有一個(gè)結(jié)點(diǎn)，即權(quán)值為 Wi的根結(jié)點(diǎn)（也是葉子結(jié)點(diǎn)）；（2）從F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的樹，作為新樹根的左右子樹，新樹根的權(quán)值是左右子樹根結(jié)點(diǎn)的權(quán)值之和；（3）從F中刪除這兩棵樹，另將新二叉樹加入F中；（4）重復(fù)（2）和（3），直到F中只包含一棵樹為止。</p><p>　　本次程序設(shè)計(jì)的是哈夫曼編碼及譯碼。由建立好的哈夫曼樹來進(jìn)

11、行編碼，從根結(jié)點(diǎn)開始，左走一步為‘0’，右走一步為‘1’，并將編碼結(jié)果存入文件中，譯碼過程為從文件中逐一掃描碼文，并從哈夫曼樹的根開始，將掃到的二進(jìn)制位串中的相鄰位與哈夫曼樹上標(biāo)的0，1相匹配，以確定一條從根到葉子結(jié)點(diǎn)的路徑，一旦到達(dá)葉子，則譯出了一個(gè)字符。再回到樹根從二進(jìn)位串的下一位開始繼續(xù)譯碼。 </p><p><b>　　3 算法設(shè)計(jì)</b></p><p>

12、　　Huffman編碼是一種可變長編碼方式，是由美國數(shù)學(xué)家David Huffman創(chuàng)立的，是二叉樹的一種特殊轉(zhuǎn)化形式。編碼的原理是：將使用次數(shù)多的代碼轉(zhuǎn)換成長度較短的代碼，而使用次數(shù)少的可以使用較長的編碼，并且保持編碼的唯一可解性。Huffman算法的最根本的原則是：累計(jì)的(字符的統(tǒng)計(jì)數(shù)字*字符的編碼長度)為最小，也就是權(quán)值(字符的統(tǒng)計(jì)數(shù)字*字符的編碼長度)的和最小。</p><p>　　Huffman樹是二叉

13、樹的一種特殊轉(zhuǎn)化形式。以下是構(gòu)件Huffman樹的例子：比如有以下數(shù)據(jù)， ABFACGCAHGBBAACECDFGFAAEABBB先進(jìn)行統(tǒng)計(jì)A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1) 括號(hào)里面的是統(tǒng)計(jì)次數(shù)。</p><p>　　生成Huffman樹：每次取最小的那兩個(gè)節(jié)點(diǎn)(node)合并成一個(gè)節(jié)點(diǎn)(node)，并且將累計(jì)數(shù)值相加作為新的接點(diǎn)的累計(jì)數(shù)值，最頂層的是根節(jié)點(diǎn)(roo

14、t) 注：列表中最小節(jié)點(diǎn)的是指包括合并了的節(jié)點(diǎn)在內(nèi)的所有節(jié)點(diǎn)，已經(jīng)合并的節(jié)點(diǎn)不在列表。4 算法實(shí)現(xiàn)</p><p>　　%哈夫曼編碼的MATLAB實(shí)現(xiàn)（基于0、1編碼）：</p><p><b>　　clc;</b></p><p><b>　　clear;</b></p><p>　　A=[0.

15、3,0.2,0.1,0.2,0.2];%信源消息的概率序列</p><p>　　A=fliplr(sort(A));%按降序排列</p><p><b>　　T=A;</b></p><p>　　[m,n]=size(A);</p><p>　　B=zeros(n,n-1);%空的編碼表（矩陣）</p>&

16、lt;p><b>　　for i=1:n</b></p><p>　　B(i,1)=T(i);%生成編碼表的第一列</p><p><b>　　end</b></p><p>　　r=B(i,1)+B(i-1,1);%最后兩個(gè)元素相加</p><p><b>　　T(n-1)=r;&

17、lt;/b></p><p><b>　　T(n)=0;</b></p><p>　　T=fliplr(sort(T));</p><p><b>　　t=n-1;</b></p><p>　　for j=2:n-1%生成編碼表的其他各列</p><p><b&g

18、t;　　for i=1:t</b></p><p>　　B(i,j)=T(i);</p><p><b>　　end</b></p><p>　　K=find(T==r);</p><p>　　B(n,j)=K(end);%從第二列開始，每列的最后一個(gè)元素記錄特征元素在</p><p>

19、;<b>　　%該列的位置</b></p><p>　　r=(B(t-1,j)+B(t,j));%最后兩個(gè)元素相加</p><p><b>　　T(t-1)=r;</b></p><p><b>　　T(t)=0;</b></p><p>　　T=fliplr(sort(T))

20、; </p><p><b>　　t=t-1;</b></p><p><b>　　end</b></p><p><b>　　B;%輸出編碼表</b></p><p>　　END1=sym('[0,1]');%給最后一列的元素編碼</p><

21、;p><b>　　END=END1;</b></p><p><b>　　t=3;</b></p><p><b>　　d=1;</b></p><p>　　for j=n-2:-1:1%從倒數(shù)第二列開始依次對(duì)各列元素編碼</p><p>　　for i=1:t-2<

22、;/p><p>　　if i>1 & B(i,j)==B(i-1,j)</p><p><b>　　d=d+1;</b></p><p><b>　　else</b></p><p><b>　　d=1;</b></p><p><b&g

23、t;　　end</b></p><p>　　B(B(n,j+1),j+1)=-1;</p><p>　　temp=B(:,j+1);</p><p>　　x=find(temp==B(i,j));</p><p>　　END(i)=END1(x(d));</p><p><b>　　end<

24、/b></p><p>　　y=B(n,j+1);</p><p>　　END(t-1)=[char(END1(y)),'0'];</p><p>　　END(t)=[char(END1(y)),'1'];</p><p><b>　　t=t+1;</b></p>&l

25、t;p><b>　　END1=END;</b></p><p><b>　　end</b></p><p>　　A%排序后的原概率序列</p><p><b>　　END%編碼結(jié)果</b></p><p><b>　　for i=1:n</b><

26、;/p><p>　　[a,b]=size(char(END(i)));</p><p><b>　　L(i)=b;</b></p><p><b>　　end</b></p><p>　　avlen=sum(L.*A)%平均碼長 </p><p>　　H1=log2(A);&l

27、t;/p><p>　　H=-A*(H1')%熵</p><p>　　P=H/avlen%編碼效率</p><p><b>　　5 測試分析</b></p><p><b>　　（1）哈夫曼編碼</b></p><p>　　對(duì)字符串進(jìn)行編碼運(yùn)行結(jié)果如圖5.2所示。</

28、p><p>　　圖1 哈夫曼編碼結(jié)果</p><p><b>　?。?）哈夫曼譯碼</b></p><p>　　另外就是在譯碼時(shí)沒能實(shí)用二進(jìn)制流文件對(duì)相關(guān)知識(shí)沒能融會(huì)貫通，</p><p>　　圖5.3哈夫曼譯碼結(jié)果</p><p><b>　　結(jié) 論</b></p>

29、;<p>　　通過這次課程設(shè)計(jì)，讓我對(duì)一個(gè)程序的算法有更全面更進(jìn)一步的認(rèn)識(shí)，根據(jù)不同的需求，采用不同的數(shù)據(jù)存儲(chǔ)方式，不一定要用棧，二叉樹等高級(jí)類型，有時(shí)用基本的一維數(shù)組，只要運(yùn)用得當(dāng)，也能達(dá)到相同的效果，甚至更佳，就如這次的課程設(shè)計(jì)，通過用for的多重循環(huán)，舍棄多余的循環(huán)，提高了程序的運(yùn)行效率。在編寫這個(gè)程序的過程中，我復(fù)習(xí)了之前學(xué)的基本語法，哈弗曼樹最小路徑的求取，哈弗曼編碼及譯碼的應(yīng)用范圍，程序結(jié)構(gòu)算法等一系列的問題它

30、使我對(duì)程序算法改變了看法。在這次設(shè)計(jì)過程中，體現(xiàn)出自己單獨(dú)設(shè)計(jì)模具的能力以及綜合運(yùn)用知識(shí)的能力，體會(huì)了學(xué)以致用、突出自己勞動(dòng)成果的喜悅心情，也從中發(fā)現(xiàn)自己平時(shí)學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補(bǔ)。</p><p>　　本次課程設(shè)計(jì)的目的是：把一個(gè)隨機(jī)輸入的字符串中不同字符作為葉子結(jié)點(diǎn)元素，把其在該字符串中出現(xiàn)的次數(shù)作為權(quán)值構(gòu)造一個(gè)赫夫曼樹，并得到各個(gè)葉子結(jié)點(diǎn)的赫夫曼編碼和整個(gè)輸入的字符串的赫夫曼編碼。在寫代碼前，首

31、先，對(duì)問題進(jìn)行了分析，明確了目標(biāo)，列出了大的框架，然后逐漸細(xì)化，劃分出不同的功能模塊，由具體的子函數(shù)去實(shí)現(xiàn)，先在紙上編寫代碼，寫好后進(jìn)行了反復(fù)的邏輯推理，發(fā)現(xiàn)并解決邏輯問題，然后，上機(jī)調(diào)試，方法是：一個(gè)一個(gè)功能模塊分開進(jìn)行調(diào)試，主要看調(diào)試的模塊能否達(dá)到預(yù)期的結(jié)果，這樣可以縮小排錯(cuò)的范圍，便以糾錯(cuò)和提高編程的效率，當(dāng)每個(gè)功能模塊都調(diào)試好后，就把各個(gè)部分組合起來，再進(jìn)行調(diào)試，主要檢查各函數(shù)接口是否正確，當(dāng)達(dá)到預(yù)期的結(jié)果，調(diào)試結(jié)束，編程部分完

32、成，然后按實(shí)驗(yàn)要求完成實(shí)驗(yàn)報(bào)告。</p><p>　　由于寫代碼前做了充分的準(zhǔn)備工作，所以寫起代碼來比較順利，使編程的效率有不少的提高并且最終達(dá)到實(shí)驗(yàn)預(yù)期的結(jié)果。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 蘇仕華．?dāng)?shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)．北京：機(jī)械工業(yè)出版社，2005</p><p>　　[2]

33、 嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)．北京：清華大學(xué)出版社，1997</p><p>　　[3]王成端, 徐翠霞．?dāng)?shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)與習(xí)題解析 北京-中國電力出版社，2006</p><p>　　[4]Adam Drozdek．?dāng)?shù)據(jù)結(jié)構(gòu)與算法，北京：清華大學(xué)出版社，2006</p><p>　　[5]李春葆，金晶．?dāng)?shù)據(jù)結(jié)構(gòu)教程．北京：清華大學(xué)出版社，2006</p&