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

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

2、班 級(jí) </p><p>　　學(xué)生姓名 學(xué)號(hào) </p><p>　　指導(dǎo)教師 職稱 </p><p>　　時(shí) 間 </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 圖像壓縮編碼評(píng)價(jià)2</p><p>　　1.3 哈夫曼編碼簡(jiǎn)介3</p><p>　　1.4 本設(shè)計(jì)所做的主要工作4</p><p>　　第二章 利用靜態(tài)哈夫曼編碼實(shí)現(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)哈夫曼編碼的具體編碼過(guò)程6</p><p>　　2.4 靜態(tài)哈夫曼編碼的算法實(shí)例7</p><p>　　2.3 利用靜態(tài)哈夫曼編碼壓縮與還原圖像的C語(yǔ)言實(shí)現(xiàn)9</p><p>　　2.3.1 壓

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

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

8、.3 解壓縮的實(shí)現(xiàn)27</p><p>　　3.6 圖像壓縮實(shí)例28</p><p>　　3.7 靜態(tài)哈夫曼編碼與動(dòng)態(tài)哈夫曼編碼的比較29</p><p>　　第四章 對(duì)哈夫曼編碼的改進(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ì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱"熵編碼法"），用于數(shù)據(jù)的無(wú)損壓縮。"熵編碼法"是指使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號(hào)）進(jìn)行編碼。這張編碼表的特殊之處在于，它是通過(guò)統(tǒng)計(jì)每一個(gè)源字符出現(xiàn)的概率建立起

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

12、算法復(fù)雜，而且解壓縮時(shí)間長(zhǎng)。因此，根據(jù)字符編碼的單值性，對(duì)哈夫曼編碼做了第二個(gè)改進(jìn)，即不構(gòu)造哈夫曼樹，而是用一個(gè)二維數(shù)組模擬哈夫曼樹的創(chuàng)建過(guò)程并得到各字符的編碼，這一改進(jìn)有效地提高了壓縮比。</p><p>　　關(guān)鍵詞：靜態(tài)哈夫曼編碼，壓縮，節(jié)點(diǎn)，哈夫曼樹</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>　　從信息論角度看，信源編碼的一個(gè)最主要的目的，就是要解決數(shù)據(jù)的壓縮問(wèn)題。</p><p>　　數(shù)據(jù)壓縮是指以最少的代碼表示信源所發(fā)出的信號(hào)，減少容納給定信息集合或數(shù)據(jù)采樣集合的信號(hào)空間。圖像編碼與壓縮的目的就是對(duì)圖像數(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ù)的存儲(chǔ)和處理是一個(gè)難題。如不進(jìn)行編碼壓縮處理，一張存6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

72、T 節(jié)點(diǎn)的編碼樹作為初始狀態(tài)，然后根據(jù)哈夫曼編碼數(shù)據(jù)流，對(duì)符號(hào)進(jìn)行還原。每次處理完一個(gè)符號(hào)，就使用這個(gè)符號(hào)調(diào)整編碼樹。這樣，在每一次輸入新的符號(hào)之前，哈夫曼樹都處于與進(jìn)行編碼時(shí)使用的哈夫曼樹完全相同的狀態(tài)，保證了解碼的正確性。</p><p>　　3.5 利用動(dòng)態(tài)哈夫曼編碼壓縮與還原圖像的C語(yǔ)言實(shí)現(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、每個(gè)字符在哈夫曼樹中葉子結(jié)點(diǎn)的位置，它被初始化為-1；next_free_node 指明首次出現(xiàn)的字符插入哈夫曼樹中的位置；weight 指明每個(gè)結(jié)點(diǎn)的權(quán)值；parent 指明該結(jié)點(diǎn)的父結(jié)點(diǎn)位置；child_is_leaf 指明該結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)，若是則置child_is_leaf = 0；若不是則置child_is_leaf = 1；child指明該結(jié)點(diǎn)是葉結(jié)點(diǎn)，則葉子上存放字符的值，否則指明該結(jié)點(diǎn)左孩子的位置，其右孩子的位置是ch

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

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

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

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

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

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

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

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

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

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

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

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

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

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

90、想，沒(méi)有必要構(gòu)造哈夫曼樹，用一個(gè)二維數(shù)組就可以模擬哈夫曼樹的創(chuàng)建過(guò)程并得到各字符的編碼。實(shí)現(xiàn)思想如下：</p><p>　　先統(tǒng)計(jì)每個(gè)編碼長(zhǎng)度Ni (二叉樹上的Ni 層) 上對(duì)應(yīng)數(shù)據(jù)的數(shù)目，再分別對(duì)Ni 層上的符號(hào)以遞增順序分配編碼。最底層編碼從0 開(kāi)始， 第Ni 層第一個(gè)編碼為下一層最后一個(gè)編碼的左邊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ù)上述實(shí)現(xiàn)思想，字符F，G，C，D，E，A，B的編碼分別為0000，0001，0010，0011，010，011，10，11。顯

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

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

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

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

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

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

98、的提升自我，鍛煉了我各個(gè)方面的能力，讓我受益匪淺，而且私下里同學(xué)的幫助也是很多的，要感謝xx同學(xué)在論文修改方面提出的各方面建議，再要感謝xx同學(xué)提供的技術(shù)支持，現(xiàn)在真正理解了啥叫眾人拾柴火更旺的道理，這篇論文的制作讓我在各個(gè)方面都收獲了不少。</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è)計(jì)與實(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]吳樂(lè)南. 數(shù)據(jù)壓縮(第一版)[M].北京:電子工業(yè)出版社,200

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

101、t;<p>　　[8]于麗娟.哈夫曼編碼及在數(shù)字電視廣播中的應(yīng)用[J].山西電子技術(shù)報(bào)，2005,1-2</p><p>　　[9]王群芳.哈夫曼編碼的另一種實(shí)現(xiàn)算法[J].安徽教育學(xué)院學(xué)報(bào),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)哈夫曼編碼對(duì)圖像壓縮解壓的實(shí)現(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)計(jì)字符頻率</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>&