王防修

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

?

基于前綴碼的快速編碼算法研究

王防修

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

摘要：針對目前符號序列的編碼存在編碼速度慢的問題，提出了一種通過減少平均查找長度來提高編碼速度的算法。根據(jù)符號概率的大小，設(shè)計(jì)了順序查找、大概率優(yōu)先查找和小概率優(yōu)先查找三種編碼算法。通過對這三種編碼算法的平均查找長度的分析比較，結(jié)果表明：大概率優(yōu)先查找算法的平均查找長度最短。根據(jù)符號本身的大小，設(shè)計(jì)了折半查找和二叉排序樹查找兩種編碼算法。通過對這兩種編碼算法的平均查找長度的分析比較，結(jié)果表明折半查找編碼算法的平均查找長度最短。因此，最優(yōu)的編碼算法應(yīng)從大概率優(yōu)先查找算法和折半查找算法之中選擇其一。算例表明，為了提高符號序列的編碼速度，對同一符號序列的編碼，應(yīng)從大概率優(yōu)先查找算法和折半查找算法中選擇平均查找長度最短的算法作為編碼算法。

關(guān)鍵詞：順序查找；折半查找；二叉排序樹查找；平均查找長度；編碼速度

1引言

作為一種即時(shí)碼，前綴碼[1]在信息編碼過程中得到廣泛應(yīng)用。其中，哈夫曼編碼[2]、香農(nóng)編碼[3]和費(fèi)諾編碼是最常見的前綴碼。設(shè)符號序列X=x1x2…xm包含n個(gè)互異符號ci(i=1,2,…,n)，即?xi∈X，有xi∈{c1,c2,…,cn}。bi是對應(yīng)ci的前綴碼，pi是ci在X中出現(xiàn)的概率，li是bi的碼長。所謂編碼，就是將X中的每個(gè)符號用對應(yīng)的碼字替換。對于符號序列X中的每個(gè)符號xi,如果存在cj=xi,則用碼字bi替換X中的xi。當(dāng)X中所有符號被碼字全部替換,則整個(gè)編碼過程結(jié)束。顯然,編碼時(shí)間取決于查找編碼表的時(shí)間。

對于一個(gè)符號序列的編碼，編碼時(shí)間[4，5]的長短取決于平均查找長度的大小。如果平均查找長度大，則編碼時(shí)間長；如果平均查找長度小，則編碼時(shí)間短。目前，針對編碼速度的研究尚未文獻(xiàn)報(bào)道。

為此，設(shè)計(jì)了5種不同的編碼算法。通過對這些算法的平均查找長度的比較，找出了編碼時(shí)間最優(yōu)的算法。算例測試表明，通過平均查找長度的計(jì)算和比較，可以找到編碼時(shí)間最短的算法。

2編碼算法

2.1順序查找法

對于符號序列X中的任何一個(gè)元素xi而言，為了從編碼表中找到對應(yīng)的碼字，需要從順序表C=c1c2…cm的第一個(gè)元素c1開始，依次與元素xi比較。如果存在某個(gè)符號cj=xi，則bj就是符號xi的碼字。將符號序列X中所有符號編碼的過程如下。

(1) 令i=1和Y=φ，它表示從X中的第一個(gè)符號x1開始編碼。

(2) 令j=1，它表示從C中的c1開始查找xi在C中的位置。

(3) 如果xi=cj，則轉(zhuǎn)步驟(4)；否則，轉(zhuǎn)步驟(5)。

(4) 令Y=Y∪{bj}，轉(zhuǎn)步驟(6)。

(5) 令j=j+1。如果j≤n，則轉(zhuǎn)步驟(1)；否則，由于編碼過程出錯(cuò)而終止計(jì)算機(jī)繼續(xù)編碼。

(6) 令i=i+1。如果i≤m，則轉(zhuǎn)步驟(2)；否則，編碼過程結(jié)束。

如果算法中出現(xiàn)j>n，則意味著符號序列中有某個(gè)符號無法編碼。事實(shí)上，除非碼字集本身存在問題，否則這種情況不可能發(fā)生。

2.2大概率優(yōu)先查找法

大概率優(yōu)先查找本質(zhì)上是一種順序查找法，唯一不同的是大概率符號一定會比小概率符號要先查找到。也就說，對于任意兩個(gè)不同符號xi和xj來說，如果pi>pj，則查找到xi所花費(fèi)的時(shí)間一定要比查找到xj所花費(fèi)的時(shí)間短。為了做到這一點(diǎn)，只需要對概率序列P=p1p2…pn進(jìn)行降序排序即可。需要說明的是，在概率序列降序排列的過程中，順序表C=c1c2…cm和編碼表B=b1b2…bm都需要相應(yīng)調(diào)換位置?？傊?jīng)過排序后，對?i∈{1,2,…,n}，符號ci對應(yīng)的概率是pi，而對應(yīng)的碼字是bi。同時(shí)，符號概率必須滿足p1≥p2≥…≥pn。

當(dāng)順序表中的符號滿足上述概率條件時(shí)，在此基礎(chǔ)上用順序查找法對符號序列進(jìn)行編碼，該編碼所花費(fèi)的時(shí)間一定比直接順序查找法要短。

2.3小概率優(yōu)先查找法

跟大概率優(yōu)先查找法一樣，小概率優(yōu)先查找法也是一種特殊的順序查找法。顧名思義，小概率優(yōu)先查找法就是小概率符號比大概率符號要先查找到。為了做到這一點(diǎn)，只需要將概率序列P=p1p2…pn進(jìn)行升序排序。同樣，在排序的過程，如果出現(xiàn)需要pi與pj交換，則相應(yīng)的需要進(jìn)行ci?cj和bi?bj。顯然，在順序表C=c1c2…cm中查找符號序列X中的任意符號時(shí)，那么小概率符號一定要比大概率符號先查找到。

2.4折半查找法

無論是順序查找法,還是大概率優(yōu)先查找法或小概率優(yōu)先查找法,整個(gè)符號序列的編碼速度都與符號的概率有關(guān).與這些方法不同的是,折半查找法的編碼速度與符號的概率無關(guān),只取決于符號本身的大小.如果順序表C=c1c2…cm是一個(gè)有序順序表,則可以用折半查找法對符號序列進(jìn)行編碼.如果順序表是一個(gè)升序序列,則對符號序列的編碼過程如下。

(1) 令i=1,表示從符號x1開始編碼.令Y=φ,表示對應(yīng)符號序列的初始編碼為空。

(2) 令l=1和h=1.此時(shí)l指示x1,而h指示xn.

(4) 如果xi>cm,則l=m+1;否則如果xi

(5) 如果xi=cm,則令Y=Y∪{bm}.

在上述算法中,沒有考慮符號編碼失敗的問題.因此,必須保證此處的碼字集是正確的。

上述算法中,每個(gè)符號的編碼速度只與它在有序順序表中的位置有關(guān),而與它自身的概率無關(guān).也就是說,概率大的符號的編碼速度有可能比概率小的符號的編碼速度小。

2.5二叉排序樹法

前面介紹的4種編碼方法查找的對象都是順序表,而二查排序樹查找的對象是二叉樹.對于二叉排序樹中的任何一個(gè)節(jié)點(diǎn)p,設(shè)其左孩子為p->lchild和右孩子為p->rchild,而節(jié)點(diǎn)信息為符號p->data和碼字p->b,其中p->b是符號p->data對應(yīng)的碼字.則由C=c1c2…cm可以建立一個(gè)二叉排序樹.如果設(shè)該二叉排序樹的根節(jié)點(diǎn)為t,則符號序列X的編碼過程描述如下。

(1) 令i=1,表示第一個(gè)需要編碼的符號是x1.令Y=φ,它表示編碼序列的初始化。

(2) 令s=t,它表示需要從二叉樹的根節(jié)點(diǎn)開始查詢。

(3) 如果s->data=xi,則Y=Y∪s->b并轉(zhuǎn)步驟(6)。

(4) 如果s->data>xi,則令s=s->lchild,轉(zhuǎn)步驟(3)。

(5)如果s->datarchild,轉(zhuǎn)步驟(3)。

(6) 令i=i+1.如果i≤m,則轉(zhuǎn)步驟(2);否則,編碼過程結(jié)束。

3編碼算法分析

算法2.1，算法2..2和算法2.3本質(zhì)上都是順序查找，不同的是他們的平均查找長度不同。要從順序表C=c1c2…cm中查找ci(i=1,2,…,n)，則查找成功的比較次數(shù)為li=i。所以，對符號序列X編碼的平均查找長度為：

(1)

由于算法2.2中大概率符號的查找長度短而小概率符號的查找長度長，故用它編碼的平均查找的長度短。相反，由于算法2.3中大概率符號的查找長度長而小概率符號的查找長度短，故用它編碼的平均查找的長度比較長。如果設(shè)L1，L2和L3分別表示算法2.1，算法2.2和算法2.3的平均查找長度，則他們之間的大小關(guān)系如下：

L2≤L1≤L3.

(2)

不等式(2)說明對于同一符號的編碼速度而言，這三種算法的平均查找長度是不一樣的。其中算法2.2的平均查找長度最短，而算法2.3的平均查找長度最長。

與算法2.1，算法2.2和算法2.3有本質(zhì)不同，算法2.4和算法2.5不是順序查找，而是跳躍查找。前三種算法的平均查找長度只與符號的概率有關(guān)，而與符號本身的大小無關(guān)。算法2.4和算法2.5的平均查找長度不僅與符號的概率有關(guān)，而且與符號自身的大小有關(guān)。如果用li表示查找到符號ci的比較次數(shù)，則算法2.4和算法2.5的平均查找長度為

(3)

要想計(jì)算用算法2.4進(jìn)行編碼的平均查找長度，必須求出每一個(gè)符號ci在有序順序表中的比較次數(shù)li。在有序順序表中查找ci的過程如下。

(1) 令li=0。對查找ci的比較次數(shù)進(jìn)行初始化。

(2) 令l=1和h=n。為第1次折半做準(zhǔn)備。

(4) 如果ci>cm，則l=m+1；否則如果ci

(5) 轉(zhuǎn)步驟3重復(fù)執(zhí)行步驟(3)和步驟(4)。

以上算法是在折半查找的基礎(chǔ)上統(tǒng)計(jì)查找ci的比較次數(shù)。

與算法2.4的統(tǒng)計(jì)查找的比較次數(shù)不同，算法2.5中每個(gè)符號的查找比較次數(shù)來自于二叉排序樹的查找。在二叉排序樹t中查找符號ci的比較次數(shù)的統(tǒng)計(jì)過程如下。

(1) 令li=1，表示查找ci時(shí)至少需要比較1次。

(2) 如果cidata，則t=t->lchild；否則如果ci>t->data，則t=t->rchild；否則，查找過程結(jié)束。

(3) 令li=li+1并轉(zhuǎn)步驟(2)重復(fù)執(zhí)行。

如果二叉排序樹是一棵嚴(yán)格平衡二叉樹，那么算法2.5的平均查找長度與算法2.4相等。否則，一般情況下，算法2.4的平均查找長度要小于算法2.5。如果L4和L5分別表示算法2.4和算法2.5的平均查找長度，那么一定有下面的關(guān)系：

L4≤L5.

(4)

通過對以上5種算法的分析，要想提高符號序列的編碼速度，只需在算法2.2和算法2.4之間選擇，即最小的平均查找長度為：

L=min{L2,L4}.

(5)

因此，從對同一符號序列的編碼速度而言，有時(shí)算法2.4的速度最快，有時(shí)算法2.2的速度最快。當(dāng)用算法2.5建立的二叉樹是嚴(yán)格平衡二叉樹時(shí),有L4=L5.

4算例

例1已知符號序列X中包含a,b,c,d,e,f六種符號，其對應(yīng)的概率分別為{0.06,0.15,0.14,0.4,0.2,0.05}..分別用上面介紹的5種方法求對符號序列X進(jìn)行編碼的平均查找長度。

解1)如果用算法2.1 求X平均查找長度，則C=abcdef，而p={0.06,0.15,0.14,0.4,0.2,0.05}，所以算法2.1編碼的平均查找長度為L1=0.06×1+0.15×2+0.14×3+0.4×4+0.2×5+0.05×6=3.78。

2)如果用算法2.2 求X平均查找長度，則C=debcaf，而p={0.4,0.2,0.15,0.14,0.06,0.05}，所以算法2.2編碼的平均查找長度為L2=0.4×1+0.2×2+0.15×3+0.14×4+0.06×5+0.05×6=2.49。

3)如果用算法2.3 求X平均查找長度，則C=facbed，而p={0.05,0.06,0.14,0.15,0.2,0.4}，所以算法2.3編碼的平均查找長度為L3=0.05×1+0.06×2+0.14×3+0.15×4+0.2×5+0.4×6=4.59。

4)如果用算法2.4 求X平均查找長度，則C=abcdef，所以l3=1，l1=l5=2和l2=l4=l6=3。故由算法2.4編碼的平均查找長度為L1=0.06×2+0.15×3+0.14×1+0.4×3+0.2×2+0.05×3=2.46。

5)如果用算法2.5 求X平均查找長度，則C=abcdef，所以編碼的平均查找長度為L1=0.06×1+0.15×2+0.14×3+0.4×4+0.2×5+0.05×6=3.78。

通過上述計(jì)算的平均查找長度比較，用算法2.4編碼的速度最優(yōu)。

例2已知符號序列X中包含a,b,c,d,e,f六種符號，其對應(yīng)的概率分別為{0.01,0.02,0.03,0.04,0.05,0.85}..求對符號序列X進(jìn)行編碼的最短平均查找長度。

解1)如果用算法2.2求平均查找長度,則C=fedcba和p={0.85,0.05,0.04,0.0.03.002,0.01}.因此,由算法2.2求得的平均查找長度L2=0.85×1+0.05×2+0.04×3+0.03×4+0.02×5+0.01×6=1.44.

2)如果用算法2.4 求X平均查找長度，則C=abcdef和p={0.01,0.02,0.03,0.04,0.05,0.85}.由折半查找有l(wèi)3=1，l1=l5=2和l2=l4=l6=3。故由算法2.4編碼的平均查找長度為L4=(0.01+0.05)×2+0.03×1+(0.02+0.04+0.85)×3=2.88.

3)如果用算法2.5 求X平均查找長度，則由C=abcdef建立的二叉排序樹有l(wèi)i=i,i=1,2,…,6。故由算法2.5編碼的平均查找長度為L5=0.01×1+0.02×2+0.03×3+0.04×4+0.05×5+0.85×6=5.65.

通過上述計(jì)算的平均查找長度比較，用算法2.2編碼的速度最優(yōu)。

例3已知符號序列X中包含c,a,e,b,d,f六種符號，其對應(yīng)的概率分別為{0.4,0.2,0.14,0.15,0.05,0.06}..求對符號序列X進(jìn)行編碼的最短平均查找長度。

解1)如果用算法2.2求平均查找長度,則C=cabefd和p={0.4,0.2,0.15,0.14,0.06,0.05}.因此,由算法2.2求得的平均查找長度L2=0.4×1+0.2×2+0.15×3+0.14×4+0.06×5+0.05×6=2.49.

2)如果用算法2.4 求X平均查找長度，則C=abcdef和p={0.2,0.15,0.4,0.05,.14,0.06}.由折半查找有l(wèi)3=1，l1=l5=2和l2=l4=l6=3。故由算法2.4編碼的平均查找長度為L4=0.2×2+0.15×3+0.4×1+0.05×3+0.15×2+0.06×3=1.88.

3)如果用算法2.5 求X平均查找長度，則由C=cabefd建立的二叉排序樹是一棵嚴(yán)格平衡二叉樹,故有l(wèi)3=1，l1=l5=2和l2=l4=l6=3。故由算法2.5編碼的平均查找長度為L5=0.2×2+0.15×3+0.4×1+0.05×3+0.15×2+0.06×3=1.88.

通過上述計(jì)算的平均查找長度比較，用算法2.4和算法2.5編碼的速度最優(yōu)。

5結(jié)束語

在對符號序列的編碼速度進(jìn)行深入分析的基礎(chǔ)上,設(shè)計(jì)了5種不同的編碼算法.通過對這些編碼算法的平均查找長度的比較,發(fā)現(xiàn)大概率優(yōu)先查找算法或折半查找算法的平均查找長度是最短的.算例表明,對于一個(gè)具體的符號序列進(jìn)行編碼,為了得到最快的編碼速度,只需要從大概率優(yōu)先查找和折半查找這兩種算法中選擇平均查找長度最短的編碼算法即可.

參考文獻(xiàn)：

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

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

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

[4]郭蕾,李東輝 ,繆志甫. 結(jié)合壓縮感知理論的快速分形編碼[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2012,9，33(9)：3494-3497.

[5]汪大勇,孫世新,楊浩淼. 一種基于殘差系數(shù)的快速編碼算法[J]. 電子與信息學(xué)報(bào), 2010,11，32(11)：2541-2546.

Fast encoding algorithm research based on prefix codes

WANGFang-xiu

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

Abstract：In view of the current symbol sequence encoding having the problem of slow encoding speed, this paper proposes an algorithm to improve the encoding speed by reducing the average search length. According to the symbol probability, it designs three coding algorithm that are a sequential search, big probability priority first search and small probability priority first search. Through the analysis and comparison of the average search length of the three coding algorithm, teh results show that the average search length is the shortest for the big probability priority search algorithm.According to the size of the symbol itself, it designs two kinds of coding algorithm,one binary search and the other two binary sort tree search. Through the analysis of the average search length of the two coding algorithm, the results show that the average search length of the binary search algorithm is the shortest. Therefore, the optimal coding algorithm must be selected from one of big probability priority search algorithm and binary search algorithm. Examples show that, in order to improve the encoding speed of the symbol sequence ,for the same symbol sequences,one must be chosn between big probability priority search algorithm and binary search algorithm which has the shortest average search length as the coding algorithm.

Key words：sequential search;binary search;two binary sort tree search;average search length;coding speed

中圖分類號：TP 391

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