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

1、<p>　　課 程 設(shè) 計(jì) 報(bào) 告</p><p>　　題目： 題目三 </p><p>　　哈夫曼編碼與文件壓縮 </p><p>　　課程名稱： 數(shù)據(jù)結(jié)構(gòu) </p><p>　　專業(yè)班級：計(jì)算機(jī)科學(xué)與技術(shù)1003班 </p><

2、p>　　學(xué) 號： </p><p>　　姓 名： </p><p>　　指導(dǎo)教師： </p><p>　　報(bào)告日期： </p><p>　　計(jì)算機(jī)科學(xué)與技術(shù)學(xué)

3、院</p><p><b>　　任務(wù)書</b></p><p>　　題目三 哈夫曼編碼與文件壓縮</p><p>　　設(shè)計(jì)目的：掌握二叉樹、哈夫曼樹的概念，性質(zhì)與存儲結(jié)構(gòu)，能夠利用哈夫曼算法實(shí)現(xiàn)哈夫曼編碼，并應(yīng)用于文件壓縮，從而提高學(xué)生綜合運(yùn)用知識的技能與實(shí)踐能力。</p><p>　　設(shè)計(jì)內(nèi)容：分析與設(shè)計(jì)哈夫曼樹的存

4、儲結(jié)構(gòu)，實(shí)現(xiàn)哈夫曼算法以及編碼與譯碼基本功能，并對任意文本文件利用哈夫曼編碼進(jìn)行壓縮得到壓縮文件，然后進(jìn)行解壓縮得到解壓文件。有興趣的同學(xué)可以查閱資料實(shí)現(xiàn)Lempel-Ziv sliding window壓縮方法，并與之比較。</p><p><b>　　設(shè)計(jì)要求：</b></p><p>　?。?）要求界面友好，輸入文本文件可帶路徑（如：D:\doc\origina

5、l.txt），哈夫曼算法所得到的壓縮文件名為*.cod，哈夫曼樹也以文件形式保存，文件名為*.hfm。</p><p>　?。?）顯示壓縮比、壓縮時(shí)間、解壓時(shí)間與對應(yīng)的編碼表。</p><p>　　設(shè)計(jì)提示：統(tǒng)計(jì)文本文件中各字符的頻度并作為權(quán)值生成哈夫曼樹，并利用哈夫曼樹進(jìn)行二進(jìn)制編碼。 </p><p><b>　　參考文獻(xiàn)：</b>&l

6、t;/p><p>　　[1] 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）. 北京: 清華大學(xué)出版社,1997</p><p>　　[2] 王曉東. 計(jì)算機(jī)算法設(shè)計(jì)與分析. 北京: 電子工業(yè)出版社, 2007</p><p>　　[3] 嚴(yán)蔚敏, 吳偉民, 米寧. 數(shù)據(jù)結(jié)構(gòu)題集（C語言版）. 北京: 清華大學(xué)出版社,1999</p><p><

7、b>　　2 緒言</b></p><p><b>　　2.1 課題背景</b></p><p>　　在計(jì)算機(jī)軟件應(yīng)用領(lǐng)域，文件壓縮是一項(xiàng)重要的技術(shù)。為了減少傳輸數(shù)據(jù)量或者減少存儲空間，都需要將大型文件壓縮成較小的文件。</p><p>　　2.2 課題研究的目的和意義</p><p>　　Huffma

8、n編碼具有速度快、簡單等優(yōu)點(diǎn)，是一種很好的壓縮方法。</p><p><b>　　2.3 國內(nèi)外概況</b></p><p>　　1952年，David A. Huffman在麻省理工攻讀博士時(shí)所發(fā)明的，并發(fā)表于《一種構(gòu)建極小多余編碼的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。&l

9、t;/p><p>　　2.4 課題的主要研究工作</p><p>　?。?）通過查閱書籍并在網(wǎng)上查看相關(guān)論文，對Huffman編碼算法有一個(gè)清晰的認(rèn)識。</p><p>　?。?） 使用 Microsoft Visual Studio 2010 實(shí)現(xiàn)基于Huffman編碼的文件壓縮程序。</p><p>　?。?）通過使用各種不同的測試文件對該程

10、序進(jìn)行測試，記錄并分析壓縮算法的壓縮比、壓縮時(shí)間等數(shù)據(jù)。</p><p>　?。?）分析測試數(shù)據(jù)，并根據(jù)需要對代碼進(jìn)行優(yōu)化。</p><p>　　3 系統(tǒng)設(shè)計(jì)方案的研究</p><p>　　3.1 系統(tǒng)的控制特點(diǎn)與性能要求</p><p>　　本系統(tǒng)是使用VS2010開發(fā)的MFC應(yīng)用程序，對話框是使用MFC生成的，而對文件讀寫操作以及Huf

11、fman編碼的算法部分是用C語言實(shí)現(xiàn)的。</p><p>　　本系統(tǒng)的特點(diǎn)是圖形界面，使用簡單，便于操控。</p><p>　　本系統(tǒng)不要求使用者安裝Visual Studio 或者 MFC類庫（？）。</p><p>　　3.2 系統(tǒng)實(shí)現(xiàn)的原理</p><p>　　3.2.1 Huffman算法</p><p>　　

12、（1）根據(jù)給定的n個(gè)權(quán)值{}構(gòu)成n棵二叉樹的集合F={}，其中每棵二叉樹中只有一個(gè)帶權(quán)為的根結(jié)點(diǎn)，其左右子樹為空。</p><p>　?。?）在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和。</p><p>　　（3）在F中刪除這兩棵樹，同時(shí)將新達(dá)到的二叉樹加入F中。</p><p>　?。?/p>

13、4）重復(fù)（2）和（3），直到F只含一棵樹為止。</p><p>　　3.2.2 Huffman編碼</p><p>　　假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為，其編碼長度為，電文中只有n種字符，則電文總長為。對應(yīng)到二叉樹上，若置為葉子結(jié)點(diǎn)的權(quán)，恰為從根到葉子結(jié)點(diǎn)的路徑長度，則恰為二叉樹上的帶權(quán)路徑長度。由此可見，設(shè)計(jì)電文總長最短的二進(jìn)制前綴編碼即為以n種字符出現(xiàn)的頻率做權(quán)，設(shè)計(jì)一棵Huffman

14、樹的問題，由此得到的二進(jìn)制前綴編碼即為Huffman編碼。</p><p>　　3.2.3 壓縮過程</p><p>　　前提：與輸入的路徑對應(yīng)的文件為txt格式。</p><p>　?。?）構(gòu)造Huffman樹：算法如3.2.1所示。</p><p>　?。?）將Huffman樹編碼：初始化編碼數(shù)組，并遍歷Huffman樹，得到各個(gè)字符的編

15、碼，并保存為.hfm文件。</p><p>　　（3）將.txt文件中的內(nèi)容讀取出來，找到對應(yīng)的Huffman編碼，并將相應(yīng)的Huffman編碼寫入.cod文件中。</p><p>　　3.2.4 解壓過程</p><p>　　前提：與輸入的路徑對應(yīng)的文件為txt格式，且輸入的路徑對應(yīng)的xxx.cod文件有對應(yīng)的Huffman編碼文件xxx.hfm存在。</p

16、><p>　　（1）由.hfm文件載入Huffman編碼的數(shù)組。</p><p>　?。?）讀取.cod文件的內(nèi)容，并找到其對應(yīng)的字符寫入新的.txt文件。</p><p>　　3.3 系統(tǒng)實(shí)現(xiàn)方案分析</p><p>　　3.3.1 實(shí)現(xiàn)Huffman編碼及壓縮所需的變量</p><p>　　表3. 1實(shí)現(xiàn)Huffman

17、編碼所需變量列表（均為全局變量）</p><p>　　3.3.2文件名處理</p><p>　?。?）輸入文件名稱的合法性</p><p>　　文件名稱合法性的識別，即當(dāng)選擇待壓縮文件時(shí)，只能選擇txt格式的文本文件；當(dāng)選擇待解壓文件時(shí)，只能選擇符合3.2.4所述規(guī)定的cod格式的文件。</p><p>　　（2）文件路徑的初始化</p

18、><p><b>　　表3. 3 文件名</b></p><p>　　3.3.3 實(shí)現(xiàn)Huffman編碼及壓縮過程所需要的函數(shù)</p><p>　　表3. 2 實(shí)現(xiàn)壓縮所需函數(shù)列表</p><p>　　3.3.4 實(shí)現(xiàn)解壓縮過程所需要的函數(shù)</p><p>　　void DeCompressionFi

19、le(void)</p><p>　　先從filename2路徑對應(yīng)的文件中讀出，再調(diào)用CreateHuffTree函數(shù)，構(gòu)造Huffman樹，再根據(jù)filename1路徑的.cod文件，讀出編碼，并根據(jù)編碼遍歷Huffman樹，直到遇到葉子結(jié)點(diǎn)，將該葉子結(jié)點(diǎn)的字符的值寫入對應(yīng)路徑filename3的txt文件中，再讀入下一個(gè)Huffman編碼，直到filename1的文件結(jié)尾。</p><p

20、>　　3.3.5 輸入輸出</p><p><b>　　輸入：</b></p><p><b>　　待壓縮文件的路徑</b></p><p><b>　　待解壓文件的路徑</b></p><p><b>　　輸出：</b></p>&l

21、t;p><b>　　錯(cuò)誤信息</b></p><p>　　在輸入的文件的路徑下建立的壓縮后或解壓縮后的文件</p><p>　　4 基于Huffman編碼的文件壓縮程序的設(shè)計(jì)</p><p>　　4.1 主模塊功能介紹</p><p>　　當(dāng)用戶點(diǎn)擊界面上的按鈕后，會對當(dāng)前情況作出判斷。如果輸入不符合要求，則彈出

22、錯(cuò)誤信息要求重新輸入。當(dāng)且僅當(dāng)選擇了符合要求的擴(kuò)展名的文件后，才能夠點(diǎn)擊開始按鈕進(jìn)行壓縮或者解壓。如圖所示。</p><p><b>　　5 系統(tǒng)的實(shí)現(xiàn)</b></p><p>　　5.1 目標(biāo)程序運(yùn)行截圖</p><p>　　圖4. 2 程序運(yùn)行截圖</p><p>　　5.2 測試及測試數(shù)據(jù)分析</p>

23、<p>　　5.2.1 測試數(shù)據(jù)</p><p>　　表5. 1 測試數(shù)據(jù)</p><p>　　5.2.2 測試數(shù)據(jù)分析</p><p>　　（1）中文字符對壓縮比的影響：當(dāng)中文字符占總字符的比例增加時(shí)，壓縮比也會增加。說明Huffman編碼在壓縮中文字符時(shí)，效果不如英文字符明顯。如圖所示。</p><p>　　圖5. 1 壓縮

24、比與中文字符所占比例的關(guān)系</p><p>　?。?）文件大小與壓縮、解壓時(shí)間的關(guān)系：</p><p>　　很明顯，當(dāng)被壓縮、解壓的文件越大，壓縮、解壓消耗的時(shí)間越長。且文件大小與操作耗時(shí)基本成線性關(guān)系。</p><p>　　圖5. 2文件大小與壓縮、解壓時(shí)間的關(guān)系</p><p><b>　　6 總結(jié)與展望</b>&

25、lt;/p><p>　　通過設(shè)計(jì)并編寫基于Huffman的文本文件壓縮程序，我獲益良多。</p><p>　　首先，由于界面是使用Visual Studio 2010 制作MFC應(yīng)用程序?qū)崿F(xiàn)的，所以，我在編寫代碼的過程中對MFC編程和Windows程序設(shè)計(jì)加深了了解。</p><p>　　其次，通過實(shí)現(xiàn)Huffman編碼及文件壓縮，我對Huffman算法及Huffman

26、編碼都有了深入的理解，對二叉樹也加深了認(rèn)識。</p><p>　　還有，在調(diào)試的過程中，遇到了一些問題。通過解決這些問題，提高了我發(fā)現(xiàn)并解決問題的能力。</p><p>　　雖然在本次的課設(shè)中我成功實(shí)現(xiàn)了Huffman編碼與文件壓縮，但是仍然覺得任務(wù)書中提到的Lempel-Ziv、Sliding Window 壓縮算法實(shí)現(xiàn)起來較有難度。盡管，對上述兩種算法都查找了相關(guān)論文和例子程序，但是仍

27、沒能夠成功將其實(shí)現(xiàn)。不過，我一定會在以后的學(xué)習(xí)閑暇努力將上述兩種算法實(shí)現(xiàn)。</p><p>　　另外，對于提交的Huffman壓縮程序，也是有增加功能的空間的，只是時(shí)間有限，無法一一實(shí)現(xiàn)。比如，可以增加對壓縮比的分析功能，通過對多組不同文本文件的壓縮，對比文件大小與壓縮比、中文字符比例與壓縮比的關(guān)系，并使用最小二乘法將曲線擬合出來。還可以使用SHA1算法檢查文件的完整性，以檢驗(yàn)Huffman編碼的壓縮確實(shí)是無損壓

28、縮。</p><p>　　總之，我認(rèn)為現(xiàn)在的提交的這個(gè)程序還有很多可以改進(jìn)的地方，可以變得更加完善。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）. 北京: 清華大學(xué)出版社,1997</p><p>　　[2] 王曉東. 計(jì)算機(jī)算法設(shè)計(jì)與分析. 北京: