基于時(shí)間最優(yōu)的費(fèi)諾編碼算法研究與設(shè)計(jì)

王防修，劉春紅

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

?

基于時(shí)間最優(yōu)的費(fèi)諾編碼算法研究與設(shè)計(jì)

王防修1，劉春紅2

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

摘要：針對(duì)費(fèi)諾編碼的算法研究與實(shí)現(xiàn)問題，提出一種最優(yōu)偏差值與分治法相結(jié)合的算法。算法以最小偏差值為目標(biāo)，在概率序列中尋找最佳斷開位置，通過(guò)最佳斷開位置實(shí)現(xiàn)費(fèi)諾編碼。鑒于費(fèi)諾編碼算法的遞歸屬性，分別設(shè)計(jì)了編碼的多模塊算法和單模塊算法。通過(guò)對(duì)算法時(shí)間復(fù)雜度的分析，對(duì)設(shè)計(jì)的算法進(jìn)行了改進(jìn)。算例仿真表明，不同算法對(duì)同一信源編碼所耗費(fèi)的時(shí)間差異很大，選擇時(shí)間最優(yōu)的費(fèi)諾編碼算法能更好地滿足費(fèi)諾編碼系統(tǒng)對(duì)適時(shí)性的要求。

關(guān)鍵詞：時(shí)間最優(yōu)；多模塊算法；單模塊算法；最優(yōu)偏差值；分治法

1引言

在三大經(jīng)典變長(zhǎng)編碼[1]中，哈夫曼編碼的編碼效率最高,香農(nóng)編碼的編碼效率最低,而費(fèi)諾編碼的編碼效率處于兩者之間.在特殊情況下,三者編碼效率相同.然而,只有香農(nóng)編碼[2,3]]和哈夫曼編碼[4-8]被廣泛研究和應(yīng)用,而費(fèi)諾編碼的算法原理及實(shí)現(xiàn)尚未見之于文獻(xiàn)。雖然文獻(xiàn)[1]給出了費(fèi)諾編碼的思想和幾個(gè)具體的例子,但費(fèi)諾編碼的原理并沒有給出.本文針對(duì)費(fèi)諾編碼的算法實(shí)現(xiàn)問題，提出了用分治法進(jìn)行費(fèi)諾編碼的算法思想，設(shè)計(jì)了幾種不同的算法來(lái)實(shí)現(xiàn)費(fèi)諾編碼。通過(guò)對(duì)不同算法對(duì)同一信源編碼所花費(fèi)的時(shí)間進(jìn)行算法比較，從中得出時(shí)間最優(yōu)的費(fèi)諾編碼算法。

2用分治法實(shí)現(xiàn)費(fèi)諾編碼的基本原理

所謂用分治法進(jìn)行費(fèi)諾編碼，就是是將一個(gè)規(guī)模為n的問題分解為兩個(gè)規(guī)模較小的子問題，這兩個(gè)子問題相互獨(dú)立與原問題相同。遞歸地解這些子問題，然后將各子問題的解合并就可以得到原問題的解。

給定包含n個(gè)事件的單信源X={x1,x2,…,xn}，設(shè)事件xi對(duì)應(yīng)的概率為pi(i=1,2,…,n)，且概率pi滿足下述三個(gè)條件：

p1≥p2≥…≥pn；

(1)

0

(2)

(3)

根據(jù)費(fèi)諾編碼的原理，將滿足上述條件的概率序列pipi+1…pj斷開為兩個(gè)子序列pipi+1…pk和pk+1pk+2…pj，然后對(duì)這兩個(gè)子序列對(duì)應(yīng)的各事件分別進(jìn)行0和1編碼，遞歸地對(duì)子序列重復(fù)該過(guò)程，直到每個(gè)子序列的長(zhǎng)度都為1，就可以得到每個(gè)事件的編碼。因此，費(fèi)諾編碼的關(guān)鍵是確定序列pipi+1…pj的斷開位置k。

2.1　遞歸子結(jié)構(gòu)

設(shè)m(i,j)表示從pi至pj這j-i+1個(gè)概率的和，其中1≤i≤j≤n。則：

當(dāng)i=j時(shí)，有m(i,i)=pi.

(4)

(5)

或

m(i,j)=m(i,j-1)+m(j,j).

(6)

如果用(5)求出所有的m(i,j)，其中1≤i

(7)

然而，如果用(6)求所有的m(i,j)，1≤i

(8)

設(shè)pi>pi+1>…>pj和i≤k

(9)

(10)

如果用s(i,j)表示將概率序列pipi+1…pj斷開為兩個(gè)概率子序列的斷開位置，則根據(jù)費(fèi)諾編碼的原理，其斷開位置s(i,j)必須滿足下列關(guān)系：

s(i,i)=i，i=1,2,…,n.

(11)

s(i,j)=k，1≤i

(12)

其中k滿足

(13)

這樣，從概率序列pipi+1…pj的位置k將該序列斷開為兩個(gè)子序列pipi+1…pk和pk+1pk+2…pj。用遞歸的方法，將pipi+1…pk和pk+1pk+2…pj進(jìn)一步斷開，直到i=j為止。

2.2　計(jì)算最優(yōu)值

如果用d(i,j)表示pipi+1…pk和pk+1pk+2…pj的最優(yōu)偏差值，即

(14)

其中k=s(i,j)，則有:

因此，只要知道概率序列pipi+1…pj的斷開位置s(i,j)，就可以立即求出最優(yōu)偏差值

(16)

2.3　構(gòu)造最優(yōu)解

設(shè)事件序列xixi+1…xj對(duì)應(yīng)的編碼為bibi+1…bj，則未進(jìn)行編碼之前，事件xk的編碼初始化為

bk=φ，k=i,i+1,…,j.

(17)

求出s(i,j)后，對(duì)事件xk進(jìn)行編碼的過(guò)程如下：

bk=bk?，k=i,i+1,s(i,j).

(18)

和

bk=bk1，k=s(i,j)+1,…,j.

(19)

求出s(i,s(i,j))后，對(duì)xixi+1…xs(i,j)

中的事件進(jìn)行遞歸編碼。

同理，xs(i,j)+1…xj中的事件是根據(jù)s(s(i,j)+1,j)斷開進(jìn)行遞歸編碼的。

2.4　計(jì)算編碼效率

信源X={x1,x2,…,xn}的熵為

(20)

其中0

(21)

因此，費(fèi)諾編碼的編碼效率

(22)

3算法設(shè)計(jì)

設(shè)遞歸函數(shù)f(i,j)是對(duì)事件序列xixi+1…xj的費(fèi)諾編碼，則通過(guò)執(zhí)行f(i,j)可以對(duì)事件序列x1x2…xn中每個(gè)事件xi(i=1,2,…,n)編碼。

3.1　模塊化設(shè)計(jì)

下面算法的步驟1到步驟3中每個(gè)步驟對(duì)應(yīng)一個(gè)功能模塊，步驟4是編碼模塊。

步驟1 通過(guò)(4)和(6)計(jì)算m(i,j)，1≤i

步驟2 通過(guò)(11)，(12)和(13)計(jì)算s(i,j)；根據(jù)(16)計(jì)算d(i,j)。具體過(guò)程如下：

a.令s(i,i)=i和d(i,i)=0，i=1,2,…,n.

b.初始化r=1和i=1.

c.使j=i+1和s(i,j)=i.

d.由(13)求出s(i,j)和(16)求出d(i,j).

e.如果i

f.如果r

步驟3遞歸函數(shù)f(i,j)編碼的過(guò)程如下：

a.如果i=j，則編碼結(jié)束。

b.bk=bk0，k=i,i+1,s(i,j).

c.bk=bk1，k=s(i,j)+1,…,j.

d.分別調(diào)用f(i,s(i,j))和f(is(i,j)+1,j).

步驟4 通過(guò)調(diào)用f(1,n)實(shí)現(xiàn)遞歸編碼，最后得到每個(gè)事件xi的編碼bi，i=1,…,n.

3.2　位置遞歸函數(shù)的算法改進(jìn)

在算法3.1的步驟2所對(duì)應(yīng)的模塊中，求d(i,j)和s(i,j)的時(shí)間復(fù)雜度為O(n3)。如果能對(duì)該模塊加以改進(jìn)，則可以大大減少編碼時(shí)間。設(shè)改進(jìn)后的模塊為遞歸函數(shù)g(i,j)，則該函數(shù)的遞歸過(guò)程如下：

a.如果i=j，則遞歸過(guò)程結(jié)束；

c.使s(i,j)=k和d(i,j)=

d.遞歸調(diào)用g(i,k)和g(k+1,j).

最后，通過(guò)調(diào)用遞歸函數(shù)g(1,n)就可以求出編碼過(guò)程需中需要的全部斷開位置。

3.3　單模塊設(shè)計(jì)

算法3.1和算法3.2都是自頂向下的多模塊設(shè)計(jì)，算法中的模塊執(zhí)行順序不能改變。其優(yōu)點(diǎn)是算法的數(shù)學(xué)模型簡(jiǎn)單，缺點(diǎn)是計(jì)算m(i,j)時(shí)需要花費(fèi)更多的機(jī)時(shí)。為此，下面編碼算法是用單一遞歸模塊h(i,j)進(jìn)行設(shè)計(jì)的：

a. 如果i=j，則遞歸過(guò)程結(jié)束。

d.初始化k=i+1.

e.使tl=tl+pk和tr=tr-pk.

g.如果k

h.bk=bk0，k=i,i+1,s(i,j)和bk=bk1，k=s(i,j)+1,…,j.

i.遞歸調(diào)用h(i,s(i,j))和h(s(i,j)+1,j).

因此，最后只要調(diào)用h(1,n)就可完成所有信源事件的編碼。

4算法仿真

本算法使用VC6.0作為仿真工具，在CPU為3.2GHz和內(nèi)存為1.86GB的個(gè)人臺(tái)式電腦上完成仿真。本節(jié)將對(duì)費(fèi)諾編碼的幾種不同算法設(shè)計(jì)進(jìn)行實(shí)例比較。

解首先，求得最優(yōu)偏差值：

d(1,11)=0.060 956，d(1,2)=0.100 574

d(3,11)=0.007 982，d(3,5)=0.063 164

d(4,5)=0.001 310，d(6,11)=0.015 718

d(6,7)=0.001 488，d(8,11)=0.022 036

d(8,9)=0.003 966，d(10,11)=0.003 966

和最優(yōu)斷開位置：

s(1,11)=2，s(1,2)=1，s(3,11)=5

s(3,5)=4，s(4,5)=4，s(6,11)=7

s(6,7)=6，s(8,11)=2，

s(8,9)=8，s(10,11)=10.

根據(jù)斷開位置得到的編碼如表1所示。

表1　11個(gè)符號(hào)的費(fèi)諾編碼

根據(jù)(20)，信源熵H(X)=3.045 056

(bit/符號(hào))。

根據(jù)(21)，經(jīng)過(guò)費(fèi)諾編碼后的平均碼長(zhǎng)

根據(jù)(22)，編碼效率為η=0.98587 923.

雖然分別用算法3.1，算法3.2和算法3.3對(duì)算例進(jìn)行編碼，會(huì)得到相同的編碼結(jié)果，但所花費(fèi)的時(shí)間是不同的。實(shí)驗(yàn)表明，它們所花費(fèi)的時(shí)間分別為:0.006 2ms, 0.003 1ms,0.001 5ms.

從編碼所花費(fèi)的時(shí)間看，算法3.3花費(fèi)的時(shí)間最少，算法3.2次之，算法3.1用時(shí)最多，這種結(jié)果與算法設(shè)計(jì)的原理是一致的。然而，單從一個(gè)算例還無(wú)法說(shuō)明算法3.3在編碼時(shí)間上就一定是最優(yōu)的。為了進(jìn)一步比較這三種算法在編碼時(shí)間方面的優(yōu)劣，在此隨機(jī)選取10個(gè)不同單信源進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果如表2所示。其中，表中的T1，T2和T3分別表示三種算法的編碼時(shí)間。

5算法分析

從表1顯示的實(shí)驗(yàn)數(shù)據(jù)可以看出：

1)筆者設(shè)計(jì)的三種算法對(duì)同一信源編碼所耗費(fèi)的時(shí)間差別很大；

表2　不同費(fèi)諾編碼算法的實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)

2)三種算法的編碼時(shí)間均隨信源符號(hào)的個(gè)數(shù)增大而增大；

3)伴隨信源符號(hào)個(gè)數(shù)的增加，算法3.1的編碼時(shí)間提高很快，而算法3.3的編碼時(shí)間增速緩慢。

算法3.2和算法3.3之所以編碼時(shí)間比算法3.1要優(yōu)，是因?yàn)榍罢哂?jì)算d(i,j)和s(i,j)的時(shí)間復(fù)雜度為O(n)，而后者時(shí)間復(fù)雜度為O(n3)。同樣，算法3.3的編碼時(shí)間之所以明顯優(yōu)于算法3.2，是因?yàn)樗惴?.3計(jì)算m(i,j)的時(shí)間復(fù)雜度為O(n)，而算法3.1和算法3.2計(jì)算m(i,j)的時(shí)間復(fù)雜度為O(n3)。

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

本文提出了一種基于時(shí)間最優(yōu)的快速費(fèi)諾編碼算法。該算法使用了最優(yōu)偏差值與分治法相結(jié)合的方法來(lái)對(duì)信源符號(hào)編碼，該算法縮小了概率序列位置斷開的計(jì)算量，減少了遞歸過(guò)程中一些變量的重復(fù)計(jì)算，提高了信源符號(hào)的編碼速度。從算法仿真可以看出，雖然費(fèi)諾編碼的原理是相同的，但不同的費(fèi)諾編碼算法設(shè)計(jì)所產(chǎn)生的編碼速度完全不一樣。因此，在實(shí)際編碼過(guò)程中，編碼速度快的算法自然更加受到青睞。在上面介紹的三種算法中，由于算法3.3的時(shí)間最優(yōu)，故對(duì)一個(gè)費(fèi)諾編碼系統(tǒng)而言,算法3.3更能滿足該編碼系統(tǒng)對(duì)適時(shí)性的要求。

參考文獻(xiàn)：

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

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

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

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

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

[6]程佳佳，熊志斌.哈夫曼算法在數(shù)據(jù)壓縮中的應(yīng)用[J] 科學(xué)技術(shù)與工程, 2010，2：35-37.

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

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

Fano Coding algorithm research and design based on time optimal matching

WANGFang-xiu1,LIUChun-hong2

(1.School of Mathematics and Computer Science,Wuhan Polylethnic University,Wuhan 430023,China;

2. Ezhou Iron and Steel Plate Spring Co Ltd, Ezhou 436000,China)

Abstract：According to the algorithm Research and implementation problems of Fano coding, this paper presents an algorithm with optimal deviation Combined with divide and conquer。In order to gain optimal deviation value, the algorithm must find the best open position in the probability series and achieve fano coding by the position. Given the recursive property in Fano coding algorithm, coding algorithm is designed for multi-module and single-module algorithm. By the time complexity analysis of the algorithm , the algorithm is improved. Examples simulation results show，difference in time-consuming is very large for different algorithms to encode the same information source，and Choose the best time Fano coding algorithm can better meet the requirements for timeliness for the coding system.

Key words：time optimal;multi-module algorithm;single module algorithm;optimal deviation;divide and conquer

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

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