基于Matlab文本文件哈夫曼編解碼仿真

摘 要： 根據當前數據壓縮技術的現狀，論述了Huffman可變長壓縮的編解碼方法。為了驗證Huffman編解碼的具體過程和特點，采用Matlab軟件編程仿真的方法，將優先隊列轉成二叉樹并建立編碼和解碼的字典表。對一隨機英文文本文件進行了Huffman編解碼仿真，得到了各個字母的概率、碼字、平均信息量、平均長度、冗余度以及編碼解碼序列輸出，具有明確的壓縮特點。

關鍵詞： 數據壓縮； Huffman編解碼； Matlab； 二叉樹

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2013）20?0031?02

根據數據的完整度，數據壓縮技術可分為無損壓縮和有損壓縮兩大類。無損壓縮利用數據的統計冗余進行壓縮，可完全恢復原始數據而無任何失真，但壓縮率受到數據統計冗余度的限制，一般為2∶1到5∶1。有損壓縮方法利用了人類對數據中的某些頻率成分不敏感的特性，允許壓縮過程中損失部分對理解原始數據影響較小的信息，以得到較大的壓縮比。實際應用中常用的壓縮方法有脈沖編碼調制、預測編碼、變換編碼、統計編碼等，Huffman編碼是統計編碼中的一種無損壓縮方法[1?2]。

1 Huffman編碼標準

Huffman編碼法是一種無損壓縮方法，是可變字長編碼的一種。在可變字長編碼中，對出現概率大的信號編以字長較短的碼字，對出現概率小的信號編以字長較長的碼字。這種方法完全依據字符出現概率來給不同的信號分配碼字，構造出平均長度最短的編碼，并使編碼的碼字是可辨識的，能夠避免譯碼的二義性或多義性，一般稱之為Huffman編碼[3?4]。Huffman編碼方法較為實用，是消除編碼冗余最常用的技術，一般用來壓縮文本和程序文件。當對信源符號逐個編碼時，能夠給出最短的碼字，編碼和解碼時間較短。信號可以是ASCII碼，也可以是其他形式的信號，如灰度值等。具體實現時，使用一張特殊的編碼表將源字符進行編碼，根據每一個源字符出現的估算概率而建立。

2 Huffman編解碼的過程

產生Huffman編碼要對原始數據掃描兩遍，第一遍掃描要精確地統計出原始數據中每個值出現的頻率，第二遍是建立Huffman樹，并進行編碼。Huffman編碼是最優編碼，效率很高，主要涉及到二叉樹并遍歷二叉樹的算法。

2.1 Huffman編碼的過程

（1）將消息按照出現概率大小從大到小排列，記為：[p1≥p2≥…≥pm-1≥pm]。

（2）給最小的概率[pm]賦予符號1，倒數第二小的概率[pm-1]賦予符號0。

（3）計算聯合概率[pi=pm+pm-1]，將未處理的m-2個概率與[pi]一起重新排序。

（4）重復步驟（1）～步驟（3），直到所有的概率都被賦予了一個符號為止[1]。

2.2 Huffman樹的構造與實現

要構造Huffman編碼，需要構造Huffman樹，即最優樹。Huffman算法過程如下：

（1）根據給定的n個概率（或頻率）構造一個集合[F=f1，f2，…，fn]，同時這n個值對應樹T的n個結點，置[i=n+1]。

（2）在集合F中選擇兩個最小的值求和作為[fi]加入集合F中；在樹T中構造一結點，使得該結點是兩最小值對應結點的父結點。

（3）在集合F中刪除兩最小值，并置[i=i+1]。

（4）重復（2）和（3），直到[i=2n-1]或集合F只有一個元素為止。這樣形成的一棵樹就是Huffman樹（最優樹）。

對一個經過Huffman編碼的文件進行解碼，首先構造相應的Huffman樹，然后按位從文件讀入數據流，查找Huffman樹，即可得到相應編碼所對應的字符，從而解碼文件。

2.3 Matlab仿真算法

在Matlab中實現Huffman算法，可用一個矩陣來表示Huffman樹，該矩陣的含義如表1所示。

表1 Huffman算法數據結構

3 文本文件的Huffman編解碼仿真

ASCII碼是用8位表示一個字符，方法簡單易于理解，是常用的計算機字符表示方法。在信息傳輸領域，字符出現的頻率不同，若用傳統方法表示數據，則冗余度大，如果用Huffman方法表示字符，頻率出現高的字符用較短的編碼表示，頻率出現低的字符用較長的編碼表示，則可以使得數據量減少。在具體的英文文本中，對于各個字母出現概率的準確估算，就可以大幅度提高無損壓縮的比例。Matlab可以應用于科學計算、控制系統設計與分析、數字信號處理、數字圖像處理、通信系統仿真與設計等領域，專門以矩陣的形式處理數據，功能強大[5?6]。

采用Matlab軟件，對一個輸入的文本進行Huffman編解碼編程仿真。輸入文本字符為“ABCADDDEEFFHHACCAAGGGCCCACCCAAABBBAACCKKKWWWCBBBLLYY”，運行結果如下：

4 結 語

文本文件的Huffman壓縮是靜態Huffman編碼，使用一棵在壓縮之前就建好的編碼樹，它是根據可能的字符出現的概率表來生成的。采用Huffman編碼要注意錯誤傳播的產生，原因是沒有錯誤保護功能，而且很難隨意查找或調用壓縮文件中的內容。

參考文獻

[1] 章毓晉.圖像工程（上冊）：圖像分析和處理[M].北京：清華大學出版社，2002.

[2] 徐飛，施曉紅.Matlab應用圖像處理[M].西安：西安電子科技大學出版社，2003.

[3] 陳天華.數字圖像處理[M].北京：清華大學出版社，2007.

[4] 高成.Matlab圖像處理與應用[M].北京：國防工業出版社，2007.

[5] 陳杰.Mmatlab寶典[M].北京：電子工業出版社，2008.

[6] 張威.Matlab基礎與編程入門[M].西安：西安電子科技大學出版社，2004.