VIP專享數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-Huffman編碼與文件壓縮

1、題目三課 程 設(shè) 計 報 告題目三題目：哈夫曼編碼與文件壓縮課程名稱： 數(shù)據(jù)結(jié)構(gòu)專業(yè)班級：計算機科學(xué)與技術(shù) 1003班學(xué) 號：姓 名： 魯辰指導(dǎo)教師：報告日期： 2012.09.26 計算機科學(xué)與技術(shù)學(xué)院目 錄1 任務(wù)書.32 緒言.42.1 課題背景 .42.2 課題研究的目的和意義 .42.3 國內(nèi)外概況 .42.4 課題的主要研究工作 .43 系統(tǒng)設(shè)計方案的研究 .53.1 系統(tǒng)的控制特點與性能要求 .53.2 系統(tǒng)實現(xiàn)的原理 .53.2.1 Huffman算法 .53.2.2 Huffman編碼 .53.2.3 壓縮過程 .53.2.4 解壓過程 .63.3 系統(tǒng)實現(xiàn)方案分析 .63.

2、3.1 實現(xiàn) Huffman 編碼及壓縮所需的變量 .63.3.2文件名處理 .73.3.3 實現(xiàn) Huffman 編碼及壓縮過程所需要的函數(shù) .73.3.4 實現(xiàn)解壓縮過程所需要的函數(shù) .83.3.5 輸入輸出 .84 基于 Huffman 編碼的文件壓縮程序的設(shè)計 .94.1 主模塊功能介紹 .95 系統(tǒng)的實現(xiàn) .105.1 目標(biāo)程序運行截圖 .105.2 測試及測試數(shù)據(jù)分析 .105.2.1 測試數(shù)據(jù) .105.2.2 測試數(shù)據(jù)分析 .116 總結(jié)與展望 .12參考文獻 .13附錄 英文縮寫詞 .142任務(wù)書哈夫曼編碼與文件壓縮Lempel-Ziv D:docoriginal.txt），

3、*.cod，哈夫曼樹也以文件形式保存，任務(wù)書哈夫曼編碼與文件壓縮Lempel-Ziv D:docoriginal.txt），*.cod，哈夫曼樹也以文件形式保存，題目三設(shè)計目的： 掌握二叉樹、哈夫曼樹的概念，性質(zhì)與存儲結(jié)構(gòu)，能夠利用哈夫曼算法實現(xiàn)哈夫曼編碼，并應(yīng)用于文件壓縮，從而提高學(xué)生綜合運用知識的技能與實踐能力。設(shè)計內(nèi)容： 分析與設(shè)計哈夫曼樹的存儲結(jié)構(gòu)，實現(xiàn)哈夫曼算法以及編碼與譯碼基本功能，并對任意文本文件利用哈夫曼編碼進行壓縮得到壓縮文件，然后進行解壓縮得到解壓文件。有興趣的同學(xué)可以查閱資料實現(xiàn)sliding window 壓縮方法，并與之比較。設(shè)計要求：（1）要求界面友好，輸入文本文件

4、可帶路徑（如：哈夫曼算法所得到的壓縮文件名為文件名為*.hfm。（2）顯示壓縮比、壓縮時間、解壓時間與對應(yīng)的編碼表。設(shè)計提示： 統(tǒng)計文本文件中各字符的頻度并作為權(quán)值生成哈夫曼樹，并利用哈夫曼樹進行二進制編碼。參考文獻：1 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)（ C語言版）. 北京: 清華大學(xué)出版社 ,19972 王曉東. 計算機算法設(shè)計與分析 . 北京: 電子工業(yè)出版社 , 20073 嚴(yán)蔚敏, 吳偉民, 米寧. 數(shù)據(jù)結(jié)構(gòu)題集（ C語言版）. 北京: 清華大學(xué)出版社,199932 緒言2.1 課題背景在計算機軟件應(yīng)用領(lǐng)域，文件壓縮是一項重要的技術(shù)。為了減少傳輸數(shù)據(jù)量或者減少存儲空間，都需要將大型文件壓

5、縮成較小的文件。2.2 課題研究的目的和意義Huffman 編碼具有速度快、簡單等優(yōu)點，是一種很好的壓縮方法。2.3 國內(nèi)外概況1952年，David A. Huffman 在麻省理工攻讀博士時所發(fā)明的，并發(fā)表于一種構(gòu)建極小多余編碼的方法（ A Method for the Construction of Minimum-Redundancy Codes）一文。2.4 課題的主要研究工作（1）通過查閱書籍并在網(wǎng)上查看相關(guān)論文，對 Huffman 編碼算法有一個清晰的認(rèn)識。（2） 使用 Microsoft Visual Studio 2010 實現(xiàn)基于 Huffman 編碼的文件壓縮程序。（3）

6、通過使用各種不同的測試文件對該程序進行測試，記錄并分析壓縮算法的壓縮比、壓縮時間等數(shù)據(jù)。（4）分析測試數(shù)據(jù)，并根據(jù)需要對代碼進行優(yōu)化。4MFC 生成的，Visual Studio 或者 MFC 類庫（？）。，? ?F中。?，其編碼長度為 ?=MFC 生成的，Visual Studio 或者 MFC 類庫（？）。，? ?F中。?，其編碼長度為 ?=?=n種字符出現(xiàn)的頻率做權(quán)，Huffman 編碼。txt 格式。Huffman 樹，得到各個字Huffman 編碼，并將相應(yīng)的構(gòu)成 n棵二叉樹的集合 F=?1,?2, ，的根結(jié)點，其左右子樹為空。，電文中只有 n種?1?1，?。對應(yīng)到二叉樹上，若置?恰

7、為二叉樹上的帶權(quán)路徑長度。由?為葉子結(jié)點的權(quán)， 恰?3.1 系統(tǒng)的控制特點與性能要求本系統(tǒng)是使用 VS2010開發(fā)的 MFC 應(yīng)用程序，對話框是使用而對文件讀寫操作以及 Huffman 編碼的算法部分是用 C語言實現(xiàn)的。本系統(tǒng)的特點是圖形界面，使用簡單，便于操控。本系統(tǒng)不要求使用者安裝3.2 系統(tǒng)實現(xiàn)的原理3.2.1 Huffman 算法（1）根據(jù)給定的 n個權(quán)值?1,?2,其中每棵二叉樹 中只有一個帶權(quán)為（2）在 F中選取兩棵根結(jié)點權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和。（3）在 F中刪除這兩棵樹，同時將新達到的二叉樹加入（4）

8、重復(fù)（ 2）和（3），直到 F只含一棵樹為止。3.2.2 Huffman 編碼假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為字符，則電文總長為為從根到葉子結(jié)點的路徑長度，則此可見，設(shè)計電文總長最短的二進制前綴編碼即為以設(shè)計一棵 Huffman 樹的問題，由此得到的二進制前綴編碼即為3.2.3 壓縮過程前提：與輸入的路徑對應(yīng)的文件為（1）構(gòu)造 Huffman 樹：算法如 3.2.1所示。（2）將 Huffman 樹編碼：初始化編碼數(shù)組，并遍歷符的編碼，并保存為 .hfm文件。（3）將.txt 文件中的內(nèi)容讀取出來，找到對應(yīng)的5txt 格式，且輸入的路徑對應(yīng)的.txt 文件。聲明語句 or類型typedefst

9、ruc Huffman_NodeHuffman_Node intHuffman_Node unsigned碼unsigned個新的txt 格式，且輸入的路徑對應(yīng)的.txt 文件。聲明語句 or類型typedefstruc Huffman_NodeHuffman_Node intHuffman_Node unsigned碼unsigned個新的 Huffman 編碼時，作xxx.cod 文件功能Huffman 樹的結(jié)點存儲每個字符在文本文件中指向生成的 Huffman 樹int 用于存儲生成的 Huffman 編int 當(dāng)遍歷 Huffman 樹為求得一3.2.4 解壓過程前提：與輸入的路徑對應(yīng)

10、的文件為有對應(yīng)的 Huffman 編碼文件 xxx.hfm 存在。（1）由.hfm文件載入 Huffman 編碼的數(shù)組。（2）讀取.cod文件的內(nèi)容，并找到其對應(yīng)的字符寫入新的3.3 系統(tǒng)實現(xiàn)方案分析3.3.1 實現(xiàn) Huffman 編碼及壓縮所需的變量表3. 1實現(xiàn) Huffman 編碼所需變量列表（均為全局變量）名稱Huffman_Nodeunsigned char char_value; /字符的值doubl char_weight/權(quán)值struct*leftchild,*rightchild,*parent;Huffman_Node;app_times256出現(xiàn)的次數(shù)*my_Huffm

11、an_Tree*my_Huffman_Tree=NULL;h_codeh_code256MaxCodeLengthtemp_codetemp_codeMaxCodeLength;為臨時存儲 Huffman 編碼用6txt 格式的文本3.2.4所述規(guī)定的 cod格式的文件。功能aa=1（進行解壓縮）用于存儲輸入的待壓縮的文件的路將 filename的最后四個字符被改為 .txt 格式的文本3.2.4所述規(guī)定的 cod格式的文件。功能aa=1（進行解壓縮）用于存儲輸入的待壓縮的文件的路將 filename的最后四個字符被改為 .路徑將 filename的最后四個字符被改為 .為.hfm后的文件名，

12、以備讀入Huffman 樹文件，修改的前提是該無任何作用函數(shù)聲明void count_timesvoid)void CreateHuffTreevoid)無任何作用用于存儲輸入的待解壓的文件的將 filename1的最后四個字符被改將 filename1的最后五個字符被改功能打開 txt 文本文件，并對各字符的出構(gòu)造 Huffman 樹，先將 app_times（1）輸入文件名稱的合法性文件名稱合法性的識別，即當(dāng)選擇待壓縮文件時，只能選擇文件；當(dāng)選擇待解壓文件時，只能選擇符合（2）文件路徑的初始化表3. 2 文件名變量名aa=0（進行壓縮）filename徑filename1cod后的文件名，

13、以備寫入壓縮后的文件內(nèi)容filename2hfm 后的文件名，以備寫入 Huffman樹文件文件存在。filename3為 u.txt 后的文件名，以備寫入解壓縮后的文件內(nèi)容3.3.3 實現(xiàn) Huffman 編碼及壓縮過程所需要的函數(shù)表 3. 3 實現(xiàn)壓縮所需函數(shù)列表調(diào)用順序（1）現(xiàn)次數(shù)進行統(tǒng)計，寫入 app_times中（2）中的內(nèi)容，分別寫入各個 Huffman樹結(jié)點權(quán)值和字符值，然后用Huffman 算法構(gòu)造 Huffman 樹7void InitCode(void)void碼，并將單次循環(huán)求出的 Huffman將 void InitCode(void)void碼，并將單次循環(huán)求出的 H

14、uffman將 temp_code賦值給 h_code的 numvoid CompressionFilevoid)CreateHuffTree函數(shù)，構(gòu)造初始化 Huffman 編碼，將 h_code的FindCode(Huffman_Node 通過遍歷 Huffman 樹求 Huffman 編讀入 filename路徑對應(yīng)文件的字符，值均置為 -1（4）*pNode)編碼存放在 temp_code中。遍歷結(jié)束后，調(diào)用函數(shù) CopyCode將temp_code賦值給 h_code的相應(yīng)位置。void CopyCodeint num)行（5）并將其轉(zhuǎn)化為 Huffman 編碼寫入filename1

15、路徑對應(yīng)的文件內(nèi)。將數(shù)組 app_times的內(nèi)容存入 filename2路徑對應(yīng)的文件內(nèi)，以便解壓縮時構(gòu)造 Huffman 樹。3.3.4 實現(xiàn)解壓縮過程所需要的函數(shù)void DeCompressionFilevoid)先從 filename2路徑對應(yīng)的文件中讀出，再調(diào)用Huffman 樹，再根據(jù) filename1路徑的.cod文件，讀出編碼，并根據(jù)編碼遍歷Huffman 樹，直到遇到葉子結(jié)點，將該葉子結(jié)點的字符的值寫入對應(yīng)路徑filename3的txt 文件中，再讀入下一個 Huffman 編碼，直到 filename1的文件結(jié)尾。3.3.5 輸入輸出輸入：（1） 待壓縮文件的路徑（2）

16、 待解壓文件的路徑輸出：（1） 錯誤信息（2） 在輸入的文件的路徑下建立的壓縮后或解壓縮后的文件89“選擇待解壓文件 ”“開始”彈出“打開”對話框0路徑合法？是aa=0彈出錯誤信息1壓縮是aa=1文件”等待用戶選擇解壓彈出錯誤信息“請選擇 cod“選擇待解壓文件 ”“開始”彈出“打開”對話框0路徑合法？是aa=0彈出錯誤信息1壓縮是aa=1文件”等待用戶選擇解壓彈出錯誤信息“請選擇 cod否路徑合法？4.1 主模塊功能介紹當(dāng)用戶點擊界面上的按鈕后，會對當(dāng)前情況作出判斷。如果輸入不符合要求，則彈出錯誤信息要求重新輸入。當(dāng)且僅當(dāng)選擇了符合要求的擴展名的文件后，才能夠點擊開始按鈕進行壓縮或者解壓。如

17、圖所示。開始初始化 aa，app_times等“選擇待壓縮文件 ”單擊按鈕彈出“打開”對話框等待用戶選擇aa=？否彈出錯誤信息“請選擇 txt文本文件 ”“請選擇文件 ”結(jié)束圖 4. 1 主程序程序框圖101中文/非中文字?jǐn)?shù)解壓中文5187294116035827283527566263470405120文件名直接使用打開按鈕即可選取txt 大小/B285387713351421中文/非中文字?jǐn)?shù)解壓中文5187294116035827283527566263470405120文件名直接使用打開按鈕即可選取txt 大小/B2853877133514200514075cod大小/B38891534

18、3070163733773937077421735324237828531壓縮比246812703642156570002244724240836182416634508耗時/ms0.63461 50.827974 440.600829 200.77681 230.57015 9630.57106 1330.562601 1060.765823 214333141664172551615.1 目標(biāo)程序運行截圖圖 4. 2 程序運行截圖5.2 測試及測試數(shù)據(jù)分析5.2.1 測試數(shù)據(jù)表5. 1 測試數(shù)據(jù)文件名壓縮非中文test0.txttest1.txttest2.txttest3.txttest

19、4.txttest5.txttest6.txttest7.txt111壓縮比中文字符所占比例1 1 1 73 0 128 995壓縮比中文字符所占比例1 1 1 73 0 128 995 111 080.0is1008 17 42 34 38708 7壓縮時長ms解壓時長ms5631 35 37 30 7 6 8733 7010 2 8 91 287 3 946 84 00（1）中文字符對壓縮比的影響：當(dāng)中文字符占總字符的比例增加時，壓縮比也會增加。說明 Huffman 編碼在壓縮中文字符時，效果不如英文字符明顯。如圖所示。壓縮比0.90.80.70.60.50.40.30.20.1043 4

20、9 05 578 8 5 0 0 00.9 0.8 0.0 0 0.0 0.0圖5. 1 壓縮比與中文字符所占比例的關(guān)系（2）文件大小與壓縮、解壓時間的關(guān)系：很明顯，當(dāng)被壓縮、解壓的文件越大，壓縮、解壓消耗的時間越長。且文件大小與操作耗時基本成線性關(guān)系。250200el 150TitAx50文件大小 B082 42 32 15圖5. 2文件大小與壓縮、解壓時間的關(guān)系126 總結(jié)與展望通過設(shè)計并編寫基于 Huffman 的文本文件壓縮程序，我獲益良多。首先，由于界面是使用 Visual Studio 2010 制作 MFC 應(yīng)用程序?qū)崿F(xiàn)的，所以，我在編寫代碼的過程中對 MFC 編程和 Windows 程序設(shè)計加深了了解。其次，通過實現(xiàn) Huffman 編碼及文件壓縮，我對 Huffman 算法及 Huffman編碼都有了深入的理解，對二叉樹也加深了認(rèn)識。還有，在調(diào)試的過程中，遇到了一些問題。通過解決這些問題，提高了我發(fā)現(xiàn)并解決問題的能力。雖然在本次的課設(shè)中我成功實現(xiàn)了 Huffman 編碼與文件壓縮