Huffman編解碼問題——講解

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

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

3、; 左孩子指針int RChild ；/右孩子指針；datacode0Z1001C1012B113A0202）編碼表結(jié)點(diǎn)結(jié)構(gòu)（如右圖2-6所示）struct HCode char data； char codeuoo】；圖2-6 Huffman樹編碼結(jié)構(gòu)3)Huffman類結(jié)構(gòu)classHuffma nprivate :HNode * HTree ;/Huffman 樹HCode * HCodeTable ;/Huffman 編碼char str 1024; char表leaf256; int a256;/輸入的原始字符串/葉子public :節(jié)點(diǎn)對應(yīng)的字符/記錄每個岀現(xiàn)字符的個數(shù)int n;

4、/葉子節(jié)點(diǎn)數(shù)void init();/初始化void CreateHTree(); 倉曜 huffman 樹 voidSelectMin(int &x, int &y, int s, int evoid CreateCodeTableo; 創(chuàng)建編碼表void Encode(char *d); 編碼void Decode(char *s, char *d); 解碼void print(int i, int m); 打印 Huffman 樹 ? Huffman();根據(jù)實(shí)驗(yàn)要求，分步驟實(shí)現(xiàn)如下：步驟1 ：統(tǒng)計(jì)輸入的字符串中字符頻率式 計(jì)效Huffman編碼的第一步需要使用字符岀現(xiàn)的頻率作為輸入，本

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

6、o； int i=o； while（ ch匸V） & （cm= n ）nN um【ch】+; str【i+ = ch; ch = ci n.geto;/記錄每一個字符出現(xiàn)的次數(shù)/統(tǒng)計(jì)字符岀現(xiàn)的次數(shù) /記錄原始字符串 讀取下一個字符str【i】=, o其中，整型數(shù)組變量 nNum 用來記錄每一個字符岀現(xiàn)的次數(shù)（若該字符未岀現(xiàn)，則 對應(yīng)的nNumch的值為。），可以把讀取的字符ch的ASCII碼當(dāng)成，當(dāng) ch 岀現(xiàn)時，nNum【ch】自動加一。當(dāng)然，數(shù)組nNum 中的等于零的字符會有很多，不方便后續(xù) 建，因此可hufma n 樹的創(chuàng)以進(jìn)行過濾，僅留下岀現(xiàn)次數(shù)大于零的字符。因此，完整的初始化代碼如下

7、： voidHuffman : init（）?n = o； for （ i=0； io）leaf n】= （char）i；a【n】=nN um【i；/若nNum i=o說明該字符未岀現(xiàn)其中，數(shù)組 leaf 存儲岀現(xiàn)次數(shù)大于零的字符，相應(yīng)的數(shù)組a存儲該字符岀現(xiàn)的次數(shù),n為字符數(shù)，作為步驟2創(chuàng)建Huffman 樹的輸入。字符數(shù)組 str存儲用戶 輸入的字符串，作為步驟5編碼的輸入。當(dāng)然，也可以使用其它方法進(jìn)行字符的統(tǒng)計(jì)，請讀者自行思考。該步驟在教材 542小節(jié)中進(jìn)行了詳細(xì)的講解和實(shí)現(xiàn)，其中有一個選擇權(quán)值之中最小的兩個權(quán)值的函數(shù)，即函數(shù) SelectMin(int &x, int &y, int s

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

9、i；具體實(shí)現(xiàn)如下：eoid Huffman : SelectMin(int &x, int &y, int s, intint i;for( i=s i=e i+)if ( HTree【i.parent = -dx=y= i; break;找岀第一個有效權(quán)值 x，并令y=xfor ( ; iei+)if ( HTree【i.parent = -1)該權(quán)值未使用過if ( HTree i. weight HTree【x weight)y = X; x = i;/迭代，依次找岀前兩個最小值else if(x=y)n(HTree【h weight HTreey. weight)y = i;/找岀第2

10、個有效權(quán)值 y特別說明，本例中葉子節(jié)點(diǎn)數(shù) n作為成員變量，因此，huffman類的成員函數(shù)的 參數(shù)中不必在添加int n這個參數(shù)，直接使用 n即可。步驟3 :打印 Huffman 樹Huffman樹的直觀表示方式由多種，我們常見的樹狀結(jié)構(gòu)如圖所示是其中的一種， 此外還有如圖a所示的嵌套集合表示法，如圖 b所示的廣義表表示法和圖 c所示的凹入表示法A圖-8其他表示法樹型表示法當(dāng)結(jié)點(diǎn)很多的時候，不容易打印的非常合適，所以我們可以選擇使用凹入表的方式打印任意形狀的 Huffman 樹。根結(jié)點(diǎn)空一格直接打印，第 2層結(jié)點(diǎn)空2格打印， 第3層結(jié)點(diǎn)空3格的打印，以此類推，每個節(jié)點(diǎn)占用獨(dú)立的一行。由于只有葉

11、子結(jié)點(diǎn)是有對應(yīng) 字符的，所以其他結(jié)點(diǎn)可以打印該結(jié)點(diǎn)的權(quán)值。因此，我們可以嘗試使用二叉樹前序遍歷的方式來進(jìn)行直觀的打印。示例代碼如下：#define N 10/定義樹的最大深度void Huffman : print（int i, int m） if（HTreei.LChild = -dcoutsetfill （ ）setw（m+1）eafisetfill（-）setw（N-m） n；e ppH n nelsesetfill（ ）setw（m+i）HTree【h weight令（-）setw（N-m）n；（HTree【i】.LChild ,m+i）；（HTree【i】.RChild ,m+i）；

12、其中，參數(shù)i表示Huffman樹的下標(biāo)為i的結(jié)點(diǎn)，m表示該結(jié)點(diǎn)的層次。該函數(shù) 是遞歸函數(shù)，所以在 maino函數(shù)中第一次調(diào)用該函數(shù)時，實(shí)參為i=2*n-2, m=i；A 步驟 4 ：創(chuàng)建編碼表編碼表生成后， 進(jìn)行編碼相對容易， 實(shí)驗(yàn)要求只要能夠顯示出來編碼后的字符串即可， 也就 是說，若A的編碼為0 , B的編碼為10,則字符串AAB的編碼顯示為0010即可。由于初始 化函數(shù)中己經(jīng)記錄了輸入的字符串 str ，因此直接使用該變量作為輸入即可。 voidHuffman : Encode(char * d)char *s= str;while (* s!=0)forif(i(n*ts i=0;Hi

13、nC;oi+d+)eTable i.data )strcat(d，HCodeTable【i】.code)； d 為編碼后的字符串break;s+;上述代碼用于本實(shí)驗(yàn)的編碼顯示和驗(yàn)證是沒問題的,但并沒有實(shí)現(xiàn)真正的壓縮效果, 這時因 為代碼的實(shí)現(xiàn)。比如若 A的編碼為100 ,實(shí)際壓縮中使用3個bit代替字符A,本例中使 用 了 3 個字符“ 100 ”來編碼, 因此沒有真正的壓縮效果。 如果希望能夠按照 bit 的方式進(jìn) 行編碼, 需要使用位運(yùn)算符進(jìn)行 bit 的操作,將編碼按照 bit 的方式寫入文件。請同學(xué)們自行思考,如何采用 bit 的方式使用 Huffman 編碼壓縮文件。步驟 6: 解碼

14、該步驟請參考教材 5.4.2 小節(jié)中的講解和實(shí)現(xiàn)即可。步驟 7: 測試 根據(jù)測試數(shù)據(jù),編寫如下的測試 man() 函數(shù)進(jìn)行測試：an HFCode; 請輸入要編碼的字符串： de.init ();void main ()；5cout創(chuàng)建 Huffman 樹“endl; HFCode.CreateHTree (); HFCode.print (2*HFCode.n-2,1); cout”創(chuàng)建Huffman 編碼表en dl;HFCode.CreateCod eTable();char d 1024=0;HFCode.E ncoded cout 編碼結(jié)果： de ndl； char S1024=0

15、;HFCode. Decoded,s）； cout ”解碼結(jié)果:se ndl;最后，也是特別要注意的地方內(nèi)存泄露。本實(shí)驗(yàn)中的主要數(shù)據(jù)結(jié)構(gòu) HTree和HCodeTable都是動態(tài)內(nèi)存，因此必須要在Huffman樹的析構(gòu)函數(shù)中進(jìn)行內(nèi)存清理，示例代碼如下：Huffman : Huffman。delete HTree; deleteHCodeTable;本實(shí)驗(yàn)的運(yùn)行效果如圖所示。圖2-9運(yùn)行測試結(jié)果根據(jù)要求，我們下面討論一下Huffman 編碼的壓縮效果。數(shù)據(jù)壓縮比（英文名稱：datacompression ratio ）為衡量數(shù)據(jù)壓縮器壓縮效率的質(zhì)量指標(biāo)。是指數(shù)據(jù)被壓縮的比例。其計(jì)算公式如下：壓縮比=壓縮前字節(jié)數(shù)/壓縮后字節(jié)數(shù)本實(shí)驗(yàn)為了方便顯示和驗(yàn)證算法，采用的是字符串方式進(jìn)行壓縮，