用哈夫曼編碼實(shí)現(xiàn)文件壓縮課案

1、用哈夫曼編碼實(shí)現(xiàn)文件壓縮實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)學(xué)期 2013 至 2014 學(xué)年第 2學(xué)期學(xué)生所在系部計(jì)算機(jī)學(xué)院年級 2012 級專業(yè)班級 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)生姓名 學(xué)號任課教師實(shí)驗(yàn)成績一、實(shí)驗(yàn)題目哈夫曼編碼實(shí)現(xiàn)文件壓縮二、實(shí)驗(yàn)?zāi)康模?、了解文件的概念。2、掌握線性鏈表的插入、刪除等算法。3、掌握 Huffman 樹的概念及構(gòu)造方法。4、掌握二叉樹的存儲(chǔ)結(jié)構(gòu)及遍歷算法。5、利用 Huffman 樹及 Huffman 編碼，掌握實(shí)現(xiàn)文件壓縮的一般原理。三、實(shí)驗(yàn)設(shè)備與環(huán)境：微型計(jì)算機(jī)、 Windows 系列操作系統(tǒng)、 Visual C+6.0 軟件。四、實(shí)驗(yàn)內(nèi)容：根據(jù) ASCII 碼文件中各

2、 ASCII 字符出現(xiàn)的頻率情況創(chuàng)建 Haffman 樹，再將各字 符對應(yīng)的哈夫曼編碼寫入文件中，實(shí)現(xiàn)文件壓縮。五、概要設(shè)計(jì)：本次實(shí)驗(yàn)采用將字符用長度盡可能短的二進(jìn)制數(shù)位表示的方法， 即對于文件中 出現(xiàn)的字符，無須全部都用 8位的 ASCII 碼進(jìn)行存儲(chǔ)，根據(jù)他們在文件中出現(xiàn)的 頻率不同，我們利用 Haffman 算法使每個(gè)字符能以最短的二進(jìn)制字符進(jìn)行存儲(chǔ)， 以達(dá)到節(jié)省存儲(chǔ)空間， 壓縮文件的目的。 解決了壓縮需采用的算法， 程序的思路 已然清晰：1統(tǒng)計(jì)需壓縮文件中每個(gè)字符出現(xiàn)的頻率。2將每個(gè)字符的出現(xiàn)頻率作為葉子結(jié)點(diǎn)構(gòu)建 Haffman 樹，然后將樹中結(jié)點(diǎn)引 向其左孩子的分支標(biāo)“ 0”，引向其

3、右孩子的分支標(biāo)“ 1”；每個(gè)字符的編碼即為從 根到每個(gè)葉子的路徑上得到的 0、 1 序列，這樣便完成了 Haffman 編碼，將每個(gè) 字符用最短的二進(jìn)制字符表示。3打開需壓縮文件，再將需壓縮文件中的每個(gè) ASCII 碼對應(yīng)的 Haffman 編碼 按 bit 單位輸出。4文件壓縮結(jié)束。六、詳細(xì)設(shè)計(jì)：（ 1）構(gòu)造 Hufffman 樹的方法 Hafffman 算法構(gòu)造 Huffman 樹步驟：I. 根據(jù)給定的 n 個(gè)權(quán)值 w1,w2, ? wn，構(gòu)造 n 棵只有根結(jié)點(diǎn)的二叉樹， 令起權(quán)值為 wj 。II. 在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的 二叉樹，置新二叉樹根結(jié)點(diǎn)權(quán)值為

4、其左右子樹根結(jié)點(diǎn)權(quán)值之和。III. 在森林中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入森林中。 . 重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹。對于 Haffman 的創(chuàng)建算法，有以下幾點(diǎn)說明：a) 這里的 Haffman 樹采用的是基于數(shù)組的帶左右兒子結(jié)點(diǎn)及父結(jié)點(diǎn)下標(biāo)作為 存儲(chǔ)結(jié)點(diǎn)的二叉樹形式，這種空間上的消耗帶來了算法實(shí)現(xiàn)上的便捷。b) 由于對于最后生成的 Haffman 樹，其所有葉子結(jié)點(diǎn)均為從一個(gè)內(nèi)部樹擴(kuò)充 出去的，所以，當(dāng)外部葉子結(jié)點(diǎn)數(shù)為 m個(gè)時(shí)，內(nèi)部結(jié)點(diǎn)數(shù)為 m-1，整個(gè) Haffman 樹的需要的結(jié)點(diǎn)數(shù)為 2m-1c) 初始化 Hafffman 樹分兩步進(jìn)行， 先將所有結(jié)點(diǎn)賦

5、值， 再將前 m個(gè)葉子結(jié)點(diǎn) 賦初值。d) 在查找權(quán)值最小并且父結(jié)點(diǎn)為空的兩個(gè)結(jié)點(diǎn)時(shí)，通過逐個(gè)比較，將兩結(jié)點(diǎn) 的位置下標(biāo)與權(quán)值分別保存。方便在與其父結(jié)點(diǎn)建立聯(lián)系時(shí)調(diào)用。2)壓縮過程的實(shí)現(xiàn)： 壓縮過程的流程是清晰而簡單的： 1創(chuàng)建 Haffman樹 2打開需壓縮文件 3將需壓縮文件中的每個(gè) ASCII 碼對應(yīng) 的 Haffman 編碼按 bit 單位輸出 4 文件壓縮結(jié)束。 其中，步驟 1和步驟 3是壓縮過程的關(guān)鍵。a) 步驟 1: 這里所要做工作是得到 Haffman 數(shù)中各葉子結(jié)點(diǎn)字符出現(xiàn)的頻率并進(jìn) 行創(chuàng)建。b) 步驟 3: 將需壓縮文件中的每個(gè) ASCII 碼對應(yīng)的 Haffman 編碼按

6、bit 單位輸 出，這是本壓縮程序中最關(guān)鍵的部分。 這里涉及“轉(zhuǎn)換”和“輸出”兩個(gè)關(guān)鍵步驟：“轉(zhuǎn)換”部分大可不必去通過遍歷 Haffman 樹來找到每個(gè)字符對應(yīng)的哈夫曼編 碼，可以將每個(gè)碼值及其對應(yīng)的 ASCII 碼存放于如下所示的結(jié)構(gòu)體中： typedef structchar asciiCode;unsigned long haffCode;int haffCodeLen;HaffCode; 創(chuàng)建由該結(jié)構(gòu)體結(jié)點(diǎn)所組成的，長度為 128 的一維數(shù)組 codeList128 ， 且 codeList 中的下標(biāo)和 asciiCode 滿足下面的順序存放關(guān)系：codeListi.asciiCode

7、=i;這樣的話，查找某個(gè)字符 inChar 的 Haffman編碼的工作便變得相當(dāng)輕松了 , 如下： sHaffCode=codeListinChar.haffCode;數(shù)組 codeList128 的創(chuàng)建可以采用某種遍歷方式下的按找到的字符進(jìn)行置數(shù) 的方式，十分的方便。以下流程圖采用的是前序遍歷的方式創(chuàng)建：說明：1 在流程圖中， youBiao 中存放字符對應(yīng)的 Haffman 編碼， sDepth 中存放其 Haffman 編碼的長度。2 在代碼的編寫過程中，可用遞歸調(diào)用實(shí)現(xiàn)。（3）“輸出”部分是最重要的部分，也是最易出錯(cuò)的部分。每個(gè)字符要能合 理的結(jié)束。這主要是為解壓縮考慮的，比如在最后

8、 ,這里涉及到 C語言的位操作 , 要求這個(gè)算法能處理好以下幾個(gè)問題：1）每個(gè)字符所對應(yīng)的 haffCode 的比特位長度由 523位不等長，不可少輸， 多輸，輸錯(cuò)任何一位，后一個(gè)字符的 haffCode 要緊跟在前一個(gè)字符的 haffCode 后面。2) 最后一個(gè)要輸出的 haffCode 的最后一位，它恰好是位于最后一個(gè)有效字符 的第一位，剩下的七個(gè)空位是要用無效的 haffCode加以填充的。 否則，如果填充 的haffCode亦為某個(gè) ascii 字符的haffCode 時(shí)，那么在解壓縮時(shí)，則該在原被壓 縮文件中不存在的字符便會(huì)無中生有的在解壓后的文件中出現(xiàn)， 這顯然是不正確 的，應(yīng)在

9、程序中加以處理。4)main 函數(shù)部分七、測試結(jié)果及分析：運(yùn)行結(jié)果：壓縮情況：實(shí)驗(yàn)分析：數(shù)據(jù)結(jié)構(gòu)將各個(gè)抽象的數(shù)據(jù)之間的關(guān)系建立起來， 無論是線性的、 循環(huán)的還 是分支的， 都是為了建立一種方便程序的實(shí)現(xiàn)和運(yùn)行的結(jié)構(gòu)， 使得數(shù)據(jù)之間不再 是孤立的。 它能使得我們在編程時(shí)在腦海中顯現(xiàn)更為清晰的數(shù)據(jù)關(guān)系畫面。 而且 在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)我們更應(yīng)該聯(lián)系所屬語言（我們所學(xué)的是 C 語言版）的特性， 這樣才能更好的理解數(shù)據(jù)結(jié)構(gòu)的思想體系。以上程序?qū)嶒?yàn)采用的方案：即統(tǒng)計(jì)了若干篇不同的文章中字符出現(xiàn)的頻率。 已事先統(tǒng)計(jì)每個(gè)字符出現(xiàn)的頻率放在 KEY.txt 文件中，然后程序運(yùn)行時(shí)自動(dòng)將字 符的權(quán)讀出存放在一個(gè)以為

10、數(shù)組中即 : wListi 中, 通過實(shí)參傳給形參 *w, 以此 按先序遍歷二叉樹的方式構(gòu)造 Huffman 樹，得各字符的 Huffman 編碼值. 在進(jìn)行 壓縮時(shí)候 , 程序界面會(huì)自動(dòng)提醒輸入要壓縮的文件名其壓縮的文件擴(kuò)展名為 *.zip. 每個(gè)字符的存儲(chǔ)編碼與 Huffman 編碼一一對應(yīng)，可以達(dá)到無損壓縮的目的 由于 KEY.txt 文件 的存在可以為后續(xù)解壓做準(zhǔn)備。總的來說，這次實(shí)驗(yàn)帶來的收獲是很大的，提取文件數(shù)據(jù)、分析數(shù)據(jù)、構(gòu)建 Huffman 樹、替換數(shù)據(jù)對文件進(jìn)行壓縮、輸出文件，一次大的實(shí)驗(yàn)幾乎運(yùn)用到了 我們一學(xué)期所學(xué)的所有知識。 經(jīng)過分、 析調(diào)試和了解程序的代碼， 鞏固了上課學(xué) 習(xí)的知識。在這次試驗(yàn)中， 我感覺到了自己的不足之處，