哈夫曼編碼的實現(xiàn)及應(yīng)用畢業(yè)論文

1、<p>　　畢 業(yè) 設(shè) 計（論文）</p><p>　　題目 哈夫曼編碼的實現(xiàn) </p><p>　　及應(yīng)用 </p><p>　　二級學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院 </p><p>　　專 業(yè) 信息與計算科學(xué) </p><p>　　

2、班 級 </p><p>　　學(xué)生姓名 學(xué)號 </p><p>　　指導(dǎo)教師 職稱 </p><p>　　時 間 </p><p><b>　

3、　目錄</b></p><p><b>　　摘要I</b></p><p>　　AbstractII</p><p><b>　　第一章 緒論1</b></p><p>　　1.1 研究目的及意義1</p><p>　　1.2 圖像壓縮編碼技術(shù)概述2&l

4、t;/p><p>　　1.2.1 圖像壓縮編碼技術(shù)分類2</p><p>　　1.2.2 圖像壓縮編碼評價2</p><p>　　1.3 哈夫曼編碼簡介3</p><p>　　1.4 本設(shè)計所做的主要工作4</p><p>　　第二章 利用靜態(tài)哈夫曼編碼實現(xiàn)圖像壓縮5</p><p>　　

5、2.1 靜態(tài)哈夫曼編碼介紹5</p><p>　　2.2 靜態(tài)哈夫曼編碼樹的構(gòu)造6</p><p>　　2.3 靜態(tài)哈夫曼編碼的具體編碼過程6</p><p>　　2.4 靜態(tài)哈夫曼編碼的算法實例7</p><p>　　2.3 利用靜態(tài)哈夫曼編碼壓縮與還原圖像的C語言實現(xiàn)9</p><p>　　2.3.1 壓

6、縮的實現(xiàn)9</p><p>　　2.3.2 解壓縮的實現(xiàn)11</p><p>　　2.4 圖象壓縮實例12</p><p>　　第三章 利用動態(tài)哈夫曼編碼實現(xiàn)圖像壓縮15</p><p>　　3.1 動態(tài)哈夫曼編碼的提出15</p><p>　　3.2 動態(tài)哈夫曼編碼的原理15</p><

7、;p>　　3.3 動態(tài)哈夫曼編碼的算法思想16</p><p>　　3.4 動態(tài)哈夫曼編碼的編碼實例18</p><p>　　3.5 利用動態(tài)哈夫曼編碼壓縮與還原圖像的C語言實現(xiàn)25</p><p>　　3.5.1 數(shù)據(jù)結(jié)構(gòu)25</p><p>　　3.5.2 壓縮的實現(xiàn)26</p><p>　　3.5

8、.3 解壓縮的實現(xiàn)27</p><p>　　3.6 圖像壓縮實例28</p><p>　　3.7 靜態(tài)哈夫曼編碼與動態(tài)哈夫曼編碼的比較29</p><p>　　第四章 對哈夫曼編碼的改進(jìn)31</p><p>　　4.1 在哈夫曼編碼中引入堆排序31</p><p>　　4.2 模擬哈夫曼樹的創(chuàng)建32<

9、/p><p><b>　　第五章 總結(jié)34</b></p><p><b>　　5.1 總結(jié)34</b></p><p><b>　　參考文獻(xiàn)35</b></p><p><b>　　附錄36</b></p><p><b

10、>　　摘要</b></p><p>　　哈夫曼編碼是一種以哈夫曼樹—即最優(yōu)二叉樹為核心的編碼方式，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。在計算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱"熵編碼法"），用于數(shù)據(jù)的無損壓縮。"熵編碼法"是指使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個符號）進(jìn)行編碼。這張編碼表的特殊之處在于，它是通過統(tǒng)計每一個源字符出現(xiàn)的概率建立起

11、來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這使得編碼之后的字符串的平均長度是最短的，從而達(dá)到無損壓縮數(shù)據(jù)的目的）。論文全面分析了靜態(tài)哈夫曼編碼和動態(tài)哈夫曼編碼算法算法，詳細(xì)介紹了靜態(tài)哈夫曼編碼樹和和動態(tài)哈夫曼編碼樹的構(gòu)造方案，并針對這兩種算法，給出了對應(yīng)的C 語言代碼。經(jīng)運行分析發(fā)現(xiàn)，由于在構(gòu)造靜態(tài)哈夫曼樹時，大量的時間消耗在從元素集合中選取兩個最小的元素上。而動態(tài)哈夫曼編碼算法，雖然克服了前者的缺點，但是

12、算法復(fù)雜，而且解壓縮時間長。因此，根據(jù)字符編碼的單值性，對哈夫曼編碼做了第二個改進(jìn)，即不構(gòu)造哈夫曼樹，而是用一個二維數(shù)組模擬哈夫曼樹的創(chuàng)建過程并得到各字符的編碼，這一改進(jìn)有效地提高了壓縮比。</p><p>　　關(guān)鍵詞：靜態(tài)哈夫曼編碼，壓縮，節(jié)點，哈夫曼樹</p><p><b>　　Abstract</b></p><p>　　Huffman

13、 encoding is a huffman tree that is optimal binary tree as the core, often used in data compression. In the computer information processing, "Huffman coding" is a consistent coding method (also known as entropy

14、 coding method ") for lossless compression of data. Entropy coding method "refers to the source character (for example, a file of a symbol) is encoded using a special encoding table. This coding table is specia

15、l because it is the statistical probability of occurrence of each source </p><p>　　Keywords: Static huffman coding, Compression, Node, huffman tree</p><p><b>　　第一章 緒論</b></p>

16、<p>　　1.1 研究目的及意義</p><p>　　從信息論角度看，信源編碼的一個最主要的目的，就是要解決數(shù)據(jù)的壓縮問題。</p><p>　　數(shù)據(jù)壓縮是指以最少的代碼表示信源所發(fā)出的信號，減少容納給定信息集合或數(shù)據(jù)采樣集合的信號空間。圖像編碼與壓縮的目的就是對圖像數(shù)據(jù)按一定的規(guī)則進(jìn)行變換和組合，從而達(dá)到以盡可能少的代碼表示盡可能多的圖像信息。</p><

17、p>　　圖像數(shù)字化之后，其數(shù)據(jù)量非常龐大，例如，一副640×480 的彩色圖像（24bit/</p><p>　　像素），其數(shù)據(jù)量約為921.6KB。如果以30 幀/s 的速度播放，則每秒的數(shù)據(jù)量為640×480×24×30bit=221.12Mbit，需要221 Mbit/s 的通信回路。在多媒體中，海量圖像數(shù)據(jù)的存儲和處理是一個難題。如不進(jìn)行編碼壓縮處理，一張存6

18、50MB 字節(jié)的光盤僅能存放24s 左右的640 像素×480 像素的圖像畫面[1][5]?？傊?，大數(shù)據(jù)量的圖像信息會給存儲器的存儲容量、通信干線通道的帶寬以及計算機(jī)的處理速度增加極大的壓力。僅靠增加存儲器容量，提高信道帶寬以及計算機(jī)的處理速度等方法來解決這個問題是不現(xiàn)實的。另一方面，圖像本身包含著大量的冗余成分。統(tǒng)計測量表明圖像信號在相鄰像素間、相鄰行間、相鄰幀之間存在著很強的相關(guān)性。一般情況下，畫面中亮度變化相對平坦的地方

19、，相鄰像素就有相同的值，而且對相鄰幀的圖像來說，畫面中的大部分區(qū)域信號變化緩慢，尤其是背景部分幾乎不變。如果能對這些冗余成分加以有效削減，就能夠大大節(jié)減圖像的存儲空間，減少圖像傳輸時所占信道容量，使得現(xiàn)有的PC 和網(wǎng)絡(luò)在指標(biāo)和性能方面能夠達(dá)到處理圖像信息的要求。沒有壓縮技術(shù)的發(fā)展，大容量圖像信息的存儲與傳輸難以適</p><p>　　1.2 圖像壓縮編碼技術(shù)概述</p><p>　　1.2

20、.1 圖像壓縮編碼技術(shù)分類</p><p>　　圖像壓縮編碼的方法很多，其分類視出發(fā)點不同而有差異。從圖像壓縮技術(shù)發(fā)展過程來看，可將圖像壓縮編碼分為兩代，第一代是指20世紀(jì)80年代以前的編碼方法，它主要研究有關(guān)信息熵、編碼方法以及數(shù)據(jù)壓縮比等內(nèi)容。第二代是指20 世紀(jì)80 年代以后的編碼方法，它突破了信源編碼理論，結(jié)合分形、模型基、神經(jīng)網(wǎng)絡(luò)、小波變換等數(shù)學(xué)工具，充分利用了人類視覺系統(tǒng)生理特性和圖像信源的各種特性。

21、但由于“第二代”編碼技術(shù)增加了分析的難度，所以大大增加了實現(xiàn)的復(fù)雜性。從當(dāng)前發(fā)展情況來看，它仍處于深入研究的階段。</p><p>　　根據(jù)解壓重建后的圖像與原始圖像之間是否有誤差，圖像壓縮編碼分為無損</p><p>　?。ㄒ渤蔀闊o失真、無誤差、信息保持、可逆壓縮）編碼和有損（有誤差、有失真、</p><p>　　不可逆）編碼兩大類。無損壓縮中去掉的僅僅是圖像數(shù)據(jù)

22、中冗余的數(shù)據(jù)，經(jīng)解碼重建的圖像和原始圖像沒有任何失真，如哈夫曼編碼、行程編碼、算術(shù)編碼；有損壓縮是指解碼重建的圖像與原始圖像相比有失真，不能精確地復(fù)原，但視覺效果基本上相同，是實現(xiàn)高壓縮比的編碼方法，如預(yù)測編碼、變換編碼。</p><p>　　1.2.2 圖像壓縮編碼評價</p><p>　　圖像信號在編碼和傳輸中會產(chǎn)生誤差，尤其是在熵壓縮編碼中，產(chǎn)生的誤差應(yīng)</p><

23、;p>　　在允許的范圍內(nèi)。壓縮方法的優(yōu)劣主要由壓縮比和所恢復(fù)的圖像的質(zhì)量兩個方面來衡量。</p><p><b>　　(1)圖像熵</b></p><p>　　設(shè)數(shù)字圖像像素灰度級集合為{d1,d2,……,dn}，其對應(yīng)的概率分別為p(d1)，</p><p>　　p(d2)，……,p(dn)。按信息論中信源信息熵的定義，圖像的熵定義為：

24、</p><p>　　(1) </p><p>　　圖像的熵表示像素各個灰度級數(shù)據(jù)的統(tǒng)計平均值，給出了對輸入灰度級集合進(jìn)</p><p>　　行編碼時所需的平均位數(shù)的下限。</p><p><b>　　(2)平均碼字長度</b></p><p>　　設(shè)ai 為數(shù)字圖像中灰度

25、級di 所對應(yīng)的碼字長度（二進(jìn)制代碼的位數(shù)），其相應(yīng)出現(xiàn)的概率為p(di)，則該數(shù)字圖像所賦予的平均碼字長度為：</p><p><b>　　(2)</b></p><p><b>　　(3)編碼效率</b></p><p><b>　　(3)</b></p><p>　　根據(jù)

26、信息論中信源碼理論，可以證明在R ≥ H 條件下，總可以設(shè)計出某種無</p><p>　　失真編碼方法。當(dāng)然如果編碼結(jié)果使R 遠(yuǎn)大于H，表明這種編碼方法效率很低，占用比特數(shù)太多。最好的編碼結(jié)果是使R 等于或接近于H。這種狀態(tài)的編碼方法，成為最佳編碼。</p><p><b>　　(4)壓縮比</b></p><p>　　壓縮比是指編碼前后平均碼

27、長之比，如果用n 表示編碼前每個字符的平均碼</p><p>　　長，通常為用二進(jìn)制碼表示時的位數(shù)，則壓縮比可表示為：</p><p><b>　　(4)</b></p><p>　　一般來說，壓縮比大，則說明被壓縮掉的數(shù)據(jù)量多。一個編碼系統(tǒng)要研究的問</p><p>　　題是設(shè)法減小編碼平均長度R，使編碼效率η盡量趨于

28、1，而冗余度趨于0。</p><p>　　1.3 哈夫曼編碼簡介</p><p>　　哈夫曼編碼是根據(jù)可變長最佳編碼定理，應(yīng)用哈夫曼算法而產(chǎn)生的一種編碼方</p><p>　　法。它是一種無損壓縮編碼方法，其基本原理是出現(xiàn)頻度較高的數(shù)據(jù)用較短的代碼，出現(xiàn)頻度較低的數(shù)據(jù)用較長的代碼。這些代碼都是二進(jìn)制碼，且碼長是可變的。它的實現(xiàn)主要借助于哈夫曼樹。哈夫曼樹，又稱最優(yōu)二

29、叉樹，是一類帶權(quán)路徑最短的樹。所有可能的輸入符號在哈夫曼樹上對應(yīng)為一個葉結(jié)點，葉結(jié)點的位置就是該符號的哈夫曼編碼。具體來說，一個符號對應(yīng)的哈夫曼編碼就是從根結(jié)點開始，沿左支或右支前進(jìn)，一直找到該符號所對應(yīng)的葉結(jié)點為止的路徑所產(chǎn)生的二進(jìn)制編碼。這種編碼是一種無前綴編碼，即，任一字符的編碼都不會是其他字符編碼的前綴，因而數(shù)據(jù)編碼后在存儲與傳輸?shù)倪^程中不會產(chǎn)生二義性。假設(shè)原始數(shù)據(jù)中含有k 個各不相同的字符a1，a2，，，ak，所出現(xiàn)的頻率分別

30、為w1，w2，，，wk，則哈夫曼編碼算法[2]如下：</p><p>　　根據(jù)給定的n 個權(quán)值{w1，w2，……wn}構(gòu)成n 棵二叉樹的集合F={T1，T2，……，Tn}，其中每棵二叉樹Ti（i=1，2，……n）中只有一個權(quán)值為wi 的根結(jié)點，其左、右子樹均為空；</p><p>　　（2）在F 中選取兩棵結(jié)點的權(quán)值最小的樹作為左、右子樹，構(gòu)造一棵新的二</p><p&

31、gt;　　叉樹，置新二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和；</p><p>　　在F 中刪除這兩棵樹，同時將新得到的二叉樹加入到F 中；</p><p>　　重復(fù)步驟（2）和（3），直到F 中只含一棵樹為止。這棵樹便是哈夫曼 樹。</p><p>　　將哈夫曼 樹的左支標(biāo)0，右支標(biāo)1，或者左支標(biāo)1，右支標(biāo)0（本文采用前一種形式）。然后將從根到葉子的路

32、徑上的標(biāo)號依次相連，作為該葉子所表示字符的編碼。</p><p>　　哈夫曼編碼有靜態(tài)和動態(tài)兩類。靜態(tài)哈夫曼編碼是以每個字符出現(xiàn)的概率為權(quán)</p><p>　　值構(gòu)造哈夫曼編碼樹，字符存在于葉子上，每個字符都有唯一的二進(jìn)制序列表示，壓縮時，只要壓入相應(yīng)的哈夫曼編碼即可；解壓時，根據(jù)取出的哈夫曼編碼，從根結(jié)點出發(fā)，編碼為0時走左子樹，為1時走右子樹，直至葉結(jié)點。動態(tài)哈夫曼編碼又稱自適應(yīng)哈夫曼

33、編碼，它對數(shù)據(jù)壓縮依據(jù)的是動態(tài)變化的哈夫曼編碼樹，具體地說，對第i+1個字符的編碼是根據(jù)原始數(shù)據(jù)中前i個字符所建立哈夫曼編碼樹進(jìn)行的。</p><p>　　1.4 本設(shè)計所做的主要工作</p><p>　　由上可知，不論是靜態(tài)哈夫曼編碼還是動態(tài)哈夫曼編碼，其編碼和解碼過程都相對簡單，而如何構(gòu)造哈夫曼編碼樹成為問題的關(guān)鍵。論文分別在第2章、第3章中詳細(xì)介紹了靜態(tài)哈夫曼編碼樹和動態(tài)哈夫曼編碼樹

34、的構(gòu)造方案，并且通過例子演示了構(gòu)造過程。之后，分別利用這兩種編碼算法實現(xiàn)了圖像的壓縮，并且給出了相應(yīng)的C語言代碼。第3章最后一節(jié)對兩種編碼方法作了比較。</p><p>　　另外，由于在構(gòu)造靜態(tài)哈夫曼樹時，大量的時間消耗在從元素集合中選取兩</p><p>　　個最小的元素上，因此，在其中引入了堆排序算法，這一改進(jìn)有效地縮短了壓縮時間，第4章第一節(jié)對這一改進(jìn)做了介紹。在靜態(tài)哈夫曼編碼算法中

35、，哈夫曼樹的保存占用了大量的空間，而動態(tài)哈夫曼編碼算法，雖然克服了前者的缺點，但是算法復(fù)雜，而且解壓縮時間長。因此，在第4章第二節(jié)，根據(jù)字符編碼的單值性，對哈夫曼編碼的第二個改進(jìn)做了介紹，即用一個二維數(shù)組模擬哈夫曼樹的創(chuàng)建過程并得到字符的前綴編碼，這一改進(jìn)有效地提高了壓縮比。</p><p>　　第二章 利用靜態(tài)哈夫曼編碼實現(xiàn)圖像壓縮</p><p>　　2.1 靜態(tài)哈夫曼編碼介紹<

36、/p><p>　　哈夫曼編碼是上個世紀(jì)五十年代由哈夫曼教授研制開發(fā)的,它借助了數(shù)據(jù)結(jié)構(gòu)當(dāng)中的樹型結(jié)構(gòu),在哈夫曼算法的支持下構(gòu)造出一棵最優(yōu)二叉樹,我們把這類樹命名為哈夫曼樹. 因此,準(zhǔn)確地說,哈夫曼編碼是在哈夫曼樹的基礎(chǔ)之上構(gòu)造出來的一種編碼形式,它的本身有著非常廣泛的應(yīng)用.</p><p>　　那么,哈夫曼編碼是如何來實現(xiàn)數(shù)據(jù)的壓縮和解壓縮的呢?</p><p>　　眾

37、所周知,在計算機(jī)當(dāng)中,數(shù)據(jù)的存儲和加工都是以字節(jié)作為基本單位的,一個西文字符要通過一個字節(jié)來表達(dá),而一個漢字就要用兩個字節(jié),我們把這種每一個字符都通過相同的字節(jié)數(shù)來表達(dá)的編碼形式稱為定長編碼. 以西文為例,例如我們要在計算機(jī)當(dāng)中存儲這樣的一句話: I am a teacher . 就需要15個字節(jié),也就是120個二進(jìn)制位的數(shù)據(jù)來實現(xiàn).</p><p>　　與這種定長編碼不同的是,哈夫曼編碼是一種變長編碼. 它根據(jù)

38、字符出現(xiàn)的概率來構(gòu)造平均長度最短的編碼. 換句話說如果一個字符在一段文檔當(dāng)中出現(xiàn)的次數(shù)多,它的編碼就相應(yīng)的短,如果一個字符在一段文檔當(dāng)中出現(xiàn)的次數(shù)少,它的編碼就相應(yīng)的長. 當(dāng)編碼中,各碼字的長度嚴(yán)格按照對應(yīng)符號出現(xiàn)的概率大小進(jìn)行逆序排列時,則編碼的平均長度是最小的. 這就是哈夫曼編碼實現(xiàn)數(shù)據(jù)壓縮的基本原理.</p><p>　　2.2 靜態(tài)哈夫曼編碼樹的構(gòu)造</p><p>　　哈夫曼（H

39、uffman）編碼屬于碼詞長度可變的編碼類，是哈夫曼在1952年提出的一種編碼方法，該算法的核心部分為哈夫曼編碼樹（huffman coding tree） 一棵滿二叉樹。所有可能的輸入符號（通常對應(yīng)為字節(jié)）哈夫曼編碼樹上對應(yīng)為一個葉節(jié)點，在葉節(jié)點的位置就是該符號的哈夫曼編碼。具體來說，一個符號對應(yīng)的哈夫曼編碼就是從根節(jié)點開始，沿左字節(jié)點（0）或右子節(jié)點（1）前進(jìn)，一直找到該符號葉節(jié)點為止的路徑對應(yīng)的二進(jìn)制編碼。在哈夫曼編碼樹的基礎(chǔ)上，

40、該算法的編碼部分輸入一系列的符號，根據(jù)哈夫曼樹對符號進(jìn)行翻譯，以符號在哈夫曼樹上的位置作為編碼結(jié)果。解碼部分反之，根據(jù)輸入的哈夫曼編碼，通過查詢哈夫曼樹翻譯回原始符號，即從下到上的編碼方法。同其他碼詞長度可變的編碼一樣，區(qū)別在于不同碼詞的生成是基于不同符號出現(xiàn)的不同概率。生成哈夫曼編碼算法基于一種稱為“編碼樹”（coding tree）的技術(shù)。算法步驟如下：</p><p>　　初始化，根據(jù)符號概率的大小按由大到

41、小順序?qū)Ψ栠M(jìn)行排序。</p><p>　　把概率最小的兩個符號組成一個新符號（節(jié)點），即新符號的概率等于這兩個符號概率之和。</p><p>　　重復(fù)第2步，直到形成一個符號為止（樹），其概率最后等于1。</p><p>　　從編碼樹的根開始回溯到原始的符號，并將每一下分枝賦值為1，上分枝賦值為0。</p><p>　　2.3 靜態(tài)哈夫曼編

42、碼的具體編碼過程</p><p>　　哈夫曼編碼步驟：1）把信源符號xi(i=1,2,… ,N) 按出現(xiàn)概率的值由大到小的順序排列；2）對兩個概率最小的符號分別分配以“0”和“1”，然后把這兩個概率相加作為一個新的輔助符號的概率；3）將這個新的輔助符號與其他符號一起重新按概率大小順序排列；4）跳到第2 步，直到出現(xiàn)概率相加為1 為止；5）用線將符號連接起來，從而得到一個碼樹，樹的N 個端點對應(yīng)N 個信源符號；6）

43、從最后一個概率為1 的節(jié)點開始，沿著到達(dá)信源的每個符號，將一路遇到的二進(jìn)制碼“0”或“1”順序排列起來，就是端點所對應(yīng)的信源符號的碼字。由于哈夫曼方法構(gòu)造出來的碼不是惟一的，主要有兩個原因：一是在兩個符號概率相加給兩條支路分配“0”和“1”時，這一選擇是任意的；二是當(dāng)兩個消息的概率相等時，0，1 分配也是隨意的。哈夫曼編碼對不同的信源，其編碼效率是不同的。7）哈夫曼編碼中，沒有一個碼字是另一個碼字的前綴。因此，每個碼字惟一可譯。<

44、/p><p>　　2.4 靜態(tài)哈夫曼編碼的算法實例</p><p>　　下面我們以 abcddbb 作為待編碼的原始數(shù)據(jù)串為例，構(gòu)造靜態(tài)哈夫曼編碼樹。</p><p>　　首先，我們需要統(tǒng)計出 a, b, c, d 四個符號分別在原始數(shù)據(jù)串中的出現(xiàn)頻率。統(tǒng)計結(jié)果如表 1所示：</p><p><b>　　表1 符號出現(xiàn)頻率</b&

45、gt;</p><p>　　然后，按照前面提到的構(gòu)造方法，經(jīng)過表 2 的四個步驟，即可獲得起基于表 1 頻率統(tǒng)計的靜態(tài)哈夫曼編碼樹.</p><p>　　表2 建立哈夫曼編碼樹</p><p>　　到此為止，我們建立起了給定符號串的哈夫曼編碼樹。經(jīng)過編碼a:000,b:1,c:001,d:01，但若a b c d的編碼分別為:0 ,10 ,101 ,11 ,我們得到

46、的壓縮數(shù)據(jù)為1010 時,那么在解壓縮時就會存在兩種翻譯的可能,一種為bb ,另一種為ca ,為什么會出現(xiàn)這樣的現(xiàn)象呢? 通過觀察我們發(fā)現(xiàn),字符b 的編碼為10 ,而字符c 的編碼為101 ,b 的編碼恰好是c 的編碼的前兩位,就造成了b 的編碼添加一位就有可能成為c ,這就增加了解壓縮的過程中誤碼的可能. 因為定長編碼已經(jīng)用相同的位數(shù)這個條件保證了任一個字符的編碼都不會成為其它編碼的前綴,所以這種情況只會出現(xiàn)在變長編碼當(dāng)中,要想避免這

47、種情況,我們就必須用一個條件來制約定長編碼,這個條件就是要想成為壓縮編碼,變長編碼就必須是前綴編碼.</p><p>　　什么是前綴編碼呢? 所謂的前綴編碼就是任何一個字符的編碼都不能是另一個字符編碼的前綴.那么哈夫曼編碼是否是前綴編碼呢? 觀察a 、b 、c 、d 構(gòu)成的編碼樹,可以發(fā)現(xiàn)b 之所以成為c 的前綴,是因為在這棵樹上,b 成為了c 的父結(jié)點,從在哈夫曼樹當(dāng)中,原文檔中的數(shù)據(jù)字符全都分布在這棵哈夫曼樹

48、的葉子位置,從而保證了哈夫曼編碼當(dāng)中的任何一個字符的編碼都不能是另一個字符編碼的前綴.也就是說哈夫曼編碼是一種前綴編碼,也就保證了解壓縮過程當(dāng)中譯碼的準(zhǔn)確性.</p><p>　　2.3 利用靜態(tài)哈夫曼編碼壓縮與還原圖像的C語言實現(xiàn)</p><p>　　2.3.1 壓縮的實現(xiàn)</p><p>　　(1) 壓縮算法思想</p><p>　　由于

49、進(jìn)行的是無損壓縮, 所以要掃描圖像的所有像素點,壓縮過程分為四步:①掃描統(tǒng)計像素出現(xiàn)的概率并按大小排列;②建立最優(yōu)二叉樹;③哈夫曼編碼;④保存編碼。</p><p>　　經(jīng)過哈夫曼編碼后的圖像中的不同像素分別用不同長度二進(jìn)制編碼表示,接下來的工作就是保存重編碼后的像素,由于無損壓縮中編碼前后一幅圖像的像素點數(shù)是相同的,如果仍然以像素為單位保存圖像數(shù)據(jù)就無法實現(xiàn)壓縮功能,能夠?qū)崿F(xiàn)壓縮是因為編碼前后表示像素的二進(jìn)制編

50、碼的位數(shù)有所變化。所以,應(yīng)該對重編碼后的二進(jìn)制位按位存儲。</p><p>　　(2) 壓縮算法流程圖</p><p>　　為提高壓縮效率，在靜態(tài)哈夫曼編碼算法中引入了堆排序算法，對于這一改進(jìn)</p><p>　　的詳細(xì)介紹將在第四章中給出。于是，在靜態(tài)哈夫曼算法的基礎(chǔ)上，根據(jù)統(tǒng)計出的概率值，先建堆，再構(gòu)造編碼樹，然后實現(xiàn)編碼壓縮。其編碼過程如圖2-1所示，其中編碼

51、表的生成過程如圖2-2所示，對字符的編碼過程如圖2-3所示：</p><p>　　圖2-1 靜態(tài)哈夫曼壓縮流程圖 </p><p>　　圖2-2 編碼表的生成 圖2-3 對字符編碼</p><p><b>　　(3) 實現(xiàn)代碼</b></p><p&

52、gt;　　詳見附錄：1.靜態(tài)哈夫曼編碼對圖像壓縮的實現(xiàn)代碼</p><p>　　2.3.2 解壓縮的實現(xiàn)</p><p><b>　　(1)解壓算法思想</b></p><p>　　壓縮文件的文件結(jié)構(gòu)如表1 在文件頭部分可利用像素與文件頭的偏移量距離位置計算文件頭和全表的長度, 從而得到哈夫曼編碼樹的起始位置。解碼過程:</p>

53、<p>　　(1)指向哈夫曼樹的樹根。</p><p>　　(2)根據(jù)當(dāng)前一位編碼為0或1從而指向左或右兒子節(jié)點。</p><p>　　(3)判斷該節(jié)點的左,右兒子是否是空(即為0)不是則向后掃描一個編碼,執(zhí)行上一步,如是則完成一個解碼,該葉子節(jié)點的數(shù)組下標(biāo)即為像素值, 繼續(xù)解下一個。在解碼過程中需要把按位存儲的編碼讀取出來,這個過程就是按位讀取。</p><

54、p><b>　　(2)解壓流程圖</b></p><p>　　根據(jù)靜態(tài)哈夫曼算法，解壓縮過程為壓縮的逆過程。先讀取解壓縮文件頭，獲</p><p>　　得原文件的長度，字符的編碼長度，字符的個數(shù)等信息，再構(gòu)建解壓縮樹，依次將編碼恢復(fù)成原始數(shù)據(jù)。其總體流程圖如圖2-4所示：</p><p>　　圖2-4 靜態(tài)哈夫曼解壓縮流程圖</p&

55、gt;<p><b>　　(3) 實現(xiàn)代碼</b></p><p>　　詳見附錄：2.靜態(tài)哈夫曼編碼對圖像解壓的實現(xiàn)代碼</p><p>　　2.4 圖象壓縮實例</p><p>　　有一幅800×600的24位位圖，名稱為“Example.bmp”，大小為1.35MB，如圖2-5</p><p>

56、;　　所示，按照以上算法進(jìn)行壓縮，圖像熵約為7.259， 平均碼字長度為7.292，編碼效率為0.995，壓縮比約為1.096，壓縮后容量為1.25MB，根據(jù)第一章第二節(jié)介紹的圖像壓縮編碼評價，以上編碼是最佳編碼，冗余度為0.005。所用時間為0.371s。</p><p>　　圖2-5 Example.bmp</p><p>　　其運行界面如圖2-6所示：</p><

57、p>　　圖2-6 利用靜態(tài)哈夫曼編碼壓縮圖像Example.bmp 的運行界面</p><p>　　還原之后如圖2-7 所示，大小仍為1.35MB，無失真，所用時間為0.621s，其</p><p>　　運行界面如圖2-8 所示：</p><p>　　圖2-7 解壓縮后的圖像</p><p>　　圖2-8 利用靜態(tài)哈夫曼編碼解壓縮圖像E

58、xample.bmp 的運行界面</p><p>　　第三章 利用動態(tài)哈夫曼編碼實現(xiàn)圖像壓縮</p><p>　　3.1 動態(tài)哈夫曼編碼的提出</p><p>　　由上一章可知，靜態(tài)哈夫曼編碼需要對原始數(shù)據(jù)進(jìn)行兩遍掃描，第一遍統(tǒng)計原始數(shù)據(jù)中各字符出現(xiàn)的概率，利用得到的概率值創(chuàng)建哈夫曼樹并將樹的有關(guān)信息保存起來，便于解壓時使用，第二遍則根據(jù)前面得到的哈夫曼樹對原始數(shù)據(jù)

59、進(jìn)行編碼，并將編碼信息存儲起來，便于傳輸。如果將這種方法用于網(wǎng)絡(luò)通信中，兩遍掃描勢必會引起較大的延時，如果用于壓縮中，額外的磁盤訪問將會降低該算法的壓縮速度。尤其是對于短小的符號流來說，加上哈夫曼編碼樹的編碼結(jié)果之后，它在尺寸上可能更大，這使靜態(tài)哈夫曼編碼的應(yīng)用受到限制。另外，靜態(tài)編碼樹的構(gòu)造方案不能對符號流的局部統(tǒng)計規(guī)律變化做出反應(yīng)，因為它從始至終都使用完全不變的編碼樹。因此，有人提出了自適應(yīng)哈夫曼編碼方案，即動態(tài)哈夫曼編碼。這種方案

60、不需事先構(gòu)造哈夫曼編碼樹，而是隨著編碼的進(jìn)行，逐步構(gòu)造哈夫曼樹。同時，這種編碼方案對符號的統(tǒng)計也是動態(tài)進(jìn)行的。這樣就在一定程度上解決了靜態(tài)哈夫曼編碼樹的不足。嚴(yán)格的說，動態(tài)哈夫曼 編碼不僅涉及到編碼樹的構(gòu)造問題，還與編碼、解碼過程相關(guān)。由于其實用性有了一定的提高，因而應(yīng)用領(lǐng)域也更加廣泛。</p><p>　　3.2 動態(tài)哈夫曼編碼的原理</p><p>　　動態(tài)哈夫曼編碼不需要事先構(gòu)造哈夫

61、曼樹，而是隨著編碼的進(jìn)行，逐步構(gòu)造哈夫曼樹。同時，這種編碼方式對符號的統(tǒng)計也動態(tài)進(jìn)行，隨著編碼的進(jìn)行，同一個符號的編碼可能發(fā)生改變（變得更長或更短）。</p><p>　　在構(gòu)造動態(tài)哈夫曼編碼數(shù)的過程中，需要遵循兩條重要的原則：</p><p>　?。?）權(quán)重值大的節(jié)點，節(jié)點編號也較大。</p><p>　　（2）父節(jié)點的節(jié)點編號總大于子節(jié)點的節(jié)點編號。</p

62、><p>　　以上兩點成為兄弟屬性。在每次調(diào)整權(quán)重值時，都需要相應(yīng)的調(diào)整節(jié)點編號，以避免兄弟屬性被破壞。在對某一個節(jié)點權(quán)重值進(jìn)行“加一操作”時，應(yīng)該首先檢查該節(jié)點是否具有所在的塊中的最大節(jié)點編號，如果不是，則應(yīng)該將該節(jié)點的權(quán)重值加一。這樣，由于該節(jié)點的節(jié)點編號已經(jīng)處于原來所屬塊中的最大值，因此權(quán)重值加一之后兄弟屬性依然得到滿足。最后由于節(jié)點的權(quán)重發(fā)生變化，必須遞歸的對節(jié)點的父節(jié)點進(jìn)行加一操作。</p>

63、<p>　　初始化編碼樹時，由于只允許對待編碼數(shù)據(jù)流進(jìn)行單遍掃描，因此不可能預(yù)知各種符號的出現(xiàn)頻率。為了對所有符號一致對待，編碼書的初始狀態(tài)只包含一個葉節(jié)點，包含符號NYT（Not Yet Transmitted,尚未傳送），權(quán)重值為0.NYT是一個逸出碼（escape code），不同于任何一個將要傳送的符號。但有一個尚未包含在編碼樹種的符號需要被編碼時，系統(tǒng)就輸出NYT編碼，然后跟著符號的原始表達(dá)。當(dāng)解碼器出一個NYT之后

64、，它就知道下面的內(nèi)容暫時不再是哈夫曼編碼，而是一個從未在編碼數(shù)據(jù)流中出現(xiàn)過的原始符號。這樣任何符號都可以在增加到編碼樹之前進(jìn)行傳送。</p><p>　　在需要插入一個新符號時，總是先構(gòu)造一個新的子樹，子樹包含NYT符號與新符號的兩個節(jié)點，然后將舊的NYT節(jié)點由這個子樹代替，由于包含NYT符號的節(jié)點權(quán)重值為0，而包含新符號的葉節(jié)點的權(quán)重值為1，因此最終效果相當(dāng)于原NYT節(jié)點位置的權(quán)重值由0變?yōu)?.因此，下一步將試

65、圖對其父節(jié)點執(zhí)行權(quán)重值“加一操作”。</p><p>　　動態(tài)哈夫曼編碼的方式與今天哈夫曼編碼一致，每次符號編碼完成后，也對包含符號的節(jié)點權(quán)值進(jìn)行加一操作。</p><p>　　將一個新的符號插入編碼樹或者輸出摸一個已編碼符號后，相應(yīng)的符號的出現(xiàn)次數(shù)增加1，繼而編碼樹種各種符號的出現(xiàn)頻率發(fā)生了改變，不一定符合兄弟屬性，按照上述方法進(jìn)行調(diào)整，使其符合要求。</p><p&

66、gt;　　3.3 動態(tài)哈夫曼編碼的算法思想</p><p>　　（1）初始化編碼樹，即建立一棵只有一個空葉結(jié)點的哈夫曼樹，該結(jié)點的</p><p>　　符號為NYT（尚未傳送），權(quán)值始終為0；</p><p>　　（2）每讀進(jìn)一個字符，首先檢查該字符是否已經(jīng)在編碼樹中，如果是，就以</p><p>　　靜態(tài)哈夫曼編碼中相同的方式對其進(jìn)行編碼，

67、然后更新編碼樹；如果不是，先對空葉結(jié)點進(jìn)行編碼，再生成一棵子樹，其右分支結(jié)點為剛讀入的字符，其左分支結(jié)點為一個新的空葉結(jié)點，然后用這棵子樹代替原來的空葉結(jié)點；</p><p>　?。?）將前i 個字符的哈夫曼樹調(diào)整成一棵i+1 個字符的哈夫曼樹，首先，</p><p>　　以葉結(jié)點ai 為初始的當(dāng)前結(jié)點，重復(fù)地將當(dāng)前結(jié)點與具有同樣權(quán)值的編號最大的結(jié)點進(jìn)行交換，并使得后者的父結(jié)點成為新的當(dāng)前

68、結(jié)點，直到遇到根結(jié)點為止；其次，將根到葉結(jié)點ai 路徑上的所有結(jié)點的權(quán)值加1，該樹就變成了前i+1 個字符的哈夫曼樹，并且該二叉樹仍是最優(yōu)二叉樹。該算法流程圖如圖3-1 所示：</p><p>　　圖3-2 動態(tài)哈夫曼編碼算法對一個輸入符號進(jìn)行編碼并更新編碼樹的流程圖</p><p>　　3.4 動態(tài)哈夫曼編碼的編碼實例</p><p>　　下面我們?nèi)砸缘诙轮薪o出

69、的數(shù)據(jù)串a(chǎn)bcddbb為例，演示動態(tài)哈夫曼編碼樹的</p><p>　　構(gòu)造過程，如表3-1所示。</p><p>　　表3-1 數(shù)據(jù)串a(chǎn)bcddbb的動態(tài)哈夫曼編碼樹的構(gòu)造過程</p><p>　　通過觀察以上步驟，容易發(fā)現(xiàn)動態(tài)哈夫曼編碼的幾個特征：</p><p>　　(1) 在步驟13 得到的編碼樹與靜態(tài)哈夫曼編碼樹基本相同，除了NYT

70、節(jié)點和符號a節(jié)點組成的子樹替代了靜態(tài)哈夫曼編碼樹中的符號a 的葉節(jié)點之外；</p><p>　　(2) 在每一次輸入新的符號之前，編碼樹都處于完整可用的正常狀態(tài)；</p><p>　　(3) 同一個輸入符號，可能產(chǎn)生多種不同的輸出。例如三次輸入的符號b，產(chǎn)生的輸出分別為0b、001 和10；</p><p>　　(4) 同樣的輸出結(jié)果，可能由不同的輸入產(chǎn)生。例如第二

71、次輸入的符號d 與第二次輸入的符號b，都產(chǎn)生了001 作為輸出結(jié)果。</p><p>　　這些特征首先說明了動態(tài)哈夫曼編碼樹與靜態(tài)哈夫曼編碼樹等同，完全符合哈夫曼樹的定義。同時，由于每一個輸入符號都對編碼樹產(chǎn)生了影響，因此解碼過程無法從哈夫曼編碼數(shù)據(jù)流的某一個中間位置開始進(jìn)行，而必須從頭至尾逐bit 處理。由于動態(tài)哈夫曼編碼算法采用了先編碼，后調(diào)整編碼樹的方案，相應(yīng)的解碼算法比較簡單。解碼算法也使用僅有唯一的NY

72、T 節(jié)點的編碼樹作為初始狀態(tài)，然后根據(jù)哈夫曼編碼數(shù)據(jù)流，對符號進(jìn)行還原。每次處理完一個符號，就使用這個符號調(diào)整編碼樹。這樣，在每一次輸入新的符號之前，哈夫曼樹都處于與進(jìn)行編碼時使用的哈夫曼樹完全相同的狀態(tài)，保證了解碼的正確性。</p><p>　　3.5 利用動態(tài)哈夫曼編碼壓縮與還原圖像的C語言實現(xiàn)</p><p>　　3.5.1 數(shù)據(jù)結(jié)構(gòu)</p><p>　　ty

73、pedef struct tree {</p><p>　　int leaf[SYMBOL_COUNT ];</p><p>　　int next_free_node;</p><p>　　struct node {</p><p>　　unsigned int weight;</p><p>　　int parent

74、;</p><p>　　int child_is_leaf;</p><p>　　int child;</p><p>　　} nodes[NODE_TABLE_COUNT ];</p><p><b>　　} TREE;</b></p><p>　　其中l(wèi)eaf[SYMBOL_COUNT ]指明

75、每個字符在哈夫曼樹中葉子結(jié)點的位置，它被初始化為-1；next_free_node 指明首次出現(xiàn)的字符插入哈夫曼樹中的位置；weight 指明每個結(jié)點的權(quán)值；parent 指明該結(jié)點的父結(jié)點位置；child_is_leaf 指明該結(jié)點是否是葉子結(jié)點，若是則置child_is_leaf = 0；若不是則置child_is_leaf = 1；child指明該結(jié)點是葉結(jié)點，則葉子上存放字符的值，否則指明該結(jié)點左孩子的位置，其右孩子的位置是ch

76、ild+1；NODE_TABLE_COUNT =( SYMBOL_COUNT * 2 ) - 1。結(jié)點符號有258 種可能的取值, 0到255 表示真實的字節(jié)值，256指文件結(jié)束標(biāo)志，257表示空葉結(jié)點，用NYT(not yettransmitted)表示，它有兩重含義：其一在編碼流中代表其后跟隨的8 bit 不再是編碼，而是一個新的符號；其二內(nèi)存中的NYT 結(jié)點代表新結(jié)點的插入位置。故定義END_OF_STREAM的值為256，定義N

77、YT的值為257，定義SYMBOL_COUNT的值為258。</p><p>　　3.5.2 壓縮的實現(xiàn)</p><p>　　(1) 壓縮算法流程圖</p><p>　　首先，初始化哈夫曼樹，然后，對每一個字符進(jìn)行兩種操作：編碼，更新哈夫曼樹，當(dāng)遇到符號END_OF_STREAM時，結(jié)束。具體實現(xiàn)過程如圖3-3所示：</p><p>　　圖3

78、-3 動態(tài)哈夫曼壓縮流程圖</p><p><b>　　(2) 代碼實現(xiàn)</b></p><p>　　詳見附錄：3．動態(tài)哈夫曼編碼對圖像壓縮的實現(xiàn)代碼</p><p>　　3.5.3 解壓縮的實現(xiàn)</p><p><b>　　(1) 解壓流程圖</b></p><p>　　首

79、先，初始化哈夫曼樹，然后，對每一個字符進(jìn)行兩種操作：解碼，更新哈夫曼樹，直到符號END_OF_STREAM。具體實現(xiàn)過程如圖3-4所示：</p><p>　　圖3-4 動態(tài)哈夫曼解壓縮流程圖</p><p><b>　　(2) 實現(xiàn)代碼</b></p><p>　　詳見附錄：4．動態(tài)哈夫曼編碼對圖像解壓的實現(xiàn)代碼</p><

80、p>　　3.6 圖像壓縮實例</p><p>　　對于第二章壓縮的圖像，利用上述算法壓縮后，大小為999KB，所用時間為0.77s，</p><p>　　壓縮比為4.11。運行界面如圖3-5所示：</p><p>　　圖3-5 利用動態(tài)哈夫曼編碼壓縮圖像Example.bmp的運行界面</p><p>　　還原之后大小仍為1.35MB，

81、無失真，所用時間為0.871s，運行界面如圖3-6所示：</p><p>　　圖3-6 利用動態(tài)哈夫曼編碼解壓縮圖像Example.bmp的運行界面</p><p>　　3.7 靜態(tài)哈夫曼編碼與動態(tài)哈夫曼編碼的比較</p><p>　　如前所述,靜態(tài)哈夫曼編碼的缺點在于需對原始數(shù)據(jù)進(jìn)行兩遍掃描。第一遍</p><p>　　掃描統(tǒng)計字符出現(xiàn)頻率

82、并建樹，第二遍掃描根據(jù)所建哈夫曼樹進(jìn)行編碼。由此，</p><p>　　在壓縮時，將會降低壓縮速度。同時，為保存哈夫曼樹以供解壓時用，也將浪費一部分存儲空間。由于靜態(tài)建樹，其壓縮率也有所下降。動態(tài)哈夫曼 編碼對數(shù)據(jù)的壓縮是依據(jù)動態(tài)變化的哈夫曼編碼樹，亦即對第i+1個字符的編碼是由原始數(shù)據(jù)中前i個字符所建立的哈夫曼樹確定。壓縮和解壓子程序具有相同的初始化樹，每處理完一個字符，壓縮和解壓縮使用相同的算法</p&

83、gt;<p>　　更新哈夫曼樹，不必為解壓而保存哈夫曼樹的有關(guān)信息，從而大大提高了壓縮率。但是，由于動態(tài)哈夫曼編碼算法在解壓時采用與壓縮時相同的方法建樹，增加了解壓時間，從而降低了還原速度。而靜態(tài)哈夫曼編碼由于對哈夫曼樹進(jìn)行保存，還原時不必重新建樹,節(jié)省了還原時間。</p><p>　　下面給出靜態(tài)哈夫曼編碼和動態(tài)哈夫曼編碼在圖像壓縮中的比較，如表3-2</p><p>&l

84、t;b>　　所示。</b></p><p>　　表3-2 靜態(tài)哈夫曼編碼和動態(tài)哈夫曼編碼在圖像壓縮中的比較</p><p>　　由上表可以看出，當(dāng)圖像容量小時，雖然利用動態(tài)哈夫曼 編碼算法壓縮圖像，</p><p>　　不用保存哈夫曼 樹，從而大大提高了壓縮比，但是針對圖像的特點，大量的時間消耗在了更新編碼樹上，這樣卻延長了壓縮時間和解壓縮時間；當(dāng)

85、圖像容量大時，一定程度上提高了壓縮比，而且縮短了壓縮時間，但又延長了解壓縮時間。所以在第4 章中將對哈夫曼 編碼進(jìn)行改進(jìn)，使得這種無損壓縮方法更加實用。</p><p>　　第四章 對哈夫曼編碼的改進(jìn)</p><p>　　4.1 在哈夫曼編碼中引入堆排序</p><p>　　堆排序算法（HEAPSORT）由1991 年計算機(jī)先驅(qū)獎獲得者、斯坦福大學(xué)計算機(jī)科學(xué)系教授羅

86、伯特·弗洛伊德(Robert W．Floyd)和威廉姆斯(J．Williams)在1964 年共同發(fā)明。堆排序是一樹形選擇排序，堆頂元素是堆中的最大(或最小)元素，且堆的每一條路徑上的元素都是有序的。堆排序正是利用了堆頂元素最大(或最小)這一特征，使得在當(dāng)前無序區(qū)中選取最大(或最小)關(guān)鍵字變得簡單。</p><p>　　堆排序中的堆分為大頂堆和小頂堆，其中大頂堆指根結(jié)點(亦稱為堆頂)的關(guān)鍵字是堆里所有關(guān)

87、鍵字中最大者的堆。小頂堆指根結(jié)點(亦稱為堆頂)的關(guān)鍵字是堆里所有關(guān)鍵字中最小者的堆。當(dāng)排序元素不再變化時，利用堆排序可一次求出所需序列。這時，堆排序的時間復(fù)雜度恒為O(nlog(n)),不會像其他排序那樣有出入，而且空間復(fù)雜度為V(n),是最低的。</p><p>　　在哈夫曼編碼算法中，為了從R[1..n]中選出兩個頻率最小的元素，需要進(jìn)行兩趟循環(huán)，每次進(jìn)行n-1 次比較。事實上，在第二趟的n-1 次比較中，有

88、許多比較可能已經(jīng)在第一趟循環(huán)中做過，但由于前一趟比較時未保留這些比較結(jié)果，所以后一趟排序時又重復(fù)執(zhí)行了這些比較操作。而堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)，從而縮短了壓縮時間。</p><p>　　在哈夫曼編碼算法中引入堆排序思想后，與靜態(tài)哈夫曼編碼、動態(tài)哈夫曼編碼的比較如表4-1 所示：</p><p>　　表4-1 引入堆排序后的哈夫曼編碼與靜、動態(tài)哈夫曼編碼的比較&l

89、t;/p><p>　　4.2 模擬哈夫曼樹的創(chuàng)建</p><p>　　在靜態(tài)哈夫曼編碼算法中，必須保存統(tǒng)計出的結(jié)果以便解碼時構(gòu)造相同的哈夫曼樹，或者直接保存哈夫曼樹本身，這要占用大量的空間，也就意味著壓縮效率的下降。在動態(tài)哈夫曼編碼算法中，雖然克服了前者的缺點，但是算法復(fù)雜，而且解壓縮耗費時間長，若用于通信，就會引起較大的延時。實際上，我們進(jìn)行壓縮時，所關(guān)心的是字符編碼的單值性，基于這種壓縮思

90、想，沒有必要構(gòu)造哈夫曼樹，用一個二維數(shù)組就可以模擬哈夫曼樹的創(chuàng)建過程并得到各字符的編碼。實現(xiàn)思想如下：</p><p>　　先統(tǒng)計每個編碼長度Ni (二叉樹上的Ni 層) 上對應(yīng)數(shù)據(jù)的數(shù)目，再分別對Ni 層上的符號以遞增順序分配編碼。最底層編碼從0 開始， 第Ni 層第一個編碼為下一層最后一個編碼的左邊Ni 位數(shù)+ 1 。</p><p>　　例如，有一幅圖片Picture.bmp，包含七

91、種顏色，分別為A，B，C，D，E，F(xiàn)，G，其出現(xiàn)概率分別為0.25，0.20，0.18，0.13，0.10，0.09，0.05。按照哈夫曼算法，所得哈夫曼樹如圖4-1所示：</p><p>　　圖4-1 Picture.bmp的哈夫曼編碼樹</p><p>　　根據(jù)上述實現(xiàn)思想，字符F，G，C，D，E，A，B的編碼分別為0000，0001，0010，0011，010，011，10，11。顯

92、然，這組編碼不能通過哈夫曼樹來建立，但與各個字符的哈夫曼編碼相比，其編碼長度并沒有改變，而且每個字符的編碼也不是其他字符編碼的前綴，同樣可以實現(xiàn)壓縮，且不會產(chǎn)生二義性。另外，通過計算圖像熵和平均編碼長度，由最佳編碼定理知，該編碼仍為最佳編碼。因此，壓縮信息中無須保存哈夫曼樹，只須保存按層遍歷二叉樹所得的符號，以及每層編碼的個數(shù)即可。這就使得在整個壓縮、解壓縮過程中所需空間比哈夫曼編碼少得多，從而提高了壓縮比。</p>&l

93、t;p><b>　　第五章 總結(jié)</b></p><p><b>　　5.1 總結(jié)</b></p><p>　　哈夫曼編碼是數(shù)據(jù)壓縮領(lǐng)域中最著名的編碼方式之一。它通過出現(xiàn)概率的不等性，構(gòu)造變長編碼，達(dá)到減少文件大小的目的。目前廣泛應(yīng)用的許多其他高效的數(shù)據(jù)壓縮算法（如算術(shù)編碼，可預(yù)測編碼等）也是在哈夫曼編碼的基礎(chǔ)上發(fā)展起來的。所以，研究哈夫曼

94、編碼，對于深入理解數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計等學(xué)科中的相關(guān)課題是十分有益的。特別是對動態(tài)哈夫曼編碼的探索以及對整個哈夫曼算法的改進(jìn)，盡可能使程序穩(wěn)定、快速、高效地運行，充分體現(xiàn)了對軟件時空需求進(jìn)行優(yōu)化和權(quán)衡的思想。</p><p>　　本設(shè)計從分析靜態(tài)哈夫曼編碼開始，逐步過度到動態(tài)哈夫曼編碼的實現(xiàn)，最后通過對兩者的比較，又對哈夫曼算法提出了一些可行的改進(jìn)。但也存在一些不足，如動態(tài)哈夫曼編碼的C 語言實現(xiàn)還不夠精練，選取的

95、圖像材料說服力不強等。并且在壓縮時間和壓縮比上不能做到十全十美，總要舍棄一頭顧一頭的感覺，三者之間的平衡點不知道怎么去找，而且就現(xiàn)有問題自己弄得有點焦頭爛額，如果有時間的話以后再對這方面的問題進(jìn)行詳細(xì)的研究，算法的改進(jìn)，我覺得是可以找到一個能兼顧三者優(yōu)點的算法。</p><p>　　最后，在對哈夫曼編碼的研究過程中，經(jīng)過不斷查資料、調(diào)程序，我對C語言以及哈夫曼編碼有了更深的了解，對圖像處理方面的知識有了一定的掌握

96、，對算法設(shè)計及實現(xiàn)有了深刻的理解和體會，從開始的不知道哈夫曼編碼是什么，如何變，為什么編碼，如何應(yīng)用，到現(xiàn)在掌握基礎(chǔ)的一些知識外還在此之上更深入的了解哈夫曼編碼，圖樣處理，以及堆的定義。另外，我深深的體會到了搞研究不僅需要知識，更重要的是耐心、恒心和細(xì)心。期間，受到了許多朋友和老師的幫助，從他們那兒也學(xué)到很多知識，知道了腳踏實地、謙虛認(rèn)真、心平氣和是一個研究者所應(yīng)具備的基本素質(zhì)。這些都使我受益匪淺。讓我在今后的學(xué)習(xí)工作當(dāng)中更好的去成長，

97、更快的去具備一個國家所需人才應(yīng)有的素質(zhì)和本領(lǐng)。</p><p><b>　　致謝</b></p><p>　　做論文歷時5個月，整篇論文從起草修改到定稿遇到了很多的困難，各種各樣的技術(shù)難題，從最開始的不知道何為哈夫曼編碼到后來能掌握它的應(yīng)用原理這都得感謝我的指導(dǎo)老師xx老師不厭其煩的指導(dǎo)，雖然沒有手把手的教，但是給我了大概的方向，讓我自己去琢磨怎么做，在不停琢磨中不斷

98、的提升自我，鍛煉了我各個方面的能力，讓我受益匪淺，而且私下里同學(xué)的幫助也是很多的，要感謝xx同學(xué)在論文修改方面提出的各方面建議，再要感謝xx同學(xué)提供的技術(shù)支持，現(xiàn)在真正理解了啥叫眾人拾柴火更旺的道理，這篇論文的制作讓我在各個方面都收獲了不少。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]邵天增，冬尚娟.[M]哈夫曼編碼應(yīng)用的一種改進(jìn).上海市

99、：華東師范大學(xué) 2008,31-56</p><p>　　[2]鹿璐.[M]哈夫曼編碼器軟硬件系統(tǒng)的設(shè)計與實現(xiàn).北京市：交通部管理干部學(xué)院,2010,22-73</p><p>　　[3] 數(shù)據(jù)結(jié)構(gòu)與算法分析,.Cli?ord A. Sha?er, 張銘、劉曉丹譯. 電子工業(yè)出版社, 1998,100-125[4]吳樂南. 數(shù)據(jù)壓縮(第一版)[M].北京:電子工業(yè)出版社,200

100、0:1-118  [5]馮斐玲.數(shù)據(jù)壓縮技術(shù)的一般方法[J].計算機(jī)世界報,1994, 15:58-65 </p><p>　　[6]王防修,周康.通過哈夫曼編碼實現(xiàn)文件的壓縮與解壓[J].武漢工業(yè)學(xué)院學(xué)　報,2008,1-3</p><p>　　[7]康洪波.靜態(tài)哈夫曼編碼的原理及應(yīng)用[J].河北建筑工程學(xué)院學(xué)報,2009,2-3</p&g

101、t;<p>　　[8]于麗娟.哈夫曼編碼及在數(shù)字電視廣播中的應(yīng)用[J].山西電子技術(shù)報，2005,1-2</p><p>　　[9]王群芳.哈夫曼編碼的另一種實現(xiàn)算法[J].安徽教育學(xué)院學(xué)報,2006,2-3</p><p>　　[10] Introduction to Data Compression, 2nd Edition, Sayood Khalid, 2000.56

102、-87</p><p>　　[11]Jeffrey Scott Vitter，Brown University,Algorithm 673 Dynamic Huffman Coding(October 1988).34-56</p><p>　　[12] Salomon,D A Concise Introduction to Data Compression(March, 2008).23

103、-87</p><p>　　[13] Adaptive Hu?man Compression,AdaptiveHuff.html, Ze-Nian Li, 2006.12-64</p><p>　　[14]Lan H. Witten, Alistair Moffat, Timothy C. Bell, 梁斌(譯), 深入搜索引擎, 北京: 電子工業(yè)出版社, 2009, 44-51, 421

104、-432.</p><p><b>　　附錄</b></p><p>　　1.靜態(tài)哈夫曼編碼對圖像壓縮解壓的實現(xiàn)代碼</p><p><b>　?。?）壓縮主函數(shù)</b></p><p>　　int Huffman_Compression(char * infilename, char * outf

105、ilename)</p><p><b>　　{</b></p><p>　　if ((ifile = fopen (infilename, "rb")) != NULL)</p><p><b>　　{</b></p><p>　　fseek (ifile, 0L, 2);&l

106、t;/p><p>　　file_size = (unsigned long) ftell (ifile); //獲得文件的大小</p><p>　　fseek (ifile, 0L, 0);</p><p>　　Get_frequency_count (); //統(tǒng)計字符頻率</p><p>　　Build_initial_heap (); //

107、建立初始堆</p><p>　　Build_code_tree (); //構(gòu)造編碼樹</p><p>　　if (!Generate_code_table ()) //產(chǎn)生編碼表</p><p><b>　　{</b></p><p>　　printf ("ERROR! Cannot Compress.\n&

108、quot;);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if ((of

109、ile = fopen (outfilename, "wb")) != NULL)</p><p><b>　　{//寫文件頭</b></p><p>　　fwrite (&file_size, sizeof (file_size), 1, ofile);</p><p>　　fwrite (code, 2, 256

110、, ofile);</p><p>　　fwrite (code_length, 1, 256, ofile);</p><p>　　fseek (ifile, 0L, 0);</p><p>　　Compress_image (); //壓縮數(shù)據(jù)</p><p>　　fclose (ofile);</p><p>&

111、lt;b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf("\nERROR: Couldn't create output file %s\n", outfilename);</p&g

112、t;<p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　fclose (ifile);</p><p><b>　　}</b></p>

113、<p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf ("\nERROR: %s -- File not found!\n", infilename);</p><p><b>　　return 0;</b>&