哈夫曼編碼的實現及應用論文
畢 業 設 計(論文)
題目 哈夫曼編碼的實現
及應用
二級學院 數學與統計學院
專 業 信息與計算科學
班 級
學生姓名 張澤欣 學號
指導教師 職稱
時 間
目錄
摘要I
AbstractII
第一章 緒論1
1.1 研究目的及意義1
1.2 圖像壓縮編碼技術概述2
1.2.1 圖像壓縮編碼技術分類2
1.2.2 圖像壓縮編碼評價2
1.3 哈夫曼編碼簡介3
1.4 本設計所做的主要工作4
第二章 利用靜態哈夫曼編碼實現圖像壓縮5
2.1 靜態哈夫曼編碼介紹5
2.2 靜態哈夫曼編碼樹的構造6
2.3 靜態哈夫曼編碼的具體編碼過程6
2.4 靜態哈夫曼編碼的算法實例7
2.3 利用靜態哈夫曼編碼壓縮與還原圖像的C語言實現9
2.3.1 壓縮的實現9
2.3.2 解壓縮的實現11
2.4 圖象壓縮實例12
第三章 利用動態哈夫曼編碼實現圖像壓縮15
3.1 動態哈夫曼編碼的提出15
3.2 動態哈夫曼編碼的原理15
3.3 動態哈夫曼編碼的算法思想16
3.4 動態哈夫曼編碼的編碼實例18
3.5 利用動態哈夫曼編碼壓縮與還原圖像的C語言實現25
3.5.1 數據結構25
3.5.2 壓縮的實現26
3.5.3 解壓縮的實現27
3.6 圖像壓縮實例28
3.7 靜態哈夫曼編碼與動態哈夫曼編碼的比較29
第四章 對哈夫曼編碼的改進31
4.1 在哈夫曼編碼中引入堆排序31
4.2 模擬哈夫曼樹的創建32
第五章 總結34
5.1 總結34
參考文獻35
附錄36
摘要
哈夫曼編碼是一種以哈夫曼樹—即最優二叉樹為核心的編碼方式，經常應用于數據壓縮。在計算機信息處理中，“哈夫曼編碼”是一種一致性編碼法(又稱"熵編碼法")，用于數據的無損壓縮。"熵編碼法"是指使用一張特殊的編碼表將源字符(例如某文件中的一個符號)進行編碼。這張編碼表的特殊之處在于，它是通過統計每一個源字符出現的概率建立起來的(出現概率高的字符使用較短的編碼，反之出現概率低的則使用較長的編碼，這使得編碼之后的字符串的平均長度是最短的，從而達到無損壓縮數據的目的)。論文全面分析了靜態哈夫曼編碼和動態哈夫曼編碼算法算法，詳細介紹了靜態哈夫曼編碼樹和和動態哈夫曼編碼樹的構造方案，并針對這兩種算法，給出了對應的C 語言代碼。經運行分析發現，由于在構造靜態哈夫曼樹時，大量的時間消耗在從元素集合中選取兩個最小的元素上。而動態哈夫曼編碼算法，雖然克服了前者的缺點，但是算法復雜，而且解壓縮時間長。因此，根據字符編碼的單值性，對哈夫曼編碼做了第二個改進，即不構造哈夫曼樹，而是用一個二維數組模擬哈夫曼樹的創建過程并得到各字符的編碼，這一改進有效地提高了壓縮比。
關鍵詞：靜態哈夫曼編碼，壓縮，節點，哈夫曼樹
Abstract
Huffman 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 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 special because it is the statistical probability of occurrence of each source character set (high probability of occurrence of the character using a shorter encoding, on
