Huffman編解碼問題——講解

2 5 Huffman編碼問題 實實驗驗四四 題題目目2 利用二叉樹結(jié)構(gòu)實現(xiàn)哈夫曼編 解碼器 基本要求 1 初始化 lnit 能夠?qū)斎氲娜我忾L度的字符串s進行統(tǒng)計 統(tǒng)計每個字符的頻度 并建立哈夫曼樹 2 建立編碼表 CreateTable 利用己經(jīng)建好的哈夫曼樹進行編碼 并將每個字符的 編碼輸出 3 編碼 Encoding 根據(jù)編碼表對輸入的字符串進行編碼 并將編碼后的字符串輸 出 4 譯碼 Decoding 利用己經(jīng)建好的哈夫曼樹對編碼后的字符串進行譯碼 并輸出 譯碼結(jié)果 5 打印 Print 以直觀的方式打印哈夫曼樹 選作 6 計算輸入的字符串編碼前和編碼后的長度 并進行分析 討論赫夫曼編碼的壓 縮效果 7 可采用二進制編碼方式 選作 實驗講解 Huffman編解碼的實驗按照模塊化分 可以劃分成如下部分 a 統(tǒng)計輸入的字符串中字符頻率 b 創(chuàng)建Huffman樹 c 打印Huffman樹 d 創(chuàng)建Huffman編碼表 e 對輸入的字符串進行編碼并輸出編碼結(jié)果 f 對編碼結(jié)果進行解碼 并輸出解碼后的字符串 g 最后編寫測試函數(shù) 測試上述步驟的正確性 根據(jù)模塊化分 設(shè)計Huffman的存儲結(jié)構(gòu)如下 1 Huffman樹的結(jié)點結(jié)構(gòu) struct HNode int weight 結(jié)點權(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 樹 Huffman 編碼表 輸入的原始字符串 葉子節(jié)點對應(yīng)的字符 記錄每個出現(xiàn)字符的個數(shù) int RChild 右孩子指針 2 編碼表結(jié) 點結(jié)構(gòu) 如 右圖2 6所示 struct HCode char data char code 100 圖圖2 6 Huffman樹編碼結(jié)構(gòu)樹編碼結(jié)構(gòu) 3 Huffman類結(jié)構(gòu) class Huffman int n 葉子節(jié)點數(shù) void init 初始化 void CreateHTree 創(chuàng)建 huffman 樹 voidSelectMin int void CreateCodeTable 創(chuàng)建編碼表 void Encode char d 編碼 void Decode char s char d 解碼 void print int i int m 打印 Huffman 樹 Huffman 根據(jù)實驗要求 分步驟實現(xiàn)如下 步步驟驟1 統(tǒng)統(tǒng)計計輸輸入入的的字字符符串串中中字字符符頻頻率率 Huffman編碼的第一步需要使用字符出現(xiàn)的頻率作為輸入 本實驗使用從鍵盤輸入的方 式進行 需要的解決得問題有2個 一是輸入的字符串中間有空格如何處理 二是如何使統(tǒng) 計效率更高 例如 char str 1024 cin str 記錄每一個字符出現(xiàn)的次數(shù) 統(tǒng)計字符出現(xiàn)的次數(shù) 記錄原始字符串 讀取下一個字符 上述代碼運行后輸入字符串 但cm str遇到空格就停止本次讀取 所以我們需要使用 其它的方法來進行輸入 即需要使用cm get 函數(shù)進行字符串讀取 get 方法每調(diào)用一次 讀取一個字符 該字符的ASCII碼作為返回值返回 換行回車等控制字符也當作普通字符 進行讀取 因此需要指定結(jié)束讀取的標志字符 才能停止get 函數(shù)的循環(huán)調(diào)用 本實驗中可以將字符讀取和統(tǒng)計結(jié)合在一起進行 示例代碼如下 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用來記錄每一個字符出現(xiàn)的次數(shù) 若該字符未出現(xiàn) 則對應(yīng) 的nNum ch 的值為0 可以把讀取的字符ch的ASCII碼當成 當ch出現(xiàn)時 nNum ch 自 動加一 當然 數(shù)組nNum中的等于零的字符會有很多 不方便后續(xù)hufman樹的創(chuàng)建 因此可 以進行過濾 僅留下出現(xiàn)次數(shù)大于零的字符 因此 完整的初始化代碼如下 void Huffman init n 0 for i 0 i0 若nNum i 0說明該字符未出現(xiàn) leaf n char i a n nNum i n 其中 數(shù)組leaf存儲出現(xiàn)次數(shù)大于零的字符 相應(yīng)的數(shù)組a存儲該字符出現(xiàn)的次數(shù) n 為字符數(shù) 作為步驟2創(chuàng)建Huffman樹的輸入 字符數(shù)組str存儲用戶輸入的字符串 作為 步驟5編碼的輸入 當然 也可以使用其它方法進行字符的統(tǒng)計 請讀者自行思考 步步驟驟2 創(chuàng)創(chuàng)建建Huffman樹樹 該步驟在教材5 4 2小節(jié)中進行了詳細的講解和實現(xiàn) 其中有一個選擇權(quán)值之中最小的兩個 權(quán)值的函數(shù) 即函數(shù)SelectMin int 其中x為最小權(quán)值 y為次小權(quán) 值 s為權(quán)值范圍的起始下標 e為結(jié)束下標 該函數(shù)如何實現(xiàn)呢 分析 從所有未使用過的權(quán)值表中選擇兩個最小的權(quán)值 可以有多種方法 比如一次選擇一 個最小的 選擇2遍 或者進行迭代 一次選擇出兩個 顯然 后者的時間效率較高 因此 我們采用后者進行實現(xiàn) 迭代選擇兩個最小值得基本思想是 1 從權(quán)值表HTree s e 中選取第一個未使用結(jié)點下標為x 并設(shè)y x 2 從剩下的未使用的權(quán)值中依次遍歷 若當前結(jié)點i的權(quán)值 結(jié)點x的權(quán)值 則迭代 即y x x i 否則 若此時y x 即y還未賦值 則y i 若此時當前結(jié)點i的權(quán)值 y結(jié)點的權(quán)值 則y i 具體實現(xiàn)如下 void Huffman SelectMin int for i s i e i if HTree i parent 1 x y i break 找出第一個有效權(quán)值x 并令y x for i e i if HTree i parent 1 該權(quán)值未使用過 if HTree i weight HTree x weight y x x i 迭代 依次找出前兩個最小值 else if x y HTree i weight HTree y weight y i 找出第2個有效權(quán)值y 特別說明 本例中葉子節(jié)點數(shù)n作為成員變量 因此 huffman類的成員函數(shù)的參數(shù)中 不必在添加int n這個參數(shù) 直接使用n即可 步步驟驟3 打打印印Huffman樹樹 Huffman樹的直觀表示方式由多種 我們常見的樹狀結(jié)構(gòu)如圖所示是其中的一種 此外 還有如圖a所示的嵌套集合表示法 如圖b所示的廣義表表示法和圖c所示的凹入表示法 A 圖 7樹型表示法 圖 8其他表示法 樹型表示法當結(jié)點很多的時候 不容易打印的非常合適 所以我們可以選擇使用凹入表 的方式打印任意形狀的Huffman樹 根結(jié)點空一格直接打印 第2層結(jié)點空2格打印 第3 層結(jié)點空3格的打印 以此類推 每個節(jié)點占用獨立的一行 由于只有葉子結(jié)點是有對應(yīng)字 符的 所以其他結(jié)點可以打印該結(jié)點的權(quán)值 因此 我們可以嘗試使用二叉樹前序遍歷的方 式來進行直觀的打印 示例代碼如下 define N 10 定義樹的最大深度 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樹的下標為i的結(jié)點 m表示該結(jié)點的層次 該函數(shù)是遞歸 函數(shù) 所以在main 函數(shù)中第一次調(diào)用該函數(shù)時 實參為i 2 n 2 m 1 步步驟驟4 創(chuàng)創(chuàng)建建編編碼碼表表 該步驟請參考教材5 4 2小節(jié)中的講解和實現(xiàn)即可 步步驟驟5 編編碼碼 編碼表生成后 進行編碼相對容易 實驗要求只要能夠顯示出來編碼后的字符串即可 也就 是說 若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 上述代碼用于本實驗的編碼顯示和驗證是沒問題的 但并沒有實現(xiàn)真正的壓縮效果 這時因 為代碼 的實現(xiàn) 比如若A的編碼為100 實際壓縮中使用3個bit代替字符A 本例中使 用了 3個字符 100 來編碼 因此沒有真正的壓縮效果 如果希望能夠按照bit的方式進 行編碼 需要使用位運算符進行bit的操作 將編碼按照bit的方式寫入文件 請同學(xué)們自行思考 如何采用bit的方式使用Huffman編碼壓縮文件 步步驟驟6 解解碼碼 該步驟請參考教材5 4 2小節(jié)中的講解和實現(xiàn)即可 步步驟驟7 測測試試 根據(jù)測試數(shù)據(jù) 編寫如下的測試man 函數(shù)進行測試 void main Huffman HFCode cout 請輸入要編碼的字符串 HFCode init cout 創(chuàng)建 Huffman 樹 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ù)據(jù)結(jié)構(gòu)HTree和 HCodeTable都是動態(tài)內(nèi)存 因此必須要在Huffman樹的析構(gòu)函數(shù)中進行內(nèi)存清理 示例代 碼如下 Huffman Huffman delete HTree delete HCodeTable 本實驗的運行效果如圖所示 圖2 9運行測試結(jié)果 根據(jù)要求 我們下面討論一下Huffman編碼的壓縮效果 數(shù)據(jù)壓縮比 英文名稱 data compression ratio 為衡量數(shù)據(jù)壓縮器壓縮效率的質(zhì)量指標 是指數(shù)據(jù)被壓縮的比例 其計 算公式如下 壓縮比 壓縮前字節(jié)數(shù) 壓縮后字節(jié)數(shù) 本實驗為了方便顯示和驗證算法 采用的是字符串方式進行壓縮