Huffman編解碼問題——講解

1、2.5 huffman 編碼問題實驗四題目 2:利用二叉樹結構實現(xiàn)哈夫曼編 / 解碼器?；疽螅?、初始化(init)：能夠?qū)斎氲娜我忾L度的字符串s進行統(tǒng)計，統(tǒng)計每個字符的頻度，并建立哈夫曼樹2 、 建立編碼表(createtable) ：利用己經(jīng)建好的哈夫曼樹進行編碼，并將每個字符的 編碼輸出。3 、編碼(encoding) : 根據(jù)編碼表對輸能的字符串進行編碼，并將編碼后的字符串輸出。4 、譯碼(decoding) : 利用己經(jīng)建好的哈夫曼樹對編碼后的字符串進行譯碼，并輸出譯碼結果。5 、 打印 (print) : 以直觀的方式打印哈夫曼樹(選作)6 、 計算輸能的字符串編碼前和編碼后

2、的長度，并進行分析，討論赫夫曼編碼的壓縮效果。7 、 可采用二進制編碼方式(選作)實驗講解：huffman編解碼的實驗按照模塊化分，可以劃分成如下部分:a) 統(tǒng)計輸能的字符串中字符頻率b) 創(chuàng)建huffman 樹c) 打印huffman 樹d) 創(chuàng)建huffman 編碼表e) 對輸能的字符串進行編碼并輸出編碼結果f) 對編碼結果進行解碼，并輸出解碼后的字符串g) 最后編寫測試函數(shù)，測試上述步驟的正確性。根據(jù)模塊化分，設計huffman 的存儲結構如下：1) huffman 樹的結點結構struct hnode intweight;/結點權值intparent;/雙親指針intlchild;/左

3、孩子指針int rchild ; /右孩子指針;2）編碼表結 點結構（如 右圖2-6所 示）struct hcode char data; char codel00;；200datacodez1001c1012b113a0圖2-6 huffman樹編碼結構3) huffman類結構class huffmanprivate :hnodc* htree; hcod e* hcodetable; char st r1024; char leaf 256; i nt a256; public : int n;void init ();void createhtree ();voidselectmin(

4、int&x,/huffman 樹huffman編碼表/輸入的原始字符串/葉子 節(jié)點對應的字符/記錄每個 出現(xiàn)字符的個數(shù)/葉子節(jié)點數(shù)/初始化/創(chuàng)建huffman樹int &y, int s, int e ）;void createcodetable ();void encode(char * d);void decode(char *s, char *d);void print(int i , intn);/創(chuàng)建編碼表/編碼/解碼/打印huffman樹huffman ();根據(jù)實驗要求，分步驟實現(xiàn)如下：步驟1：統(tǒng)計輸入的字符串中字符頻率huffman編碼的第一步需要使用字符出現(xiàn)的頻率作為輸入，本

5、實驗使用從鍵盤輸入的方式進行，需要的解決得問題有 2個：一是輸入的字符串中間有空格如何處理？二是如何使統(tǒng) 計效率更 高？例如：char str1024;cinstr;上述代碼運行后輸入字符串，但cmstr 遇到空格就停止本次讀取，所以我們需要使用其它的方法來進行輸入，即需要使用cm. get () 函數(shù)進行字符串讀取。 get () 方法每調(diào)用一次， 讀取一個字符，該字符的 ascii 碼作為返回值返回，換行回車等控制字符也當作普通字符進行讀取，因此需要指定結束讀取的標志字符，才能停止get () 函數(shù)的循環(huán)調(diào)用。 本實驗中可以/ 記錄每一個字符出現(xiàn)的次數(shù)將字符讀取和統(tǒng)計結合在一起進行。示例代

6、碼如下：intnnum256= 0; intch = cin .get (); inti =0;/ 統(tǒng)計字符出現(xiàn)的次數(shù)/ 記錄原始字符串 / 讀取下一個字符 while ( ch!=v) &(c h!= n ) nnumch+; str i + = ch; ch =(); str i = ，其中，整型數(shù)組變量cin . get0nnurffl來記錄每一個字符出現(xiàn)的次數(shù)(若該字符未出現(xiàn)，則對應 的nnumch的值為0),可以把讀取的字符 ch的ascii碼當成，當ch出現(xiàn)時，nnumch自 動加一。當然，數(shù)組nnu時的等于零的字符會有很多，不方便后續(xù) hufman樹的創(chuàng)建，因此可以進行過濾，僅留

7、下出現(xiàn)次數(shù)大于零的字符。因此，完整的初始化代碼如下： voidhuffman : init ()?n = 0;for ( i =0; i 0)/若nnumi =0說明該字符未出現(xiàn)leaf n = ( char)i ; a n = nnum i ;n+;其中，數(shù)組leaf存儲出現(xiàn)次數(shù)大于零的字符，相應的數(shù)組a存儲該字符出現(xiàn)的次數(shù)，n為字符數(shù)，作為步驟2創(chuàng)建huffman樹的輸入。字符數(shù)組 str存儲用戶輸入的字符串，作為步驟5編碼的輸入。當然，也可以使用其它方法進行字符的統(tǒng)計，請讀者自行思考。步驟2:創(chuàng)建huffman樹權值該步驟在教材5.4.2 小節(jié)中進行了詳細的講解和實現(xiàn)，其中有一個選擇權值

8、之中最小的兩個 的函數(shù)，即函數(shù) selectmin(int &x, int &y, int s, int e );其中x為最小權值，y為次小權值，s為權值范圍的起始下標，e為結束下標。該函數(shù)如何實現(xiàn)呢？分析：從所有未使用過的權值表中選擇兩個最小的權值，可以有多種方法，比如一次選擇一個最小的，選擇2遍；或者進行迭代，一次選擇出兩個。顯然，后者的時間效率較高，因此 我們采用后者進行實現(xiàn)。迭代選擇兩個最小值得基本思想是：1、 從權值表 htree s. e 中選取第一個未使用結點下標為 x, 并設 y=x ；2、 從剩下的未使用的權值中依次遍歷若當前結點 i 的權值 結點 x 的權值，則迭代，即y=

9、x; x = i ;否則：若此時y=x ( 即 y 還未賦值) ，則y=i ;若此時當前結點i的權值y結點的權值，則具體實現(xiàn)如下：void huffman : selectmin(int &x, int int i ;for ( i =s; i =e; i +)if ( htree i.parent = -1)x = y= i ; break ;for ( ; i e; i +)if ( htree i.parent = -1)if ( htree i . weight y = x; x = i ;else if ( x=y) | ( y = i;& y,y=i ;int s, int e )

10、/ 找出第一個有效權值x ，并令y=x/ 該權值未使用過 htree x. weight )/ 迭代，依次找出前兩個最小值htree i . weight htree y. weight )/ 找出第 2個有效權值y特別說明，本例中葉子節(jié)點數(shù)n作為成員變量，因此，huffman類的成員函數(shù)的參數(shù)中不必在添加int n這個參數(shù)，直接使用 n即可。步驟 3 ：打印 huffman 樹huffman 樹的直觀表示方式由多種，我們常見的樹狀結構如圖所示是其中的一種，此外還有如圖a所示的嵌套集合表示法，如圖b所示的廣義表表示法和圖c所示的凹入表示法。口e圖-8其他表示法樹型表示法當結點很多的時候，不容易

11、打印的非常合適，所以我們可以選擇使用凹入表的方式打印任意形狀的 hufman樹。根結點空一格直接打印，第2層結點空2格打印，第3層結點空3格的打印，以此類推，每個節(jié)點占用獨立的一行。由于只有葉子結點是有對應字符的，所以其他結點可以打印該結點的權值。因此，我們可以嘗試使用二叉樹前序遍歷的方式來進行直觀的 打印。示例代碼如下：#define n 10/定義樹的最大深度void huffman 二 print(int i , int n) if ( htree i.lchild = -1)cout setfill ( )setw(m+1)eaf i sefill( - ):setw(n-n) n；e

12、lse cout setfill( )setw( n+1)htree i . weight setfill( - )setw(nkn)4n ； print (htreei . lchild , n+1); print (htreei . rchild , n+1);其中，參數(shù)i表示huffman樹的下標為i的結點，n表示該結點的層次。該函數(shù)是遞歸 函數(shù)，所 以在main()函數(shù)中第一次調(diào)用該函數(shù)時，實參為 i =2*n-2, m=1;步驟4：創(chuàng)建編碼表該步驟請參考教材5.4.2 小節(jié)中的講解和實現(xiàn)即可。 步驟5: 編碼編碼表生成后， 進行編碼相對容易， 實驗要求只要能夠顯示出來編碼后的字符串即

13、可， 也就 是說，若a的編碼為0, b的編碼為10,則 字符串a(chǎn)ab勺編碼顯示為0010即可。由于初始化函數(shù)中己經(jīng)記錄了輸入的字符串 str ，因此直接使用該變量作為輸入即可。 void huffman: en code(char * d)char *s = str ;while (* s! =0 )for (int i =0; i n; i +)if (*s = hcodetablei.data ) strcat ( d, hcodetable i .code);/d 為編碼后的字符串break ; s+; 上述代碼用于本實驗的編碼顯示和驗證是沒問題的，但并沒有實現(xiàn)真正的壓縮效果，這時因 為

14、代碼的實現(xiàn)。比如若 a的編碼為100,實際壓縮中使用3個bit代替字符a,本例中使 用了 3個字符“ 100”來編碼，因此沒有真正的壓縮效果。如果希望能夠按照 bit 的方式進 行編碼，需要使用位運算符進行bit 的操作，將編碼按照 bit 的方式寫入文件。請同學們自行思考，如何采用 bit 的方式使用 huffman 編碼壓縮文件。步驟 6: 解碼該步驟請參考教材5.4.2 小節(jié)中的講解和實現(xiàn)即可。步驟 7: 測試根據(jù)測試數(shù)據(jù)，編寫如下的測試man() 函數(shù)進行測試： void main()huffman hfcode;cout 請輸入要編碼的字符串： ；hfcode. init ();co

15、ut 創(chuàng)建 huffman 枳:endl ;hfcode. createhtree ();hfcode. print (2*hfcode. n-2,1);cout ”創(chuàng)建huffman 編碼表: endl ;hfcode. createcodetable ();char d1024=0;hfcode. encode( d);cout 編碼結果： dendl ;char s1024=0;hfcodedecode(d, s); cout 解碼結果: sendl ;最后，也是特別要注意的地方內(nèi)存泄露。本實驗中的主要數(shù)據(jù)結構htree和hcodetable都是動態(tài)內(nèi)存，因此必須要在huffman樹的析構函數(shù)中進行內(nèi)存清理，示例代 碼如下：huffman : huffman。delete htree; delete 口hcodetable;）圖2-9運行測試結果根據(jù)要求，我們下面討論一下huffman編碼的壓縮效果。數(shù)據(jù)壓縮比（英文名稱：data compression ratio ）為衡量數(shù)據(jù)壓縮器壓縮效率的質(zhì)量指標。是指數(shù)據(jù)被壓縮的比例。其計算公式如下：壓縮比=壓縮前字節(jié)數(shù)/壓縮后字節(jié)數(shù)本實驗為了方便顯示和驗證算法，采用的是