余　結(jié)，王防修，胡　迪，熊海夢，胡　義

(武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,湖北 武漢 430023)

?

一種香農(nóng)編碼優(yōu)化算法的改進(jìn)

余結(jié)，王防修，胡迪，熊海夢，胡義

(武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,湖北 武漢 430023)

摘要：針對香農(nóng)編碼優(yōu)化算法在編碼效率方面存在的不足，提出一種基于信源符號碼字重新分配而使平均碼長變短的優(yōu)化算法。新算法在原優(yōu)化算法的基礎(chǔ)上，通過判斷優(yōu)化碼的碼長是否隨概率的遞減而遞增來決定該優(yōu)化碼是否需要進(jìn)一步優(yōu)化。鑒于改進(jìn)算法只對優(yōu)化碼的碼長不是隨概率的遞減而遞增的情形才有效，首先設(shè)計(jì)一個優(yōu)化碼能否改進(jìn)的判斷算法，通過對優(yōu)化碼的判斷，然后對能進(jìn)一步優(yōu)化的優(yōu)化碼用改進(jìn)算法優(yōu)化。改進(jìn)算法用選擇排序算法對優(yōu)化碼進(jìn)行重新分配，使得分配后的碼字滿足碼長隨概率的遞減而遞增。算例仿真表明，對能進(jìn)一步優(yōu)化的優(yōu)化碼，改進(jìn)算法可以進(jìn)一步提高優(yōu)化算法的編碼效率。

關(guān)鍵詞：香農(nóng)編碼；優(yōu)化算法；編碼效率；改進(jìn)算法；選擇排序

1引言

在數(shù)據(jù)傳輸和存儲過程中，為提高通信效率，有必要對數(shù)據(jù)信息進(jìn)行壓縮處理。作為一種重要的變長編碼[1]技術(shù)，香農(nóng)編碼對此具有重要的理論指導(dǎo)意義。因此，對香農(nóng)編碼的研究與實(shí)現(xiàn)一直是人們關(guān)注的熱點(diǎn)[2-8]。雖然文獻(xiàn)[9]對香農(nóng)編碼算法進(jìn)行了優(yōu)化，也一定程度上提高了香農(nóng)編碼的編碼效率，但通過算法測試發(fā)現(xiàn)，經(jīng)過該算法編碼得到的碼字有時(shí)會出現(xiàn)大概率符號對應(yīng)長碼字而小概率符號對應(yīng)短碼字的情況，使得該算法的平均碼長還可以進(jìn)一步縮短。為了進(jìn)一步提高該優(yōu)化算法的編碼效率，本文提出了一種通過對碼字進(jìn)行升序排序和碼字重新分配的方法對算法加以改進(jìn)，使得用改進(jìn)算法得到的編碼總是大概率事件對應(yīng)短碼字而小概率事件對應(yīng)長碼字。算法仿真表明，與原優(yōu)化算法相比，改進(jìn)算法可以使信源符號的編碼效率得到進(jìn)一步提高。

2香農(nóng)編碼優(yōu)化算法及其存在的問題

(1)

2.1香農(nóng)編碼的優(yōu)化算法

香農(nóng)編碼的優(yōu)化步驟如下：

1)對n個信源符號xi的概率進(jìn)行降序排列，即滿足

p1≥p2≥…≥pn.

(2)

2)所有碼字取相同的碼長

(3)

4)將每個累加概率Pi轉(zhuǎn)化為二進(jìn)制數(shù)，取小數(shù)點(diǎn)后l位二進(jìn)制數(shù)作為備用碼字，即

Pi=Pi-1+pi-1，i=2,3,…,n.

(4)

(5)

i=1,2,…,n和j=1,2,…,l，bi,j表示碼字bi的第j位二進(jìn)制數(shù)，bi滿足

Pi=(0.bi…)2.

(6)

即bi是Pi的小數(shù)點(diǎn)后的l位二進(jìn)制數(shù)。

5)對備用碼字進(jìn)行優(yōu)化，使任意一個碼字都不是其它碼字的前綴[10-11]，同時(shí)每個碼字的碼長盡可能短。

其優(yōu)化過程如下：

a.初始化碼字指示器i=1；

b.設(shè)置碼字指示器j=1和kmax=0；

c.如果i≠j，則計(jì)算bi與bj的不同二進(jìn)制位的位置，即

bi(k-1)=bj(k-1).

(7)

和

bi,k≠bj,k.

(8)

其中bi(l)表示取碼字bi的前l(fā)位，而bi,k表示碼字bi的第k位二進(jìn)制位，則k表示bi與bj互為前綴碼的最小位置。

如果k>kmax，則kmax=k

(9)

d.如果j

e.根據(jù)最終求得的kmax更新備用碼字bi，使得bi=bi(kmax).

(10)

f.如果i

2.2　香農(nóng)編碼優(yōu)化算法存在的不足

由于備用碼字經(jīng)過優(yōu)化后，經(jīng)常會出現(xiàn)大概率符號對應(yīng)長碼字而小概率符號對應(yīng)短碼字的情形。因此，有必要對生成的碼字進(jìn)行調(diào)整，使得最終的碼字滿足大概率符號對應(yīng)短碼字而小概率符號對應(yīng)長碼字。只有這樣，才能使信源符號的平均碼長最短。

3算法改進(jìn)

設(shè)概率為pi的信源符號xi經(jīng)過優(yōu)化編碼后的碼字為bi，其中概率pi滿足式(2)。為了實(shí)現(xiàn)大概率符號對應(yīng)短碼字而小概率符號對應(yīng)長碼字，只需要對bi根據(jù)碼長進(jìn)行升序排序，使得最終獲得

l(bi1)≤l(bi2)≤…≤l(bin).

(11)

然后，重新分配信源符號xj的碼字為bij，j=1,2,…,n。

如果優(yōu)化碼bi的碼長是li，i=1,,…,n，則有

(12)

即改進(jìn)碼的平均碼長一般要小于優(yōu)化碼，故改進(jìn)碼的編碼效率一般要高于優(yōu)化碼。

3.1　優(yōu)化碼進(jìn)一步優(yōu)化的判斷依據(jù)

不是任何優(yōu)化碼都能用改進(jìn)的算法進(jìn)一步優(yōu)化，只有當(dāng)優(yōu)化碼的碼長不是單調(diào)遞增時(shí)才行。即當(dāng)p1≥p2≥…≥pn時(shí)，如果出現(xiàn)對應(yīng)的優(yōu)化碼的碼長滿足l1≤l2≤…≤ln，則該優(yōu)化碼就一定無法被改進(jìn)算法優(yōu)化；反之，如果?ipj，s.t.li>lj，則該優(yōu)化碼就可用改進(jìn)算法優(yōu)化。因此，判斷優(yōu)化碼能否被進(jìn)一步優(yōu)化的算法如下：

a.初始化。使i=1，表示i指示第一個碼字的碼長；

b.如果li>li+1，則轉(zhuǎn)至步驟d.

c.如果i

d.如果i

e.如果i=n-1且ln-1>ln，則優(yōu)化碼可以被進(jìn)一步優(yōu)化。

3.2基于選擇排序的碼字分配

所謂碼字分配，就是指概率大的符號得到短碼字而概率小的符號得到長碼字。

因此，可以根據(jù)碼長進(jìn)行升序排序來實(shí)現(xiàn)碼字的重新分配。這里不妨用選擇排序算法對碼字重新排序的過程描述如下：

a.計(jì)算碼字的碼長li=len(bi)，i=1,…,n.

b.初始化碼長指示器i=1；

c.使h=i，表示h是需要競爭的位置；

d.j=i+1,如果lj

e.如果j

f.如果h≠i，則lh?li和bh?bi；

g.如果i

h.信源符號xi的碼字對應(yīng)為bi，i=1,2,…,n.

碼字bi經(jīng)過選擇排序后，得到的碼字滿足

l(b1)≤l(b2)≤…≤l(bn).

(13)

這樣，信源符號xi的概率越大，則其碼長越短；反之，概率越小，碼長越長。則由

(14)

可知碼字的平均碼長越小，從而編碼效率越高。

4算法仿真

下面幾個算例使用VC6.0作為仿真工具，在CPU為3.2 GHz和內(nèi)存為1.86 GB的個人臺式電腦上完成仿真。下面算例均要求用香農(nóng)編碼，優(yōu)化編碼和改進(jìn)編碼對信源符號進(jìn)行編碼。

算例1現(xiàn)有12個信源符號，其概率分布如表1所示。

表1　12個信源符號的概率分布

通過使用三種不同算法進(jìn)行編碼，可以得到如表2所示的編碼結(jié)果。

表2　12個信源符號的編碼結(jié)果比較

由信源的熵公式

(15)

和公式(13)，可以求得編碼效率為

(16)

因此，求得三種不同算法的編碼效率如表3所示。

表3　12個信源符號的編碼效率比較

算例2現(xiàn)有6個信源符號，其概率分布如表4所示。

表4　6個信源符號的概率分布

通過使用三種不同算法進(jìn)行編碼，可以得到如表5所示的編碼結(jié)果。

表5　6個信源符號的編碼結(jié)果比較

同樣，求得三種不同算法的編碼效率如表6所示。

表6　6個信源符號的編碼效率比較

算例3表7是4個信源符號的編碼結(jié)果。

根據(jù)編碼效率的計(jì)算公式，可知香農(nóng)編碼的編碼效率為η=0.769 350，而優(yōu)化算法的編碼效率為η=0.923 220。

表7　4個信源符號的編碼結(jié)果比較

對算例1和算例2的編碼結(jié)果進(jìn)行比較，可以看出本文算法較之香農(nóng)編碼優(yōu)化算法而言，其編碼效率有不同程度的提高。算例3由于碼長是隨概率的遞減而遞增，故優(yōu)化碼不能被進(jìn)一步優(yōu)化。其次，對不同個數(shù)的信源符號進(jìn)行編碼，編碼效率也可能會有所不同。

5結(jié)論

由于本文提出的算法是香農(nóng)編碼優(yōu)化算法的改進(jìn)，它是在優(yōu)化編碼的基礎(chǔ)上對優(yōu)化碼進(jìn)一步優(yōu)化，故它的編碼效率一般要高于優(yōu)化編碼算法。

優(yōu)化編碼算法之所以編碼效率要高于香農(nóng)編碼，是因?yàn)閮?yōu)化編碼算法可以得到更短的平均碼長。同樣，如果優(yōu)化編碼算法得到的碼長不是隨概率遞減而遞增，則與優(yōu)化算法相比，用改進(jìn)算法進(jìn)行編碼又可以得到更短的平均碼長。所以一般情況下，優(yōu)化編碼的編碼效率要高于香農(nóng)編碼，而改進(jìn)算法的編碼效率又要優(yōu)于優(yōu)化編碼。通過對改進(jìn)算法的分析，可以得出如下結(jié)論。

1)本文所提算法的編碼編碼效率一般要高于優(yōu)化編碼；

2)只有當(dāng)優(yōu)化碼的碼長不是隨概率遞減而遞增時(shí)，才考慮用改進(jìn)算法對優(yōu)化碼進(jìn)一步優(yōu)化；

3)對不同個數(shù)的信源符號，改進(jìn)算法對編碼效率的提高會有所不同；

4)即使信源符號的個數(shù)相同，改進(jìn)算法對編碼效率的提高也可能會有不同。

參考文獻(xiàn)：

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

[2]楊揚(yáng),申石磊.支持更新的XML編碼方案[J].計(jì)算機(jī)工程與設(shè)計(jì), 2012,33(4)：1629-1632.

[3]譚鵬許,陳越. 基于廣播加密的安全容錯編碼[J].計(jì)算機(jī)工程與設(shè)計(jì), 2013，34(10)：3417-3421.

[4]邢楠,朱虹. 一種快速判斷非唯一可譯碼的方法[J].無線通信技術(shù), 2008，31(2)：29-31.

[5]劉憶寧.信息論教學(xué)中的程序設(shè)計(jì)[J]. 桂林電子科技大學(xué)學(xué)報(bào),2008,28(4)：338-341.

[6]郭姝,施滔滔.淺談香農(nóng)編碼的JAVA實(shí)現(xiàn)及其效率分析[J]. 中國西部科技, 2009,8(27)：44-46.

[7]張燕紅 ,王燕.幾種常用圖像壓縮編碼方法的研究及C#實(shí)現(xiàn)[J]. 計(jì)算技術(shù)與自動化,2013，32(3)：60-63.

[8]張曉梅.常見離散信源編碼方法的比較[J].福建電腦, 2009(5)：64-66.

[9]邵軍花 ,劉玉紅.香農(nóng)編碼的優(yōu)化算法研究[J].蘭州交通大學(xué)學(xué)報(bào),2010,29(6):110-113.

[10]謝勰.關(guān)于Shannon編碼的若干注記[J].西安郵電學(xué)院學(xué)報(bào), 2009,14(3)：58-60.

[11]舒季君,沈傳龍.d-L前綴碼的完全化構(gòu)造方法[J].杭州師范學(xué)院學(xué)報(bào), 2008,7(1)：24-28.

An improved shannon coding optimization algorithm

YUJie,WANGFang-xiu,HUDi,XIONGHai-meng,HUYi

(School of Mathematics and Computer Science,Wuhan Polytechnic University,Wuhan 430023,China)

Abstract：Aiming at the deficiency in shannon coding optimization algorithm, this paper presents an optimization algorithma which redistributs lcodeword to source symbols and makes the average code length shorter.The new algorithm which is on the basis of the original optimization algorithm, and uses the code length to determine optimal codes increases with probability decreases ,and judge whether the optimized code is in need of further optimization. In view of the improved algorithm which is effective to optimize the code length that does not increases with the probability of decreasing ,this paper designs a judgment algorithm to decide whether the optimized code can be improved. By judging to the optimized code, it uses the improved algorithm to optimize the optimization code.The improved algorithm uses selection sort algorithm to redistribute the optimized code, the distribution of codewords satisfy code length increasing with the probability descreasing. Simulation results show that, for the further optimization of the energy of the optimized code, the improved algorithm can further improve the coding efficiency of optimization algorithm。

Key words：shannon code; optimization algorithm; coding efficiency; improved algorithm;selection sort

DOI:10.3969/j.issn.2095-7386.2015.02.020

文章編號：2095-7386(2015)02-0087-05

基金項(xiàng)目：河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目課題(15B520026，15B520025).

作者簡介：董萍(1980-)，女，講師，E-mail：dongpingms2008@163.com.

收稿日期：2015-04-08.

中圖分類號：TP 391

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