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

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

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

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

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

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

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

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

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

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

10、的文件為有對(duì)應(yīng)的 Huffman 編碼文件 xxx.hfm 存在。（1）由.hfm文件載入 Huffman 編碼的數(shù)組。（2）讀取.cod文件的內(nèi)容，并找到其對(duì)應(yīng)的字符寫入新的3.3 系統(tǒng)實(shí)現(xiàn)方案分析3.3.1 實(shí)現(xiàn) Huffman 編碼及壓縮所需的變量表3. 1實(shí)現(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;為臨時(shí)存儲(chǔ) Huffman 編碼用6txt 格式的文本3.2.4所述規(guī)定的 cod格式的文件。功能aa=1（進(jìn)行解壓縮）用于存儲(chǔ)輸入的待壓縮的文件的路將 filename的最后四個(gè)字符被改為 .txt 格式的文本3.2.4所述規(guī)定的 cod格式的文件。功能aa=1（進(jìn)行解壓縮）用于存儲(chǔ)輸入的待壓縮的文件的路將 filename的最后四個(gè)字符被改為 .路徑將 filename的最后四個(gè)字符被改為 .為.hfm后的文件名，

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

13、以備寫入壓縮后的文件內(nèi)容filename2hfm 后的文件名，以備寫入 Huffman樹文件文件存在。filename3為 u.txt 后的文件名，以備寫入解壓縮后的文件內(nèi)容3.3.3 實(shí)現(xiàn) Huffman 編碼及壓縮過程所需要的函數(shù)表 3. 3 實(shí)現(xiàn)壓縮所需函數(shù)列表調(diào)用順序（1）現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì)，寫入 app_times中（2）中的內(nèi)容，分別寫入各個(gè) Huffman樹結(jié)點(diǎn)權(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路徑對(duì)應(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、路徑對(duì)應(yīng)的文件內(nèi)。將數(shù)組 app_times的內(nèi)容存入 filename2路徑對(duì)應(yīng)的文件內(nèi)，以便解壓縮時(shí)構(gòu)造 Huffman 樹。3.3.4 實(shí)現(xiàn)解壓縮過程所需要的函數(shù)void DeCompressionFilevoid)先從 filename2路徑對(duì)應(yīng)的文件中讀出，再調(diào)用Huffman 樹，再根據(jù) filename1路徑的.cod文件，讀出編碼，并根據(jù)編碼遍歷Huffman 樹，直到遇到葉子結(jié)點(diǎn)，將該葉子結(jié)點(diǎn)的字符的值寫入對(duì)應(yīng)路徑filename3的txt 文件中，再讀入下一個(gè) Huffman 編碼，直到 filename1的文件結(jié)尾。3.3.5 輸入輸出輸入：（1） 待壓縮文件的路徑（2）

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

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

18、3070163733773937077421735324237828531壓縮比246812703642156570002244724240836182416634508耗時(shí)/ms0.63461 50.827974 440.600829 200.77681 230.57015 9630.57106 1330.562601 1060.765823 214333141664172551615.1 目標(biāo)程序運(yùn)行截圖圖 4. 2 程序運(yùn)行截圖5.2 測(cè)試及測(cè)試數(shù)據(jù)分析5.2.1 測(cè)試數(shù)據(jù)表5. 1 測(cè)試數(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壓縮時(shí)長(zhǎng)ms解壓時(shí)長(zhǎng)ms5631 35 37 30 7 6 8733 7010 2 8 91 287 3 946 84 00（1）中文字符對(duì)壓縮比的影響：當(dāng)中文字符占總字符的比例增加時(shí)，壓縮比也會(huì)增加。說明 Huffman 編碼在壓縮中文字符時(shí)，效果不如英文字符明顯。如圖所示。壓縮比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）文件大小與壓縮、解壓時(shí)間的關(guān)系：很明顯，當(dāng)被壓縮、解壓的文件越大，壓縮、解壓消耗的時(shí)間越長(zhǎng)。且文件大小與操作耗時(shí)基本成線性關(guān)系。250200el 150TitAx50文件大小 B082 42 32 15圖5. 2文件大小與壓縮、解壓時(shí)間的關(guān)系126 總結(jié)與展望通過設(shè)計(jì)并編寫基于 Huffman 的文本文件壓縮程序，我獲益良多。首先，由于界面是使用 Visual Studio 2010 制作 MFC 應(yīng)用程序?qū)崿F(xiàn)的，所以，我在編寫代碼的過程中對(duì) MFC 編程和 Windows 程序設(shè)計(jì)加深了了解。其次，通過實(shí)現(xiàn) Huffman 編碼及文件壓縮，我對(duì) Huffman 算法及 Huffman編碼都有了深入的理解，對(duì)二叉樹也加深了認(rèn)識(shí)。還有，在調(diào)試的過程中，遇到了一些問題。通過解決這些問題，提高了我發(fā)現(xiàn)并解決問題的能力。雖然在本次的課設(shè)中我成功實(shí)現(xiàn)了 Huffman 編碼與文件壓縮