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

李曉飛

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

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

中圖分類號(hào):TN911 文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):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 引 言

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

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

1 靜態(tài)Huffman編碼

1.1 Huffman編碼的原理

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

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

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

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

(2) 在結(jié)點(diǎn)集中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹,且置新的二叉樹的結(jié)點(diǎn)的權(quán)值為其左、右子樹上結(jié)點(diǎn)的權(quán)值之和。

(3) 在結(jié)點(diǎn)集中刪除這兩棵樹,同時(shí)將新得到的二叉樹加入結(jié)點(diǎn)集中。

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

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

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

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

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

1.2 靜態(tài)Huffman編碼壓縮算法的程序?qū)崿F(xiàn)

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

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

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

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

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

(5) 在輸出文件上做標(biāo)記以標(biāo)識(shí)壓縮文件,完成對(duì)原文件的壓縮。

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

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

2 自適應(yīng)Huffman編碼

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

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

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

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

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

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

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

2.2 Huffman編碼的更新

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

欲更改某個(gè)字符的權(quán)值,只要把該字符所對(duì)應(yīng)的葉結(jié)點(diǎn)的權(quán)值增1,接著向上移至其父結(jié)點(diǎn),把其權(quán)值也增1,同樣的處理一直向上直至根結(jié)點(diǎn)。

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

2.3 兩種編碼方法的比較

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

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

3 結(jié) 語

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

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

參考文獻(xiàn)

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

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

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

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

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

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

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