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

2 5 Huffman編碼問(wèn)題 實(shí)實(shí)驗(yàn)驗(yàn)四四 題題目目2 利用二叉樹(shù)結(jié)構(gòu)實(shí)現(xiàn)哈夫曼編 解碼器 基本要求 1 初始化 lnit 能夠?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ì)算輸入的字符串編碼前和編碼后的長(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 int weight 結(jié)點(diǎn)權(quán)值 int parent 雙親指針 int LChild 左孩子指針 20 datacode 0 Z 100 1 C 101 2 B 11 3A0 5 11 private HNode HTree HCode HCodeTable char str 1024 char leaf 256 int a 256 public Huffman 樹(shù) Huffman 編碼表 輸入的原始字符串 葉子節(jié)點(diǎn)對(duì)應(yīng)的字符 記錄每個(gè)出現(xiàn)字符的個(gè)數(shù) int RChild 右孩子指針 2 編碼表結(jié) 點(diǎn)結(jié)構(gòu) 如 右圖2 6所示 struct HCode char data char code 100 圖圖2 6 Huffman樹(shù)編碼結(jié)構(gòu)樹(shù)編碼結(jié)構(gòu) 3 Huffman類結(jié)構(gòu) class Huffman int n 葉子節(jié)點(diǎn)數(shù) void init 初始化 void CreateHTree 創(chuàng)建 huffman 樹(shù) voidSelectMin int void CreateCodeTable 創(chuàng)建編碼表 void Encode char d 編碼 void Decode char s char d 解碼 void print int i int m 打印 Huffman 樹(shù) Huffman 根據(jù)實(shí)驗(yàn)要求 分步驟實(shí)現(xiàn)如下 步步驟驟1 統(tǒng)統(tǒng)計(jì)計(jì)輸輸入入的的字字符符串串中中字字符符頻頻率率 Huffman編碼的第一步需要使用字符出現(xiàn)的頻率作為輸入 本實(shí)驗(yàn)使用從鍵盤輸入的方 式進(jìn)行 需要的解決得問(wèn)題有2個(gè) 一是輸入的字符串中間有空格如何處理 二是如何使統(tǒng) 計(jì)效率更高 例如 char str 1024 cin str 記錄每一個(gè)字符出現(xiàn)的次數(shù) 統(tǒng)計(jì)字符出現(xiàn)的次數(shù) 記錄原始字符串 讀取下一個(gè)字符 上述代碼運(yùn)行后輸入字符串 但cm str遇到空格就停止本次讀取 所以我們需要使用 其它的方法來(lái)進(jìn)行輸入 即需要使用cm get 函數(shù)進(jìn)行字符串讀取 get 方法每調(diào)用一次 讀取一個(gè)字符 該字符的ASCII碼作為返回值返回 換行回車等控制字符也當(dāng)作普通字符 進(jìn)行讀取 因此需要指定結(jié)束讀取的標(biāo)志字符 才能停止get 函數(shù)的循環(huán)調(diào)用 本實(shí)驗(yàn)中可以將字符讀取和統(tǒng)計(jì)結(jié)合在一起進(jìn)行 示例代碼如下 int nNum 256 0 int ch cin get int i 0 while ch V str i ch ch cin get str i 0 其中 整型數(shù)組變量nNum用來(lái)記錄每一個(gè)字符出現(xiàn)的次數(shù) 若該字符未出現(xiàn) 則對(duì)應(yīng) 的nNum ch 的值為0 可以把讀取的字符ch的ASCII碼當(dāng)成 當(dāng)ch出現(xiàn)時(shí) nNum ch 自 動(dòng)加一 當(dāng)然 數(shù)組nNum中的等于零的字符會(huì)有很多 不方便后續(xù)hufman樹(shù)的創(chuàng)建 因此可 以進(jìn)行過(guò)濾 僅留下出現(xiàn)次數(shù)大于零的字符 因此 完整的初始化代碼如下 void Huffman init n 0 for i 0 i0 若nNum i 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ǔ)用戶輸入的字符串 作為 步驟5編碼的輸入 當(dāng)然 也可以使用其它方法進(jìn)行字符的統(tǒng)計(jì) 請(qǐng)讀者自行思考 步步驟驟2 創(chuàng)創(chuàng)建建Huffman樹(shù)樹(shù) 該步驟在教材5 4 2小節(jié)中進(jìn)行了詳細(xì)的講解和實(shí)現(xiàn) 其中有一個(gè)選擇權(quán)值之中最小的兩個(gè) 權(quán)值的函數(shù) 即函數(shù)SelectMin int 其中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 x x i 否則 若此時(shí)y x 即y還未賦值 則y i 若此時(shí)當(dāng)前結(jié)點(diǎn)i的權(quán)值 y結(jié)點(diǎn)的權(quán)值 則y i 具體實(shí)現(xiàn)如下 void Huffman SelectMin int for i s i e i if HTree i parent 1 x y i break 找出第一個(gè)有效權(quán)值x 并令y x for i e i if HTree i parent 1 該權(quán)值未使用過(guò) if HTree i weight HTree x weight y x x i 迭代 依次找出前兩個(gè)最小值 else if x y HTree i weight HTree y weight y i 找出第2個(gè)有效權(quán)值y 特別說(shuō)明 本例中葉子節(jié)點(diǎn)數(shù)n作為成員變量 因此 huffman類的成員函數(shù)的參數(shù)中 不必在添加int n這個(gè)參數(shù) 直接使用n即可 步步驟驟3 打打印印Huffman樹(shù)樹(shù) Huffman樹(shù)的直觀表示方式由多種 我們常見(jiàn)的樹(shù)狀結(jié)構(gòu)如圖所示是其中的一種 此外 還有如圖a所示的嵌套集合表示法 如圖b所示的廣義表表示法和圖c所示的凹入表示法 A 圖 7樹(shù)型表示法 圖 8其他表示法 樹(shù)型表示法當(dāng)結(jié)點(diǎn)很多的時(shí)候 不容易打印的非常合適 所以我們可以選擇使用凹入表 的方式打印任意形狀的Huffman樹(shù) 根結(jié)點(diǎn)空一格直接打印 第2層結(jié)點(diǎn)空2格打印 第3 層結(jié)點(diǎn)空3格的打印 以此類推 每個(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 m if HTree i LChild 1 cout setfill setw m 1 leaf i setfill setw N m n else cout setfill setw m 1 HTree i weight setfill setw N m n print HTree i LChild m 1 print HTree i RChild m 1 其中 參數(shù)i表示Huffman樹(shù)的下標(biāo)為i的結(jié)點(diǎn) m表示該結(jié)點(diǎn)的層次 該函數(shù)是遞歸 函數(shù) 所以在main 函數(shù)中第一次調(diào)用該函數(shù)時(shí) 實(shí)參為i 2 n 2 m 1 步步驟驟4 創(chuàng)創(chuàng)建建編編碼碼表表 該步驟請(qǐng)參考教材5 4 2小節(jié)中的講解和實(shí)現(xiàn)即可 步步驟驟5 編編碼碼 編碼表生成后 進(jìn)行編碼相對(duì)容易 實(shí)驗(yàn)要求只要能夠顯示出來(lái)編碼后的字符串即可 也就 是說(shuō) 若A的編碼為0 B的編碼為10 則字符串AAB的編碼顯示為 0010 即可 由于初始 化函數(shù)中己經(jīng)記錄了輸入的字符串str 因此直接使用該變量作為輸入即可 void Huffman Encode char d char s str while s 0 for int i 0 i n i if s HCodeTable i data strcat d HCodeTable i code d 為編碼后的字符串 break s 上述代碼用于本實(shí)驗(yàn)的編碼顯示和驗(yàn)證是沒(méi)問(wèn)題的 但并沒(méi)有實(shí)現(xiàn)真正的壓縮效果 這時(shí)因 為代碼 的實(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è)測(cè)試試 根據(jù)測(cè)試數(shù)據(jù) 編寫(xiě)如下的測(cè)試man 函數(shù)進(jìn)行測(cè)試 void main Huffman HFCode cout 請(qǐng)輸入要編碼的字符串 HFCode init cout 創(chuàng)建 Huffman 樹(shù) endl HFCode CreateHTree HFCode print 2 HFCode n 2 1 cout 創(chuàng)建 Huffman 編 碼 表 endl HFCode CreateCodeTable char d 1024 0 HFCode Encode d cout 編碼結(jié)果 d endl char s 1024 0 HFCode Decode d s cout 解碼結(jié)果 s endl 最后 也是特別要注意的地方一一內(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 本實(shí)驗(yàn)的運(yùn)行效果如圖所示 圖2 9運(yùn)行測(cè)試結(jié)果 根據(jù)要求 我們下面討論一下Huffman編碼的壓縮效果 數(shù)據(jù)壓縮比 英文名稱 data compression ratio 為衡量數(shù)據(jù)壓縮器壓縮效率的質(zhì)量指標(biāo) 是指數(shù)據(jù)被壓縮的比例 其計(jì) 算公式如下 壓縮比 壓縮前字節(jié)數(shù) 壓縮后字節(jié)數(shù) 本實(shí)驗(yàn)為了方便顯示和驗(yàn)證算法 采用的是字符串方式進(jìn)行壓縮