王防修，劉春紅

(1.武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北 武漢 430023；2.鄂鋼馳久鋼板彈簧有限責(zé)任公司，湖北 鄂州 436000)

?

基于哈夫曼編碼的選擇算法

王防修1，劉春紅2

(1.武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北 武漢 430023；2.鄂鋼馳久鋼板彈簧有限責(zé)任公司，湖北 鄂州 436000)

摘要：針對(duì)同一哈夫曼樹有多種不同哈夫曼編碼的問題，提出一種哈夫曼編碼的選擇算法。算法以哈夫曼編碼的多樣性為基礎(chǔ)，在哈夫曼樹的非葉子節(jié)點(diǎn)處提供編碼方式0或1，由所有非葉子節(jié)點(diǎn)的編碼方式組成一個(gè)二進(jìn)制序列，最后根據(jù)該二進(jìn)制序列進(jìn)行節(jié)點(diǎn)的哈夫曼編碼。鑒于哈夫曼編碼的遞歸子結(jié)構(gòu)，設(shè)計(jì)了一種不同于傳統(tǒng)哈夫曼編碼的回溯算法。算例仿真表明，一方面同一事件有時(shí)可以構(gòu)造不同的哈夫曼樹，另一方面同一哈夫曼樹根據(jù)編碼方式的不同可以得到不同的哈夫曼編碼結(jié)果。

關(guān)鍵詞：哈夫曼樹；哈夫曼編碼；選擇算法；回溯算法；遞歸子結(jié)構(gòu)

1引言

作為一種無損壓縮編碼，哈夫曼編碼比其他編碼具有更高的壓縮效率[1]。常見的哈夫曼編碼，是先建立哈夫曼樹，然后由哈夫曼樹得到哈夫曼編碼[2-4]。按照現(xiàn)有的哈夫曼編碼算法[5-6]，只能得到兩種編碼結(jié)果中的一種。然而，根據(jù)哈夫曼樹的結(jié)構(gòu)和所采用的編碼方式，應(yīng)該存在更多的編碼結(jié)果。因此，對(duì)一個(gè)具體事件的哈夫曼樹而言，究竟可以得到多少不同的編碼結(jié)果，該問題的研究尚未見之于文獻(xiàn)。此外，實(shí)現(xiàn)哈夫曼編碼不同結(jié)果的任意選擇，也是需要解決的問題。針對(duì)這兩個(gè)問題，本文一方面需要從理論上證明由同一哈夫曼樹可以得到不同的編碼結(jié)果，另一方面需要設(shè)計(jì)為得到不同哈夫曼編碼結(jié)果的選擇算法。

2哈夫曼編碼不唯一

對(duì)同一事件進(jìn)行哈夫曼編碼，雖然編碼的平均碼長是唯一的，但哈夫曼編碼的結(jié)果不唯一[1]。具體原因表現(xiàn)在以下兩個(gè)方面：(1)同一事件的哈夫曼樹可能不唯一；(2)同一哈夫曼樹的編碼方式不唯一。

定理 如果編碼事件包含n個(gè)權(quán)重，則該事件對(duì)應(yīng)的哈夫曼樹有2n-1種不同的哈夫曼編碼結(jié)果。

證明 因?yàn)榫幋a事件有n個(gè)權(quán)重，故相應(yīng)的哈夫曼樹總共有2n-1個(gè)節(jié)點(diǎn)。除了n個(gè)葉子節(jié)點(diǎn)沒有孩子節(jié)點(diǎn)外，其他n-1個(gè)非葉子節(jié)點(diǎn)均有兩個(gè)孩子節(jié)點(diǎn)。對(duì)每個(gè)非葉子節(jié)點(diǎn)而言，如果對(duì)指向左孩子的分支編碼為0，由前綴碼[1]可知指向右孩子的分支編碼必須為1；相反，如果指向左孩子的分支編碼為1，則指向右孩子的分支編碼必須為0。也就是說，從每個(gè)非葉子節(jié)點(diǎn)出發(fā)，都有兩種編碼方式。由于有n-1個(gè)非葉子節(jié)點(diǎn)而這些節(jié)點(diǎn)又是相互獨(dú)立的，故由排列組合可知，總共有2n-1種不同的編碼結(jié)果。

總之，對(duì)同一事件編碼，不同哈夫曼樹的哈夫曼編碼結(jié)果不同，而同一哈夫曼樹按不同的編碼方式也可以得到不同的哈夫曼編碼結(jié)果。如果同一事件可以構(gòu)造m棵不同的哈夫曼樹，由每棵哈夫曼樹有2n-1種不同編碼結(jié)果，則總共就有2n-1m種不同編碼結(jié)果。

3哈夫曼編碼的選擇算法原理

一個(gè)事件的哈夫曼編碼不僅與建立的哈夫曼樹有關(guān)，而且與采用的編碼方式有關(guān)。為方便起見，一般常采用以下兩種編碼方式：(1)所有非葉子節(jié)點(diǎn)指向左孩子的分支統(tǒng)一編碼為0，指向右孩子的分支統(tǒng)一編碼為1；(2)所有非葉子節(jié)點(diǎn)指向左孩子的分支統(tǒng)一編碼為1，而指向右孩子的分支統(tǒng)一編碼為0。

故由以上兩種編碼方式只能得到兩種編碼結(jié)果，而無法得到哈夫曼編碼的其他任何一種結(jié)果。如果想得到其他哈夫曼編碼結(jié)果，則必須改變分支的編碼方式，也就是必須對(duì)非葉子節(jié)點(diǎn)分支的編碼方式能夠任意選擇，即從哈夫曼樹的根節(jié)點(diǎn)出發(fā)，對(duì)樹中的每個(gè)非葉節(jié)點(diǎn)分支的編碼方式不是統(tǒng)一規(guī)定而是逐個(gè)規(guī)定。具體做法是：在哈夫曼樹的遍歷過程中，每遇到一個(gè)非葉子節(jié)點(diǎn)，則為其提供一個(gè)0或1的整數(shù)。如果該整數(shù)是0，則表示當(dāng)前非葉子節(jié)點(diǎn)指向左孩子的分支編碼為0，指向右孩子的分編碼為1；否則，如果提供的整數(shù)是1，則當(dāng)前非葉子節(jié)點(diǎn)指向左孩子的分支編碼為1，指向右孩子的分編碼為0?？傊鲜鲞x擇編碼方式要求對(duì)每個(gè)非葉子節(jié)點(diǎn)的分支編碼方式都要依次規(guī)定。

總之，一個(gè)n-1位二進(jìn)制數(shù)對(duì)應(yīng)一種哈夫曼編碼結(jié)果，不同的n-1位二進(jìn)制數(shù)對(duì)應(yīng)不同的哈夫曼編碼結(jié)果。只要產(chǎn)生不同的n-1位二進(jìn)制數(shù)，就可以得到不同的哈夫曼編碼結(jié)果。

4哈夫曼編碼的選擇算法實(shí)現(xiàn)

要實(shí)現(xiàn)某一事件的哈夫曼編碼，必須首先建立哈夫曼樹，然后根據(jù)建立的哈夫曼樹進(jìn)行哈夫曼編碼。

4.1哈夫曼樹建立

為了說明編碼事件的哈夫曼樹有可能不唯一，不妨將哈夫曼樹的構(gòu)造過程描述如下：

(1) 設(shè)wi(i=1,2,…,n)是給定的n個(gè)權(quán)重,由這些權(quán)重構(gòu)成n棵二叉樹的對(duì)應(yīng)集合為T={ti|i=1,2,…,n},其中ti的權(quán)重為ti.weight=wi,而ti的左右孩子滿足ti.lchild=ti.rchild=∧。

(2) 從T中選取權(quán)重最小的兩棵二叉樹tl和tr,即tl和tr分別滿足

tr.weight=min{t.weight|t∈T}.

(1)

tr.weight=min{t.weight|t∈T-{tl}}.

(2)

(3) 構(gòu)造一棵根節(jié)點(diǎn)為s而左右孩分別為tl和tr的新的二叉樹,其中s是兩個(gè)孩子的全重之和,即

s.lchild=tl,s.rchild=tr.

(3)

s.weight=tl.weight+tr.weight.

(4)

(4) 從集合T中刪除節(jié)點(diǎn)tl和節(jié)點(diǎn)tr,向集合T中增加節(jié)點(diǎn)s,即

T=T-{tl,tr}.

(5)

T=T+{s}.

(6)

(5)如果T≠{s},則轉(zhuǎn)步驟(2);否則,構(gòu)造過程結(jié)束,二叉樹s就是一棵哈夫曼樹。

從上述算法中可以發(fā)現(xiàn),新生成二叉樹的根節(jié)點(diǎn)的權(quán)重有可能與原集合T中的某棵二叉樹的根節(jié)點(diǎn)的權(quán)重相等,如果存在這種情況,并且在選擇最小權(quán)重的節(jié)點(diǎn)時(shí)只能是其中之一,那到底是選擇前者還是選擇后者呢。如果選擇前者,則得到的哈夫曼編碼的碼長變化較小。反之,如果選擇后者, 則碼長變化較大。之所以會(huì)出現(xiàn)這種情況,是由于構(gòu)造的二叉樹不同所致。

4.2哈夫曼編碼的選擇算法

有了哈夫曼樹后,依據(jù)該哈夫曼樹就可以進(jìn)行哈夫曼編碼了。現(xiàn)有的哈夫曼編碼算法很多,不外乎遞歸或非遞歸算法。此處,不妨設(shè)計(jì)一個(gè)尚未見之于文獻(xiàn)的回溯算法。

設(shè)bi(i=1,2,…,n)是存儲(chǔ)權(quán)重wi的二進(jìn)制編碼，S=s1s2…sn-1是一個(gè)n-1位的二進(jìn)制數(shù)。如果用遞歸函數(shù)f(t)實(shí)現(xiàn)回溯編碼,則f(t)表示由t的雙親到t的編碼過程。若用c保存遞歸過程的中間編碼,則由當(dāng)前編碼c到t的編碼必須滿足:

如果t是深度優(yōu)先搜索的第i個(gè)非葉子節(jié)點(diǎn)，則t的分支編碼方式由si決定。如果si=0，則t到左孩子的編碼為c=2c+0，而t到右孩子的編碼為c=2c+1。相反，如果si=1，則t到左孩子的編碼為c=2c+1,而t到右孩子的編碼為c=2c+0。

由于有n個(gè)權(quán)重,故有n個(gè)編碼,只有葉子節(jié)點(diǎn)的編碼需要保存。如果i和j的初始值為i=j=1, 則遞歸函數(shù)f(t)的回溯過程如下:

(1) 如果t是葉子節(jié)點(diǎn),則c當(dāng)前存儲(chǔ)的是權(quán)重t.weight的編碼,故令bi=c和i=i+1。然后返回遞歸上一層。

(2) 如果sj=0，則t的左分支編碼為：ct=c,c=2c+0和f(t.lchild)；而t的右分支編碼為：c=ct,c=2c+1和f(t.rchild)。

(3)如果sj=1，則t的左分支編碼為：ct=c,c=2c+1和f(t.lchild)；而t的右分支編碼為：c=ct,c=2c+0和f(t.rchild)。

(4) 令j=j+1，轉(zhuǎn)步驟(1)。

從以上算法可以看出，它實(shí)質(zhì)是一個(gè)深度優(yōu)先搜索算法，搜索的結(jié)果完全取決于相應(yīng)的哈夫曼樹和編碼方式S=s1s2…sn-1。

5算法仿真

本算法中筆者使用VC6.0作為仿真工具，在CPU為3.2GHz和內(nèi)存為1.86GB的個(gè)人臺(tái)式電腦上完成仿真。

算例 已知編碼事件xi(i=1,2,…,5)的權(quán)重wi(i=1,2,…,5)分別為8,4,4,2,2，求該事件的哈夫曼編碼。

解 建立哈夫曼樹。建法一：合并后的新權(quán)重總是比其他等權(quán)重要后選擇，則建立的哈夫曼樹如圖1所示。

圖1　哈夫曼樹(建法一)

建法二：合并后的新權(quán)重總是比其他等權(quán)重要先選擇，則建立的哈夫曼樹見圖2所示。

圖2　哈夫曼樹(建法二)

由于建立的哈夫曼樹有4個(gè)非葉子節(jié)點(diǎn)，故每棵哈夫曼樹有16種編碼結(jié)果。對(duì)圖1所示的哈夫曼樹，如果編碼方式選擇1001或1010，則編碼結(jié)果如表1所示。

表1建法一的兩種編碼

符號(hào)權(quán)重1001編碼1010編碼x1800x241111x34100101x4210111000x5210101001

與表1相比，通過傳統(tǒng)算法得到的哈夫曼編碼的結(jié)果如表2所示。

表2建法一的傳統(tǒng)編碼

符號(hào)權(quán)重0000編碼1111編碼x1810x240110x34000111x4200101101x5200111100

對(duì)圖2所示的哈夫曼樹，如果編碼方式選擇1101或0010，則編碼結(jié)果如表3所示。

表3建法二的兩種編碼

符號(hào)權(quán)重1101編碼0010編碼x181100x240011x340110x42101010x52100011

與表3相比，通過傳統(tǒng)算法得到的哈夫曼編碼的結(jié)果如表4所示.

表4建法二的傳統(tǒng)編碼

符號(hào)權(quán)重0000編碼1111編碼x180011x241001x341100x42010101x52011100

從上述不同的編碼結(jié)果可以發(fā)現(xiàn)，每種編碼結(jié)果中的碼字互為前綴碼。雖然編碼的平均碼長都是2.2,但由建法二所建哈夫曼樹得到的哈夫曼編碼的各碼字的碼長變化相對(duì)較小。

6結(jié)束語

筆者以哈夫曼樹為基礎(chǔ)，通過對(duì)常規(guī)哈夫曼編碼算法的改進(jìn)，提出了一種可以得到更多哈夫曼編碼結(jié)果的選擇算法。仿真結(jié)果表明:對(duì)于一個(gè)有n個(gè)符號(hào)的信源而言,其哈夫曼編碼的結(jié)果可以通過一個(gè)長度為n-1的二進(jìn)制數(shù)選擇,證明了算法的有效性和哈夫曼編碼結(jié)果的多樣性。

參考文獻(xiàn)：

[1]葉芝慧,沈克勤.信息論與編碼[M].北京：電子工業(yè)出版社,2013.

[2]王向鴻.基于Matlab文本文件哈夫曼編解碼仿真[J].現(xiàn)代電子技術(shù),2013,36(20):31-32.

[3]薛向陽. 基于哈夫曼編碼的文本文件壓縮分析與研究[J]. 科學(xué)技術(shù)與工程, 2010,10(23):5779-5781.

[4]程佳佳,熊志斌.哈夫曼算法在數(shù)據(jù)壓縮中的應(yīng)用[J].電腦編程技巧與維護(hù),2013(02):35-37.

[5]闞君滿.基于改進(jìn)哈夫曼編碼的全文索引結(jié)構(gòu)壓縮算法[J].吉林大學(xué)學(xué)報(bào), 2011,29(5):473-476.

[6]鄧宏貴,郭晟偉,李志堅(jiān).基于哈夫曼編碼的矢量量化圖像壓縮算法[J].計(jì)算機(jī)工程, 2010,36(4):218-222.

Selection algorithm based on Huffman coding

WANGFang-xiu1,LIUChun-hong2

(1. School of Mathematics and Computer Science,Wuhan Polytechnic University, Wuhan 430023,China;2. Ezhou Iron and Steel Plate Spring Co., Ltd. Ezhou 436000, China)

Abstract：Aiming at the same Huffman tree having a variety of different Huffman coding , this paper proposes a Huffman code selection algorithm. Based on diversity of Huffman coding, the algorithm provides 0 or 1 as coding method for every non leaf node of the huffman tree. A binary sequence is constructed by the composition of all non leaf node coding method, finally Huffman coding is obtained according to the binary sequence. In view of the fact that the recursive substructures of Huffman coding, this paper designs a backtracking algorithm that is different from the traditional Huffman coding. Simulation results show, on the one hand, sometimes the same event can contruct different Huffman tree. on the other hand according to the different coding methods different results of Huffman coding can obtained from the same Huffman tree.

Key words：Huffman tree; Huffman code; selection algorithm; backtracking algorithm;recursive sub structure

收稿日期：2015-12-31.

作者簡(jiǎn)介：王防修(1973-)，男，副教授，E-mail:wfx323@126.com.

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61179032).

文章編號(hào)：2095-7386(2016)02-0079-04

DOI:10.3969/j.issn.2095-7386.2016.02.014

中圖分類號(hào)：TP 391

文獻(xiàn)標(biāo)識(shí)碼：A