一種哈夫曼編碼的改進算法

王防修，劉春紅

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

?

一種哈夫曼編碼的改進算法

王防修1，劉春紅2

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

摘要：針對哈夫曼編碼需要用到指針和結構體而導致使用受到限制的問題，提出一種不用指針和結構體也能進行哈夫曼編碼的算法。算法以哈夫曼編碼的編碼原理為基礎，先自底向上得到各個中間結點的雙親結點和孩子結點，然后自頂向下得到各個結點的二進制碼字，最后得到的葉子結點的碼字就是哈夫曼編碼。由于所設計的哈夫曼編碼算法只需要使用一維數組即可以實現，故對完成編碼的計算機語言沒有任何限制。算例仿真表明，使用三個一維數組即可實現任何事件的哈夫曼編碼。

關鍵詞：哈夫曼編碼；中間結點；碼字；葉子結點

1引言

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

2哈夫曼編碼的原理

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

2.1中間結點權重的計算

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

第j個中間結點的左孩子結點權重的選擇算子如下：

(1)

式(1)中的wl表示從所有未被選擇的權重中選擇最小的權重,其中fi=0表示權重wi沒有被選。而式中的fl=-1表示權重wl將作為第j個中間結點的左孩子權重。

第j個中間結點的右孩子結點權重的選擇算子如下：

(2)

式(2)中的fr=1表示權重wr將作為第j個中間結點的右孩子權重。

通過式(1)和式(2)可以求出第j個中間結點的左孩子結點權重wl和右孩子結點權重wr,則第j個中間結點的權重計算如下：

(3)

式(3)中fj=0表示權重wj可以進一步作為其它尚未求出權重的中間結點的子權重。

當wl和wr分別被選擇為第j個中間結點的左右孩子權重后,然后通過式(3)求出第j個中間結點的權重wj后,為了方便接下來的哈夫曼編碼,需要更新wl和wr的值,更新過程如下：

wl=wr=j.

(4)

式(4)中的wl和wr被用來保存第l個結點和第r個結點的雙親結點位置j。

當計算出所有中間結點的權重之后,除了第2n-1個結點的權重w2n-1存儲所有非根結點的權重之和外,其他權重變量wi保存的都是其雙親結點的位置。同樣,只有f2n-1=0,其它的標志變量fi不是-1就是1。總之,接下來變量wi和fi將作為求碼字bi的依據。

2.2求每個結點的碼字

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

首先,根結點不需要編碼,故做如下的初始化工作：

b2n-1=w2n-1=0.

(5)

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

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

當求第i個碼字bi時,需要根據fi的值來決定編碼過程。

如果fi=-1,則bi是雙親結點的左孩子碼字,故

bi=2bwi+0.

(6)

如果fi=1,則bi是雙親結點的右孩子碼字,故

bi=2bwi+1.

(7)

在式(6)和式(7)中,由于wi表示第i個結點的雙親位置,故第i個結點的編碼就是在其雙親碼字的末位補上一個二進制位,其中式(6)表示末位補0,而式(7)表示末位補1。

當求出碼字bi后, wi已經完成其編碼任務。也就是說,此后不再需要用它來保存第i個結點的雙親位置。所以，可以用wi保存碼字bi的碼長，其計算過程如下：

wi=wwi+1.

(8)

顯然,式(8)體現了孩子結點的碼長比其雙親結點的碼長多1。

3哈夫曼編碼的算法實現

從上面的編碼原理可知,要想求出某一信源的哈夫曼編碼,必須先求出所有中間結點的權重。當計算出所有中間結點的權重后,再由結點之間的關系得到哈夫曼編碼。因此,編碼算法實現過程分為兩個階段。

3.1求中間結點的權重

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

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

(2)令j=n+1,則j表示第一個需要求權重的中間結點的位置。

(3) 由式(1)求出第j個中間結點的左孩子權重wl。

(4) 由式(2)求出第j個中間結點的右孩子權重wr。

(5)由式(3)求出第j個中間結點的權重wj。

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

(7)令j=j+1。如果j≤2n-1,則轉步(2)重復進行;否則,求中間結點權重的過程結束。

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

3.2求各結點的碼字

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

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

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

(3)令wi=wwi+1，表示第i個結點的碼長是其雙親的碼長加1。

(4)令i=i-1。如果i≥1，則轉步(2)重復進行；否則，編碼過程結束。

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

4算法仿真

算例1假設有7個信源符號,其頻率分布為{20,19,18,17,15,10,1},要求用本文算法對其進行哈夫曼編碼。

解首先,葉子結點的權重wi和選擇標志fi的初始化，即

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

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

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

其次，通過算法3.1求第i個中間結點的權重wi，其中i=8,…,13，其過程如下：

(1)求第8個結點的權重w8及其左右孩子結點選擇：

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

f7=-1。所以w7是左孩子結點權重。因為

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

所以w7是右孩子結點權重。故

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

(2)求第9個結點的權重w9及其左右孩子結點選擇：

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個結點的權重w10及其左右孩子結點選擇：

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個結點的權重w11及其左右孩子結點選擇：

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個結點的權重w12及其左右孩子結點選擇：

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

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

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

(6)求第13個結點的權重w13及其左右孩子結點選擇：

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

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

最后，運用算法3.2進行哈夫曼編碼。

(1)令b13=Φ。因為w11=w12=13，而f11=-1,f12=1,所以b11=0,b12=1.

(2)因為w9=w10=12，而f9=-1,f10=1,所以b9=10,b10=11.

(3)因為w5=w8=9，而f8=-1,f5=1,所以b5=101,b8=100.

(4)因為w6=w7=8，而f7=-1,f6=1,所以b6=1001,b7=1000.

(5)因為w3=w4=10，而f4=-1,f3=1,所以b3=111,b4=110.

(6)因為w1=w2=11，而f2=-1,f1=1,所以b1=01,b2=00.

算例2假設有4個信源符號，其權重分布為{40,30,20,10},要求用本文算法對其進行哈夫曼編碼。

解首先，對結點的權重和選擇標志的初始化如表1所示。

表1權重和標志的初始化

I1234567wi40302010000fi0000000

通過算法3.1得到如表2的哈夫曼編碼的中間結果。

表2編碼的中間結果

I1234567wi765567100fi-1-11-1110

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

表3哈夫曼編碼結果

I1234567wi1233210bi010111110111

從表3可以得到對應的哈夫曼編碼為{0,10,111,110}。

表1中的wi表示第i個結點的權重, 表2中的wi表示第i個結點的雙親結點的位置, 表3中的wi表示碼字bi的碼長。

5結束語

筆者提出了一種不用指針和結構體的哈夫曼編碼算法。該算法使用一維數組保存各結點的編碼信息，在整個編碼過程中不需要建立哈夫曼樹。無論從算法設計還是算法仿真可以看出，整個算法都只使用一維數組，而數組是任何計算機語言都具有的功能。需要說明的是，前面所說到的雙親結點和孩子結點，只是為方便說明元素之間的關系而已，并不代表該編碼需要建立哈夫曼樹。根據筆者設計的哈夫曼編碼算法，用任何計算機語言都可實現哈夫曼編碼，而這對于哈夫曼編碼的推廣和應用具有重要意義。

參考文獻：

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

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

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

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

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

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

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

[8]王防修,周康,同小軍.一種不用構造二叉樹的哈夫曼編碼[J].武漢工業(yè)學院學報,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

中圖分類號：TP 391

文獻標識碼：A

DOI:10.3969/j.issn.2095-7386.2016.01.019

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

基金項目：國家自然科學基金資助項目(61179032).

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

收稿日期：2015-12-16.