Huffman編解碼及其快速算法研究

李曉飛

摘 要:Huffman壓縮編碼是一種較好的變長前綴碼,它由D.A.Huffman于1952年發(fā)明。Huffman編碼作為一種高效而簡單的可變長編碼而被廣泛應用于信源編碼等方面。介紹了基本的Huffman編碼算法,并針對其缺點,提出了動態(tài)Huffman編碼算法,改進算法對數(shù)據進行編碼的依據是動態(tài)變化的Huffman樹。

關鍵詞:Huffman編碼;數(shù)據壓縮;Huffman樹;優(yōu)化算法

中圖分類號:TN911 文獻標識碼:A

文章編號:1004-373X(2009)21-102-03

Huffman Codec and Its Fast Algorithm

LI Xiaofei

(Shaanxi Railway Institute,Weinan,714000,China)

Abstract:Huffman coding is a good variable-length prefix code,invented by D.A.Huffman in 1952.Huffman coding as an efficient and simple variable-length coding has been widely used in areas such as source coding.The basic Huffman coding algorithm is introduced,and for its shortcomings,dynamic Huffman coding algorithm is introduced,improved algorithm to encode the data is based on dynamic changes of the Huffman tree.

Keywords:Huffman coding;data compression;Huffman tree;optimization algorithm

0 引 言

隨著科技與經濟的迅速發(fā)展,海量的數(shù)據進入了人們的生活。20年前,以兆字節(jié)為單位的存儲要求也是異想天開的事情。可是現(xiàn)在,隨著大容量存儲設備的迅速發(fā)展,即使對于個人用戶來說,存儲上千兆字節(jié)的數(shù)據也很平常,并且離太字節(jié)的存儲量也不再遙遠。如何正確而迅速的處理和保存這些數(shù)據就成為計算機科學中亟待解決的一大問題。因此,數(shù)據壓縮技術已經成為計算機科學的主要分支。所謂數(shù)據壓縮,實際上就是對需要壓縮的數(shù)據對象進行某種可逆性編碼,使編碼的總長度小于原數(shù)據的總長度,從而達到減小數(shù)據總長度的目的。數(shù)據壓縮的關鍵在于編碼,編碼就是基于由模型提供的概率分布來確定符號的輸出表達方式。對于以數(shù)據壓縮為目的的編碼,一般的想法是對于常見的符號,編碼器輸出較短的碼字;而對于少見的符號則用較長的碼字表示[1]。

自1952年提出Huffman編碼以來,在過去的50年中,Huffman算法一直得到國內外相關領域學者的關注,并取得了許多重要的進展。隨著信息技術的發(fā)展,Huffman編碼作為高效的無損壓縮的重要方法正日益廣泛地在文本、圖像、視頻壓縮及通信、密碼等領域得到應用。

1 靜態(tài)Huffman編碼

1.1 Huffman編碼的原理

Huffman編碼是一種變長度編碼方法,只要給定符號的概率分布,Huffman編碼算法就能夠計算出給定字符的代碼。對于給定概率分布的無前綴代碼,產生的碼字可實現(xiàn)很好的壓縮效果。Huffman編碼通過從底向頂構造解碼樹來解碼。其編碼算法為每一個符號創(chuàng)造一個包含了這個符號和概率值的葉結點(見圖1),然后把具有最小概率值的兩個葉結點排列在同一個父結點下,成為兄弟結點,父結點的概率值等于兩個子結點的概率值之和(見圖2)。

忽略已連接的子結點,選擇兩個具有最小概率值的子結點重復進行連接操作。例如,A與B已連接生成新的結點,下一步就是要把這個新的結點與結點C連接起來,產生一個概率為P=0.20的結點。將這個過程重復下去,直到只有一個結點沒有父結點為止,這個結點即成為解碼樹的根(見圖3)。那么,兩個沒有葉結點的分支就被標記為0和1(順序并不重要)從而形成樹。

生成Huffman樹的具體步驟如下:

(1) 根據給定的n個權值為W1,W2,…,Wj 構成n棵二叉樹的集合F={T1,T2,…,Tn),其中每棵二叉樹T1中只有一個帶權為Wi的根結點,其左右子樹均空。

(2) 在結點集中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹,且置新的二叉樹的結點的權值為其左、右子樹上結點的權值之和。

(3) 在結點集中刪除這兩棵樹,同時將新得到的二叉樹加入結點集中。

(4) 重復步驟(2)和(3),直到結點集中只含一棵樹為止,這棵樹便是Huffman樹。

生成Huffman樹之后,在樹的左右分枝上賦值1和0即可得到Huffman編碼。

由于Huffman樹中沒有度為1的結點,一棵有n個葉子結點的Huffman樹共有2n-1個結點,可以以一個大小為2n-1的向量表示。由于在構成Huffman樹之后,為求得編碼,需從葉子結點出發(fā)走一條從葉到根的路徑;而為譯碼需從根出發(fā)走一條從根到葉子的路徑。則對每個結點而言,既需知道其雙親的信息,又需知道其子結點的信息。

譯碼的過程是,分解原文中字符串,從根結點出發(fā),按字符‘0或‘1確定訪問子結點的路徑,直至葉結點,便求得該子串相對應的字符。

在Huffman編碼過程中,當出現(xiàn)2個以上最小概率的結點時,若選擇樹中葉結點概率為最小者與葉結點概率為最大者進行合并,則得到相應編碼的平均偏離方差為最小(注:定理的逆定理不真)。上述的Huffman編碼是利用壓縮對象出現(xiàn)頻率的不等性進行編碼的一種常用的無損數(shù)據壓縮方法。不論從算法的復雜度還是在實現(xiàn)的難度以及對數(shù)據壓縮的效果來看,Huffman編碼都不失為一種較好的數(shù)據壓縮算法。

1.2 靜態(tài)Huffman編碼壓縮算法的程序實現(xiàn)

以下步驟是實現(xiàn)的靜態(tài)Huffman編碼的壓縮和解壓縮算法。

(1) 掃描原文件的全部數(shù)據,完成字符出現(xiàn)概率的統(tǒng)計。

(2) 依據字符概率建立Huffman樹。

(3) 將Huffman樹的信息寫入輸出文件(壓縮后文件),以備解壓縮時使用。

(4) 進行第二遍掃描,將原文件所有字符轉化為Huffman編碼,并以ASCII字符形式保存到輸出文件。

(5) 在輸出文件上做標記以標識壓縮文件,完成對原文件的壓縮。

該程序的算法源于靜態(tài)Huffman編碼的經典思想。即壓縮時,首先掃描原文件的全部數(shù)據,生成字符(ASCII字符)頻率表。然后構造Huffman樹并生成與字符相對應的不等長編碼。再將生成的Huffman編碼轉換為字符寫入文件中。最后,將文件結尾倒數(shù)第五個字符標記為“H”,以標識壓縮后的文件。解壓縮時,將Huffman編碼做逆變換后寫入文件即可。

在數(shù)據通訊中,各碼字的平均偏離方差直接影響到接收端的預留數(shù)據緩沖器的容量。當編碼器經通信線路傳送壓縮數(shù)據流時,平均偏離方差很小的Huffman編碼近似于恒定速度把每位編碼送入緩沖器,增加了數(shù)據傳輸?shù)臏蚀_度,同時也只需很小容量的緩沖器即可;平均偏離方差很大時,將使導入編碼的輸出碼率不斷變化,使每位編碼進入緩沖器的速度不恒定,產生錯誤碼的機率隨之增大,同時也需要較大容量的緩沖器。

2 自適應Huffman編碼

上述的Huffman編碼是利用壓縮對象出現(xiàn)頻率的不等性進行編碼的一種常用的無損數(shù)據壓縮方法。不論從算法的復雜度還是在實現(xiàn)的難度以及對數(shù)據壓縮的效果來看,Huffman編碼都不失為一種較好的數(shù)據壓縮算法。

Huffman編碼假定壓縮器事先知道字母表中所有符號出現(xiàn)的概率。而實用中,符號出現(xiàn)的頻率絕少能預知。一個解決方法就是讓壓縮器讀兩次原始數(shù)據,第一次只是計算各符號的出現(xiàn)頻率,第二次才壓縮數(shù)據。在兩次處理之間,壓縮器構造Huffman樹,這種方法稱為半自適應的,但通常慢得無法實用,實用方法是自適應Huffman編碼。

針對靜態(tài)Huffman編碼的上述缺點,提出了動態(tài)Huffman編碼的算法。改進算法對數(shù)據進行編碼的依據是動態(tài)變化的Huffman樹,也就是說對第t+1個字符的編碼是根據原數(shù)據中前t個字符得到的Huffman樹來進行的。壓縮和解壓子程序具有相同的初始化樹,每處理完一個字符,壓縮和解壓縮使用相同的算法修改Huffman樹。動態(tài)Huffman編碼算法克服了傳統(tǒng)Huffman編碼必須對文本進行兩遍掃描的缺點,壓縮效率大幅度提高。尤其對一些龐大的原文件而言,壓縮和解壓效率可以提高一倍至三倍。

2.1 首次出現(xiàn)字符的處理

在動態(tài)Huffman編碼中,第i個字符的編碼是通過前i-1個字符所構成的Huffman樹來求得的,哪些字符會出現(xiàn)事先無法知道,因此,當某個字符首次出現(xiàn)時,因它不在Huffman樹中,無法對它進行編碼,解決此問題的一個方法是,簡單地將Huffman樹初始化為權值為1的256個所有可能出現(xiàn)的碼字符。這樣,開始時每個字符的編碼都是8位長,隨著字符出現(xiàn)次數(shù)的增加,其編碼位數(shù)將隨之減少。但是,這在多數(shù)情況下會造成存儲空間的浪費,降低數(shù)據壓縮效果。為此,引入一個虛設的特殊字符‘KEY,用它來代替第一次出現(xiàn)的字符。當某個字符首次出現(xiàn)時,就用‘KEY所在的結點位置對它進行編碼,并把編碼寫進目標文件。接著,把首次出現(xiàn)的字符的ASCII碼值也寫進目標文件。這樣,就完成了首次出現(xiàn)字符的壓縮處理。隨后,要改變Huffman樹的結構,讓‘KEY代替下一個首次出現(xiàn)的字符。假定原先Huffman樹的結構如圖4(a)所示,當有一個字符首次出現(xiàn)時,就增加兩個葉結點,它們分別作為‘KEY所在結點的左、右孩子。左孩子存放首次出現(xiàn)的字符,并令其權值為0,右孩子存放‘KEY,其權值仍為1,改變后的Huffman樹如圖4(b)所示。

圖4 首次出現(xiàn)的字符處理示意圖

同樣地,在解壓過程中,當還原出來的字符為‘KEY時,說明當時壓縮的這個字符是首次出現(xiàn)的,接著往下連續(xù)讀出8位(一個字符長),該字符就是所壓的首次出現(xiàn)的字符。隨后,使用與上述壓縮過程中改變Huffman樹結構的同樣算法來改變Huffman樹結構。

2.2 Huffman編碼的更新

在動態(tài)Huffman編碼中,第i+1個字符的壓縮是由第i個字符壓縮后所構成的Huffman樹確定的。因此,每當壓縮完一個字符,要隨之更新Huffman樹,它主要由權值的更改和調整兩個步驟實現(xiàn)。

欲更改某個字符的權值,只要把該字符所對應的葉結點的權值增1,接著向上移至其父結點,把其權值也增1,同樣的處理一直向上直至根結點。

Huffman樹有一個重要的特性:樹中任一個結點(根結點除外)的權值都小于或等于它上面任一結點的權值,并與它的兄弟相鄰。當樹中某個結點權值改變時,可能破壞這一特性。此時,就必須進行調整,使之仍為一棵真正的Huffman樹。但是,權值改變未必破壞這一特性,因此這一步驟并不總是每次要執(zhí)行。當某個結點的權值改變后,只要把當前結點的權值與它前一個結點的權值進行比較,若前者大于后者,則需要調整;否則不必調整。為了減少調整的工作量,向上查找,找到某權值小于當前結點的最遠的一個結點,它就是所求的被交換結點,把當前結點與所求結點連同它們的左右子樹(如果有的話)進行交換,就得到一棵正確有序的Huffman樹。

2.3 兩種編碼方法的比較

下面對靜態(tài)Huffman編碼和動態(tài)Huffman編碼方法稍作比較。靜態(tài)Huffman編碼的缺點在于需對原始數(shù)據進行兩遍掃描第一遍掃描統(tǒng)計字符出現(xiàn)頻率并建樹,第二遍掃描根據所建Huffman樹進行編碼由此,在壓縮時,將會降低壓縮速度同時,為保存Huffman樹以供解壓時用,也將浪費一部分存儲空間經驗證明,由于靜態(tài)建樹,其壓縮率也有所下降。

如前所述,動態(tài)Huffman編碼對數(shù)據的壓縮是依據動態(tài)變化的Huffman編碼樹,亦即對第i+1個字符的編碼是由原始數(shù)據中前i個字符所建立的Huffman樹確定的壓縮和解壓子程序具有相同的初始化樹,每處理完一個字符,壓縮和解壓使用相同的算法更新Huffman樹,不必為解壓而保存Huffman樹的有關信息,從而提高了數(shù)據壓縮率。而且,由于只要一遍掃描就可完成壓縮和解壓處理,大大提高了壓縮速度。但是,由于解壓時采用與壓縮時相同方法建樹,增加了解壓時間,從而降低了還原速度。而靜態(tài)Huffman編碼由于對Huffman樹進行保存,還原時不必重新建樹,節(jié)省了還原時間。應用所設計的壓縮程序對多種類型的文件進行壓縮并就壓縮率加以比較,從而發(fā)現(xiàn)此壓縮程序對文本文件的壓縮率較高,對可執(zhí)行文件等非文本文件的壓縮率相對較低而且壓縮率與文件長度有關,文件較長時其壓縮率也隨之下降,這正是動態(tài)Huffman編碼數(shù)據壓縮技術相對于其他壓縮技術的一個缺點。

3 結 語

數(shù)據壓縮是計算機科學中非常具有生命力的論題。一個好的數(shù)據壓縮方法往往能夠明顯減少數(shù)據的存儲空間,大大提高存儲媒體的訪問速度。

Huffman編碼是數(shù)據壓縮領域中最著名的編碼方式之一。它通過對象頻率出現(xiàn)的不等性,構造最優(yōu)編碼,達到減小文件大小的目的。目前廣泛應用的許多其他高效的數(shù)據壓縮算法(如算術編碼,可預測編碼等) 也是在Huffman編碼的基礎上發(fā)展起來的。所以,研究Huffman編碼的思想,對于深入理解數(shù)據結構、程序設計等學科中的相關課題是十分有益的。特別是對動態(tài)Huffman編碼算法的探索,盡可能使程序穩(wěn)定、快速、高效地運行,充分體現(xiàn)了對軟件時空需求進行優(yōu)化與權衡的思想,這也是現(xiàn)代軟件工程中十分重視的核心問題。

參考文獻

[1]朱懷宏,吳楠,夏黎春.利用優(yōu)化Huffman編碼進行數(shù)據壓縮的探索.微機發(fā)展,2004(6):1-6.

[2]Manoj Aggurwul,Ajui Nuruyun.Efficient Huffman Decoding.Applied Physics Letters,2000.

[3]張全伙,于洪斌,林榆.優(yōu)化Huffman編碼數(shù)據壓縮技術及程序實現(xiàn).華僑大學學報:自然科學版,1995(3):19-22.

[4]李偉生,李域,王濤.一種不用建造Huffman樹的高效Huffman編碼算法[J].中國圖像圖形學報,2005(3):18-21.

[5]劉金嶺,劉國香.Huffman編碼的優(yōu)化.河北師范大學學報:自然科學版,2006,30(1):29-32.

[6]林建英,伍勇,李建華,等.一種易于硬件實現(xiàn)的快速自適應Huffman編碼算法.大連理工大學學報,2008,48(3):436-440.

[7]包爾固德,李偉生.一種基于濃縮Huffman表的Huffman算法的研究與實現(xiàn).微電子學與計算機,2007(11):31-33.