王防修，劉春紅

(1.武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北 武漢 430023；2.九州通醫(yī)藥集團(tuán)物流有限公司，湖北 武漢 430040)

?

一種哈夫曼編碼的改進(jìn)算法

王防修1，劉春紅2

(1.武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北 武漢 430023；2.九州通醫(yī)藥集團(tuán)物流有限公司，湖北 武漢 430040)

摘要：針對(duì)哈夫曼編碼需要用到指針和結(jié)構(gòu)體而導(dǎo)致使用受到限制的問(wèn)題，提出一種不用指針和結(jié)構(gòu)體也能進(jìn)行哈夫曼編碼的算法。算法以哈夫曼編碼的編碼原理為基礎(chǔ)，先自底向上得到各個(gè)中間結(jié)點(diǎn)的雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)，然后自頂向下得到各個(gè)結(jié)點(diǎn)的二進(jìn)制碼字，最后得到的葉子結(jié)點(diǎn)的碼字就是哈夫曼編碼。由于所設(shè)計(jì)的哈夫曼編碼算法只需要使用一維數(shù)組即可以實(shí)現(xiàn)，故對(duì)完成編碼的計(jì)算機(jī)語(yǔ)言沒(méi)有任何限制。算例仿真表明，使用三個(gè)一維數(shù)組即可實(shí)現(xiàn)任何事件的哈夫曼編碼。

關(guān)鍵詞：哈夫曼編碼；中間結(jié)點(diǎn)；碼字；葉子結(jié)點(diǎn)

1引言

作為一種壓縮率最高的無(wú)損壓縮編碼[1]，哈夫曼編碼的算法實(shí)現(xiàn)一直是人們關(guān)注的熱點(diǎn)問(wèn)題[2-5]。在哈夫曼編碼的計(jì)算機(jī)實(shí)現(xiàn)過(guò)程中，普遍都需要使用指針和結(jié)構(gòu)體構(gòu)造哈夫曼樹。然而，許多計(jì)算機(jī)高級(jí)語(yǔ)言并不支持指針和結(jié)構(gòu)體，比如常用的basic語(yǔ)言。同樣，許多網(wǎng)絡(luò)語(yǔ)言也不支持指針和結(jié)構(gòu)體，比如vbscript腳本語(yǔ)言。如果能夠設(shè)計(jì)一個(gè)不需要指針和結(jié)構(gòu)體的哈夫曼編碼算法，則哈夫曼編碼的使用可以得到進(jìn)一步推廣[6-8]。因此，本文研究并設(shè)計(jì)一種不需要指針和結(jié)構(gòu)體也可實(shí)現(xiàn)哈夫曼編碼的算法。

2哈夫曼編碼的原理

設(shè)xi(i=1,2,…,n)是信源S的n個(gè)事件，而wi是xi在信源S中出現(xiàn)的頻率。由哈夫曼編碼的原理，可以得到事件xi對(duì)應(yīng)的編碼bi。為了方便計(jì)算機(jī)實(shí)現(xiàn)同時(shí)又不能使用指針和結(jié)構(gòu)體，需要探索現(xiàn)有這些變量之間的聯(lián)系。

2.1中間結(jié)點(diǎn)權(quán)重的計(jì)算

根據(jù)哈夫曼編碼原理，如果把wi(i=1,2,…,n)看作編碼結(jié)點(diǎn)的權(quán)重，則已經(jīng)具有哈夫曼編碼的n個(gè)葉子結(jié)點(diǎn)權(quán)重。由于哈夫曼編碼總共需要2n-1個(gè)結(jié)點(diǎn)權(quán)重，故還需要計(jì)算n-1個(gè)中間結(jié)點(diǎn)的權(quán)重wi(i+1,i+2,…,2n-1)。對(duì)于第j個(gè)中間結(jié)點(diǎn)的權(quán)重wj而言，其權(quán)重是其左右孩子結(jié)點(diǎn)的權(quán)重之和。因此,要求權(quán)重wj,必須先求出它的兩個(gè)孩子權(quán)重。為方便起見,不妨設(shè)wj的左孩子權(quán)重為wl和右孩子權(quán)重為wr。

第j個(gè)中間結(jié)點(diǎn)的左孩子結(jié)點(diǎn)權(quán)重的選擇算子如下：

(1)

式(1)中的wl表示從所有未被選擇的權(quán)重中選擇最小的權(quán)重,其中fi=0表示權(quán)重wi沒(méi)有被選。而式中的fl=-1表示權(quán)重wl將作為第j個(gè)中間結(jié)點(diǎn)的左孩子權(quán)重。

第j個(gè)中間結(jié)點(diǎn)的右孩子結(jié)點(diǎn)權(quán)重的選擇算子如下：

(2)

式(2)中的fr=1表示權(quán)重wr將作為第j個(gè)中間結(jié)點(diǎn)的右孩子權(quán)重。

通過(guò)式(1)和式(2)可以求出第j個(gè)中間結(jié)點(diǎn)的左孩子結(jié)點(diǎn)權(quán)重wl和右孩子結(jié)點(diǎn)權(quán)重wr,則第j個(gè)中間結(jié)點(diǎn)的權(quán)重計(jì)算如下：

(3)

式(3)中fj=0表示權(quán)重wj可以進(jìn)一步作為其它尚未求出權(quán)重的中間結(jié)點(diǎn)的子權(quán)重。

當(dāng)wl和wr分別被選擇為第j個(gè)中間結(jié)點(diǎn)的左右孩子權(quán)重后,然后通過(guò)式(3)求出第j個(gè)中間結(jié)點(diǎn)的權(quán)重wj后,為了方便接下來(lái)的哈夫曼編碼,需要更新wl和wr的值,更新過(guò)程如下：

wl=wr=j.

(4)

式(4)中的wl和wr被用來(lái)保存第l個(gè)結(jié)點(diǎn)和第r個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)位置j。

當(dāng)計(jì)算出所有中間結(jié)點(diǎn)的權(quán)重之后,除了第2n-1個(gè)結(jié)點(diǎn)的權(quán)重w2n-1存儲(chǔ)所有非根結(jié)點(diǎn)的權(quán)重之和外,其他權(quán)重變量wi保存的都是其雙親結(jié)點(diǎn)的位置。同樣,只有f2n-1=0,其它的標(biāo)志變量fi不是-1就是1?？傊?接下來(lái)變量wi和fi將作為求碼字bi的依據(jù)。

2.2求每個(gè)結(jié)點(diǎn)的碼字

設(shè)bi(i=1,2,…,2n-1)是第i個(gè)結(jié)點(diǎn)的碼字,則需要先求出其雙親結(jié)點(diǎn)的碼字,然后才能求出孩子結(jié)點(diǎn)的碼字。

首先,根結(jié)點(diǎn)不需要編碼,故做如下的初始化工作：

b2n-1=w2n-1=0.

(5)

式(5)中b2n-1=0是方便后繼結(jié)點(diǎn)的編碼而設(shè)置的,而w2n-1=0表示第2n-1個(gè)結(jié)點(diǎn)的碼字長(zhǎng)度為0。

接下來(lái)是依次求碼字bi,而每個(gè)碼字只有先求出其雙親的碼字,然后才能求出它自身的碼字,故求解bi的順序是下標(biāo)遞減，即i=2n-2,2n-3,…,1。

當(dāng)求第i個(gè)碼字bi時(shí),需要根據(jù)fi的值來(lái)決定編碼過(guò)程。

如果fi=-1,則bi是雙親結(jié)點(diǎn)的左孩子碼字,故

bi=2bwi+0.

(6)

如果fi=1,則bi是雙親結(jié)點(diǎn)的右孩子碼字,故

bi=2bwi+1.

(7)

在式(6)和式(7)中,由于wi表示第i個(gè)結(jié)點(diǎn)的雙親位置,故第i個(gè)結(jié)點(diǎn)的編碼就是在其雙親碼字的末位補(bǔ)上一個(gè)二進(jìn)制位,其中式(6)表示末位補(bǔ)0,而式(7)表示末位補(bǔ)1。

當(dāng)求出碼字bi后, wi已經(jīng)完成其編碼任務(wù)。也就是說(shuō),此后不再需要用它來(lái)保存第i個(gè)結(jié)點(diǎn)的雙親位置。所以，可以用wi保存碼字bi的碼長(zhǎng)，其計(jì)算過(guò)程如下：

wi=wwi+1.

(8)

顯然,式(8)體現(xiàn)了孩子結(jié)點(diǎn)的碼長(zhǎng)比其雙親結(jié)點(diǎn)的碼長(zhǎng)多1。

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

從上面的編碼原理可知,要想求出某一信源的哈夫曼編碼,必須先求出所有中間結(jié)點(diǎn)的權(quán)重。當(dāng)計(jì)算出所有中間結(jié)點(diǎn)的權(quán)重后,再由結(jié)點(diǎn)之間的關(guān)系得到哈夫曼編碼。因此,編碼算法實(shí)現(xiàn)過(guò)程分為兩個(gè)階段。

3.1求中間結(jié)點(diǎn)的權(quán)重

對(duì)于一個(gè)包含n個(gè)事件的信源而言,它總共有2n-1個(gè)權(quán)重,其中n個(gè)權(quán)重是n個(gè)事件在信源中的頻率,而其他n-1個(gè)權(quán)重需要計(jì)算得到。具體的求解過(guò)程如下：

(1) 初始化。為了從權(quán)重序列中選擇最小權(quán)重,需要設(shè)置各權(quán)重的初始標(biāo)志位為0,即令fi=0(i=1,2,…,2n-1)。

(2)令j=n+1,則j表示第一個(gè)需要求權(quán)重的中間結(jié)點(diǎn)的位置。

(3) 由式(1)求出第j個(gè)中間結(jié)點(diǎn)的左孩子權(quán)重wl。

(4) 由式(2)求出第j個(gè)中間結(jié)點(diǎn)的右孩子權(quán)重wr。

(5)由式(3)求出第j個(gè)中間結(jié)點(diǎn)的權(quán)重wj。

(6)由式(4)保存左孩子和右孩子結(jié)點(diǎn)的雙親位置。

(7)令j=j+1。如果j≤2n-1,則轉(zhuǎn)步(2)重復(fù)進(jìn)行;否則,求中間結(jié)點(diǎn)權(quán)重的過(guò)程結(jié)束。

從上述過(guò)程可以看出，求wj是一個(gè)遞增的過(guò)程，即j=n+1,n+2,…2n-1。

3.2求各結(jié)點(diǎn)的碼字

當(dāng)所有中間結(jié)點(diǎn)的權(quán)重計(jì)算完成后，除w2n-1保存的是所有結(jié)點(diǎn)的權(quán)重之和外，其它結(jié)點(diǎn)的權(quán)重變量wi(i=1,2,…,2n-2)保存的不再是自身權(quán)重，而是第i個(gè)結(jié)點(diǎn)的雙親位置。同樣，除了f2n-1=0外，其它標(biāo)志變量fi(i=1,2,…,2n-2)不是1就是-1。因此，信源的哈夫曼編碼的過(guò)程如下：

(1)令b2n-1=w2n-1=0和i=2n-2。

(2)如果fi=-1，那么bi=2bwi；否則，bi=2bwi+1。

(3)令wi=wwi+1，表示第i個(gè)結(jié)點(diǎn)的碼長(zhǎng)是其雙親的碼長(zhǎng)加1。

(4)令i=i-1。如果i≥1，則轉(zhuǎn)步(2)重復(fù)進(jìn)行；否則，編碼過(guò)程結(jié)束。

從上述編碼過(guò)程可以看出，w2n-1=0表明根結(jié)點(diǎn)的碼字b2n-1是長(zhǎng)度為0的空碼，而bi是長(zhǎng)度為wi的碼字，其中i=1,2,…,2n-2。在這里，只有bi(i=1,2,…,n)是前綴碼。因此，bi(i=1,2,…,n)就是所求的哈夫曼編碼。

4算法仿真

算例1假設(shè)有7個(gè)信源符號(hào),其頻率分布為{20,19,18,17,15,10,1},要求用本文算法對(duì)其進(jìn)行哈夫曼編碼。

解首先,葉子結(jié)點(diǎn)的權(quán)重wi和選擇標(biāo)志fi的初始化，即

w1=20,w2=19,w3=18,w4=17,

w5=15,w6=10,w7=1.

fi=0,i=1,2,…,7.

其次，通過(guò)算法3.1求第i個(gè)中間結(jié)點(diǎn)的權(quán)重wi，其中i=8,…,13，其過(guò)程如下：

(1)求第8個(gè)結(jié)點(diǎn)的權(quán)重w8及其左右孩子結(jié)點(diǎn)選擇：

w7=min{w1,w2,w3,w4,w5,w6,w7}

f7=-1。所以w7是左孩子結(jié)點(diǎn)權(quán)重。因?yàn)?/p>

w6=min{w1,w2,w3,w4,w5,w6}，f6=1.

所以w7是右孩子結(jié)點(diǎn)權(quán)重。故

w8=w7+w6=11，f8=0,w6=w7=8.

(2)求第9個(gè)結(jié)點(diǎn)的權(quán)重w9及其左右孩子結(jié)點(diǎn)選擇：

w8=min{w1,w2,w3,w4,w5,w8},f8=-1.

w5=min{w1,w2,w3,w4,w5},f5=1.

所以w9=w5+w8=26和f9=0,w5=w8=9.

(3)求第10個(gè)結(jié)點(diǎn)的權(quán)重w10及其左右孩子結(jié)點(diǎn)選擇：

w4=min{w1,w2,w3,w4,w9},f4=-1,

w3=min{w1,w2,w3,w9},f3=1.

所以w10=w3+w4=35,f10=0,w3=w4=10.

(4)求第11個(gè)結(jié)點(diǎn)的權(quán)重w11及其左右孩子結(jié)點(diǎn)選擇：

w2=min{w1,w2,w9,w10},f2=-1.

w1=min{w1,w9,w10}f1=1.

所以有w11=w1+w2=39,f11=0.w1=w2=11.(5)求第12個(gè)結(jié)點(diǎn)的權(quán)重w12及其左右孩子結(jié)點(diǎn)選擇：

w9=min{w9,w10,w11},f9=-1.

w10=min{w10,w11},f10=1.

w12=w9+w10=61,w9=w10=12.

(6)求第13個(gè)結(jié)點(diǎn)的權(quán)重w13及其左右孩子結(jié)點(diǎn)選擇：

w11=min{w11,w12},f11=-1,f12=1.

w13=w11+w12=100,w11=w12=13.

最后，運(yùn)用算法3.2進(jìn)行哈夫曼編碼。

(1)令b13=Φ。因?yàn)閣11=w12=13，而f11=-1,f12=1,所以b11=0,b12=1.

(2)因?yàn)閣9=w10=12，而f9=-1,f10=1,所以b9=10,b10=11.

(3)因?yàn)閣5=w8=9，而f8=-1,f5=1,所以b5=101,b8=100.

(4)因?yàn)閣6=w7=8，而f7=-1,f6=1,所以b6=1001,b7=1000.

(5)因?yàn)閣3=w4=10，而f4=-1,f3=1,所以b3=111,b4=110.

(6)因?yàn)閣1=w2=11，而f2=-1,f1=1,所以b1=01,b2=00.

算例2假設(shè)有4個(gè)信源符號(hào)，其權(quán)重分布為{40,30,20,10},要求用本文算法對(duì)其進(jìn)行哈夫曼編碼。

解首先，對(duì)結(jié)點(diǎn)的權(quán)重和選擇標(biāo)志的初始化如表1所示。

表1權(quán)重和標(biāo)志的初始化

I1234567wi40302010000fi0000000

通過(guò)算法3.1得到如表2的哈夫曼編碼的中間結(jié)果。

表2編碼的中間結(jié)果

I1234567wi765567100fi-1-11-1110

通過(guò)算法3.2得到如表3的哈夫曼編碼。

表3哈夫曼編碼結(jié)果

I1234567wi1233210bi010111110111

從表3可以得到對(duì)應(yīng)的哈夫曼編碼為{0,10,111,110}。

表1中的wi表示第i個(gè)結(jié)點(diǎn)的權(quán)重, 表2中的wi表示第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的位置, 表3中的wi表示碼字bi的碼長(zhǎng)。

5結(jié)束語(yǔ)

筆者提出了一種不用指針和結(jié)構(gòu)體的哈夫曼編碼算法。該算法使用一維數(shù)組保存各結(jié)點(diǎn)的編碼信息，在整個(gè)編碼過(guò)程中不需要建立哈夫曼樹。無(wú)論從算法設(shè)計(jì)還是算法仿真可以看出，整個(gè)算法都只使用一維數(shù)組，而數(shù)組是任何計(jì)算機(jī)語(yǔ)言都具有的功能。需要說(shuō)明的是，前面所說(shuō)到的雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)，只是為方便說(shuō)明元素之間的關(guān)系而已，并不代表該編碼需要建立哈夫曼樹。根據(jù)筆者設(shè)計(jì)的哈夫曼編碼算法，用任何計(jì)算機(jī)語(yǔ)言都可實(shí)現(xiàn)哈夫曼編碼，而這對(duì)于哈夫曼編碼的推廣和應(yīng)用具有重要意義。

參考文獻(xiàn)：

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

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

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

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

[5]高健,陳耀.分組無(wú)損圖像壓縮編碼方法[J].計(jì)算機(jī)工程與設(shè)計(jì), 2010,31(15):3447-3450.

[6]李靈華,劉勇奎.Freeman四方向鏈碼壓縮率提高的方法研究 [J]. 計(jì)算機(jī)工程與設(shè)計(jì),2013,34(3):1132-1136.

[7]王敏超,王敏莉,李秋生，等.無(wú)損自適應(yīng)分布式算術(shù)編碼的研究及應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì),2011,32(10)：3470-3475.

[8]王防修,周康,同小軍.一種不用構(gòu)造二叉樹的哈夫曼編碼[J].武漢工業(yè)學(xué)院學(xué)報(bào),2012,31(2):52-54.

An Improved Algorithm of Huffman Encoding

WANGFang-xiu1,LIUChun-hong2

(1.School of Mathematics and Computer Science,Wuhan Polytechnic University, Wuhan 430023，China;2. Jointown Phamaceutical Group Logistics Co., Ltd. Wuhan 430040,China)

Abstract：According to the application limitation of Huffman encoding due to the need of using the pointer and structure body, a Huffman encoding algorithm without the pointer and structure body was presented in this paper.The algorithm is based on the encoding principle of Huffman encoding.First, from the bottom up to the top it can get the parent node and child nodes of every intermediate node. Second, from the top down to the bottom it can get the binary code of each node. Finally ,codewords of all the leaf nodes consist of the Huffman encoding. The Huffman encoding algorithm can be achieved only by using a one-dimensional in this paper, so the completion of the encoding doesn't depend on any computer language. The simulation results show that three one-dimension arrays can realize the Huffman encoding of any event.

Key words：Huffman coding; intermediate node; code word; Leaf node

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

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

DOI:10.3969/j.issn.2095-7386.2016.01.019

文章編號(hào)：2095-7386(2016)01-0088-04

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

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

收稿日期：2015-12-16.