哈夫曼編碼課程設計

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

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

3、，權值</p><p><b>　　目 錄</b></p><p><b>　　1 問題描述1</b></p><p><b>　　2 問題分析2</b></p><p><b>　　3 算法設計3</b></p><p>

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

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

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

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

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

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

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

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

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

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

14、t) 注：列表中最小節(jié)點的是指包括合并了的節(jié)點在內的所有節(jié)點，已經合并的節(jié)點不在列表。4 算法實現(xiàn)</p><p>　　%哈夫曼編碼的MATLAB實現(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);%最后兩個元素相加</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);%從第二列開始，每列的最后一個元素記錄特征元素在</p><p>

19、;<b>　　%該列的位置</b></p><p>　　r=(B(t-1,j)+B(t,j));%最后兩個元素相加</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ù)第二列開始依次對各列元素編碼</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%編碼結果</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>　?。?）哈夫曼編碼</b></p><p>　　對字符串進行編碼運行結果如圖5.2所示。</

28、p><p>　　圖1 哈夫曼編碼結果</p><p><b>　?。?）哈夫曼譯碼</b></p><p>　　另外就是在譯碼時沒能實用二進制流文件對相關知識沒能融會貫通，</p><p>　　圖5.3哈夫曼譯碼結果</p><p><b>　　結 論</b></p>

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

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

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

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

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