Huffman編解碼問(wèn)題——講解

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

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

3、孩子指針int rchild ; /右孩子指針;2）編碼表結(jié) 點(diǎn)結(jié)構(gòu)（如 右圖2-6所 示）struct hcode char data; char codel00;；200datacodez1001c1012b113a0圖2-6 huffman樹(shù)編碼結(jié)構(gòu)3) huffman類(lèi)結(jié)構(gòu)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 樹(shù)huffman編碼表/輸入的原始字符串/葉子 節(jié)點(diǎn)對(duì)應(yīng)的字符/記錄每個(gè) 出現(xiàn)字符的個(gè)數(shù)/葉子節(jié)點(diǎn)數(shù)/初始化/創(chuàng)建huffman樹(shù)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樹(shù)huffman ();根據(jù)實(shí)驗(yàn)要求，分步驟實(shí)現(xiàn)如下：步驟1：統(tǒng)計(jì)輸入的字符串中字符頻率huffman編碼的第一步需要使用字符出現(xiàn)的頻率作為輸入，本

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

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

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

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

9、x; x = i ;否則：若此時(shí)y=x ( 即 y 還未賦值) ，則y=i ;若此時(shí)當(dāng)前結(jié)點(diǎn)i的權(quán)值y結(jié)點(diǎn)的權(quán)值，則具體實(shí)現(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、/ 找出第一個(gè)有效權(quán)值x ，并令y=x/ 該權(quán)值未使用過(guò) htree x. weight )/ 迭代，依次找出前兩個(gè)最小值htree i . weight htree y. weight )/ 找出第 2個(gè)有效權(quán)值y特別說(shuō)明，本例中葉子節(jié)點(diǎn)數(shù)n作為成員變量，因此，huffman類(lèi)的成員函數(shù)的參數(shù)中不必在添加int n這個(gè)參數(shù)，直接使用 n即可。步驟 3 ：打印 huffman 樹(shù)huffman 樹(shù)的直觀表示方式由多種，我們常見(jiàn)的樹(shù)狀結(jié)構(gòu)如圖所示是其中的一種，此外還有如圖a所示的嵌套集合表示法，如圖b所示的廣義表表示法和圖c所示的凹入表示法。口e圖-8其他表示法樹(shù)型表示法當(dāng)結(jié)點(diǎn)很多的時(shí)候，不容易

11、打印的非常合適，所以我們可以選擇使用凹入表的方式打印任意形狀的 hufman樹(shù)。根結(jié)點(diǎn)空一格直接打印，第2層結(jié)點(diǎn)空2格打印，第3層結(jié)點(diǎn)空3格的打印，以此類(lèi)推，每個(gè)節(jié)點(diǎn)占用獨(dú)立的一行。由于只有葉子結(jié)點(diǎn)是有對(duì)應(yīng)字符的，所以其他結(jié)點(diǎn)可以打印該結(jié)點(diǎn)的權(quán)值。因此，我們可以嘗試使用二叉樹(shù)前序遍歷的方式來(lái)進(jìn)行直觀的 打印。示例代碼如下：#define n 10/定義樹(shù)的最大深度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樹(shù)的下標(biāo)為i的結(jié)點(diǎn)，n表示該結(jié)點(diǎn)的層次。該函數(shù)是遞歸 函數(shù)，所 以在main()函數(shù)中第一次調(diào)用該函數(shù)時(shí)，實(shí)參為 i =2*n-2, m=1;步驟4：創(chuàng)建編碼表該步驟請(qǐng)參考教材5.4.2 小節(jié)中的講解和實(shí)現(xiàn)即可。 步驟5: 編碼編碼表生成后， 進(jìn)行編碼相對(duì)容易， 實(shí)驗(yàn)要求只要能夠顯示出來(lái)編碼后的字符串即

13、可， 也就 是說(shuō)，若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+; 上述代碼用于本實(shí)驗(yàn)的編碼顯示和驗(yàn)證是沒(méi)問(wèn)題的，但并沒(méi)有實(shí)現(xiàn)真正的壓縮效果，這時(shí)因 為

14、代碼的實(shí)現(xiàn)。比如若 a的編碼為100,實(shí)際壓縮中使用3個(gè)bit代替字符a,本例中使 用了 3個(gè)字符“ 100”來(lái)編碼，因此沒(méi)有真正的壓縮效果。如果希望能夠按照 bit 的方式進(jìn) 行編碼，需要使用位運(yùn)算符進(jìn)行bit 的操作，將編碼按照 bit 的方式寫(xiě)入文件。請(qǐng)同學(xué)們自行思考，如何采用 bit 的方式使用 huffman 編碼壓縮文件。步驟 6: 解碼該步驟請(qǐng)參考教材5.4.2 小節(jié)中的講解和實(shí)現(xiàn)即可。步驟 7: 測(cè)試根據(jù)測(cè)試數(shù)據(jù)，編寫(xiě)如下的測(cè)試man() 函數(shù)進(jìn)行測(cè)試： void main()huffman hfcode;cout 請(qǐng)輸入要編碼的字符串： ；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 編碼結(jié)果： dendl ;char s1024=0;hfcodedecode(d, s); cout 解碼結(jié)果: sendl ;最后，也是特別要注意的地方內(nèi)存泄露。本實(shí)驗(yàn)中的主要數(shù)據(jù)結(jié)構(gòu)htree和hcodetable都是動(dòng)態(tài)內(nèi)存，因此必須要在huffman樹(shù)的析構(gòu)函數(shù)中進(jìn)行內(nèi)存清理，示例代 碼如下：huffman : huffman。delete htree; delete 口hcodetable;）圖2-9運(yùn)行測(cè)試結(jié)果根據(jù)要求，我們下面討論一下huffman編碼的壓縮效果。數(shù)據(jù)壓縮比（英文名稱(chēng)：data compression ratio ）為衡量數(shù)據(jù)壓縮器壓縮效率的質(zhì)量指標(biāo)。是指數(shù)據(jù)被壓縮的比例。其計(jì)算公式如下：壓縮比=壓縮前字節(jié)數(shù)/壓縮后字節(jié)數(shù)本實(shí)驗(yàn)為了方便顯示和驗(yàn)證算法，采用的是