基于前缀码的快速编码算法研究

王防修

(武汉轻工大学 数学与计算机学院,湖北 武汉 430023)



基于前缀码的快速编码算法研究

王防修

(武汉轻工大学 数学与计算机学院,湖北 武汉 430023)

摘要：针对目前符号序列的编码存在编码速度慢的问题，提出了一种通过减少平均查找长度来提高编码速度的算法。根据符号概率的大小，设计了顺序查找、大概率优先查找和小概率优先查找三种编码算法。通过对这三种编码算法的平均查找长度的分析比较，结果表明：大概率优先查找算法的平均查找长度最短。根据符号本身的大小，设计了折半查找和二叉排序树查找两种编码算法。通过对这两种编码算法的平均查找长度的分析比较，结果表明折半查找编码算法的平均查找长度最短。因此，最优的编码算法应从大概率优先查找算法和折半查找算法之中选择其一。算例表明，为了提高符号序列的编码速度，对同一符号序列的编码，应从大概率优先查找算法和折半查找算法中选择平均查找长度最短的算法作为编码算法。

关键词：顺序查找；折半查找；二叉排序树查找；平均查找长度；编码速度

1引言

作为一种即时码，前缀码[1]在信息编码过程中得到广泛应用。其中，哈夫曼编码[2]、香农编码[3]和费诺编码是最常见的前缀码。设符号序列X=x1x2…xm包含n个互异符号ci(i=1,2,…,n)，即∀xi∈X，有xi∈{c1,c2,…,cn}。bi是对应ci的前缀码，pi是ci在X中出现的概率，li是bi的码长。所谓编码，就是将X中的每个符号用对应的码字替换。对于符号序列X中的每个符号xi,如果存在cj=xi,则用码字bi替换X中的xi。当X中所有符号被码字全部替换,则整个编码过程结束。显然,编码时间取决于查找编码表的时间。

对于一个符号序列的编码，编码时间[4，5]的长短取决于平均查找长度的大小。如果平均查找长度大，则编码时间长；如果平均查找长度小，则编码时间短。目前，针对编码速度的研究尚未文献报道。

为此，设计了5种不同的编码算法。通过对这些算法的平均查找长度的比较，找出了编码时间最优的算法。算例测试表明，通过平均查找长度的计算和比较，可以找到编码时间最短的算法。

2编码算法

2.1顺序查找法

对于符号序列X中的任何一个元素xi而言，为了从编码表中找到对应的码字，需要从顺序表C=c1c2…cm的第一个元素c1开始，依次与元素xi比较。如果存在某个符号cj=xi，则bj就是符号xi的码字。将符号序列X中所有符号编码的过程如下。

(1) 令i=1和Y=φ，它表示从X中的第一个符号x1开始编码。

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

(3) 如果xi=cj，则转步骤(4)；否则，转步骤(5)。

(4) 令Y=Y∪{bj}，转步骤(6)。

(5) 令j=j+1。如果j≤n，则转步骤(1)；否则，由于编码过程出错而终止计算机继续编码。

(6) 令i=i+1。如果i≤m，则转步骤(2)；否则，编码过程结束。

如果算法中出现j>n，则意味着符号序列中有某个符号无法编码。事实上，除非码字集本身存在问题，否则这种情况不可能发生。

2.2大概率优先查找法

大概率优先查找本质上是一种顺序查找法，唯一不同的是大概率符号一定会比小概率符号要先查找到。也就说，对于任意两个不同符号xi和xj来说，如果pi>pj，则查找到xi所花费的时间一定要比查找到xj所花费的时间短。为了做到这一点，只需要对概率序列P=p1p2…pn进行降序排序即可。需要说明的是，在概率序列降序排列的过程中，顺序表C=c1c2…cm和编码表B=b1b2…bm都需要相应调换位置。总之，经过排序后，对∀i∈{1,2,…,n}，符号ci对应的概率是pi，而对应的码字是bi。同时，符号概率必须满足p1≥p2≥…≥pn。

当顺序表中的符号满足上述概率条件时，在此基础上用顺序查找法对符号序列进行编码，该编码所花费的时间一定比直接顺序查找法要短。

2.3小概率优先查找法

跟大概率优先查找法一样，小概率优先查找法也是一种特殊的顺序查找法。顾名思义，小概率优先查找法就是小概率符号比大概率符号要先查找到。为了做到这一点，只需要将概率序列P=p1p2…pn进行升序排序。同样，在排序的过程，如果出现需要pi与pj交换，则相应的需要进行ci↔cj和bi↔bj。显然，在顺序表C=c1c2…cm中查找符号序列X中的任意符号时，那么小概率符号一定要比大概率符号先查找到。

2.4折半查找法

无论是顺序查找法,还是大概率优先查找法或小概率优先查找法,整个符号序列的编码速度都与符号的概率有关.与这些方法不同的是,折半查找法的编码速度与符号的概率无关,只取决于符号本身的大小.如果顺序表C=c1c2…cm是一个有序顺序表,则可以用折半查找法对符号序列进行编码.如果顺序表是一个升序序列,则对符号序列的编码过程如下。

(1) 令i=1,表示从符号x1开始编码.令Y=φ,表示对应符号序列的初始编码为空。

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

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

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

在上述算法中,没有考虑符号编码失败的问题.因此,必须保证此处的码字集是正确的。

上述算法中,每个符号的编码速度只与它在有序顺序表中的位置有关,而与它自身的概率无关.也就是说,概率大的符号的编码速度有可能比概率小的符号的编码速度小。

2.5二叉排序树法

前面介绍的4种编码方法查找的对象都是顺序表,而二查排序树查找的对象是二叉树.对于二叉排序树中的任何一个节点p,设其左孩子为p->lchild和右孩子为p->rchild,而节点信息为符号p->data和码字p->b,其中p->b是符号p->data对应的码字.则由C=c1c2…cm可以建立一个二叉排序树.如果设该二叉排序树的根节点为t,则符号序列X的编码过程描述如下。

(1) 令i=1,表示第一个需要编码的符号是x1.令Y=φ,它表示编码序列的初始化。

(2) 令s=t,它表示需要从二叉树的根节点开始查询。

(3) 如果s->data=xi,则Y=Y∪s->b并转步骤(6)。

(4) 如果s->data>xi,则令s=s->lchild,转步骤(3)。

(5)如果s->datarchild,转步骤(3)。

(6) 令i=i+1.如果i≤m,则转步骤(2);否则,编码过程结束。

3编码算法分析

算法2.1，算法2..2和算法2.3本质上都是顺序查找，不同的是他们的平均查找长度不同。要从顺序表C=c1c2…cm中查找ci(i=1,2,…,n)，则查找成功的比较次数为li=i。所以，对符号序列X编码的平均查找长度为：

(1)

由于算法2.2中大概率符号的查找长度短而小概率符号的查找长度长，故用它编码的平均查找的长度短。相反，由于算法2.3中大概率符号的查找长度长而小概率符号的查找长度短，故用它编码的平均查找的长度比较长。如果设L1，L2和L3分别表示算法2.1，算法2.2和算法2.3的平均查找长度，则他们之间的大小关系如下：

L2≤L1≤L3.

(2)

不等式(2)说明对于同一符号的编码速度而言，这三种算法的平均查找长度是不一样的。其中算法2.2的平均查找长度最短，而算法2.3的平均查找长度最长。

与算法2.1，算法2.2和算法2.3有本质不同，算法2.4和算法2.5不是顺序查找，而是跳跃查找。前三种算法的平均查找长度只与符号的概率有关，而与符号本身的大小无关。算法2.4和算法2.5的平均查找长度不仅与符号的概率有关，而且与符号自身的大小有关。如果用li表示查找到符号ci的比较次数，则算法2.4和算法2.5的平均查找长度为

(3)

要想计算用算法2.4进行编码的平均查找长度，必须求出每一个符号ci在有序顺序表中的比较次数li。在有序顺序表中查找ci的过程如下。

(1) 令li=0。对查找ci的比较次数进行初始化。

(2) 令l=1和h=n。为第1次折半做准备。

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

(5) 转步骤3重复执行步骤(3)和步骤(4)。

以上算法是在折半查找的基础上统计查找ci的比较次数。

与算法2.4的统计查找的比较次数不同，算法2.5中每个符号的查找比较次数来自于二叉排序树的查找。在二叉排序树t中查找符号ci的比较次数的统计过程如下。

(1) 令li=1，表示查找ci时至少需要比较1次。

(2) 如果cidata，则t=t->lchild；否则如果ci>t->data，则t=t->rchild；否则，查找过程结束。

(3) 令li=li+1并转步骤(2)重复执行。

如果二叉排序树是一棵严格平衡二叉树，那么算法2.5的平均查找长度与算法2.4相等。否则，一般情况下，算法2.4的平均查找长度要小于算法2.5。如果L4和L5分别表示算法2.4和算法2.5的平均查找长度，那么一定有下面的关系：

L4≤L5.

(4)

通过对以上5种算法的分析，要想提高符号序列的编码速度，只需在算法2.2和算法2.4之间选择，即最小的平均查找长度为：

L=min{L2,L4}.

(5)

因此，从对同一符号序列的编码速度而言，有时算法2.4的速度最快，有时算法2.2的速度最快。当用算法2.5建立的二叉树是严格平衡二叉树时,有L4=L5.

4算例

例1已知符号序列X中包含a,b,c,d,e,f六种符号，其对应的概率分别为{0.06,0.15,0.14,0.4,0.2,0.05}..分别用上面介绍的5种方法求对符号序列X进行编码的平均查找长度。

解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。

通过上述计算的平均查找长度比较，用算法2.4编码的速度最优。

例2已知符号序列X中包含a,b,c,d,e,f六种符号，其对应的概率分别为{0.01,0.02,0.03,0.04,0.05,0.85}..求对符号序列X进行编码的最短平均查找长度。

解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}.由折半查找有l3=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建立的二叉排序树有li=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.

通过上述计算的平均查找长度比较，用算法2.2编码的速度最优。

例3已知符号序列X中包含c,a,e,b,d,f六种符号，其对应的概率分别为{0.4,0.2,0.14,0.15,0.05,0.06}..求对符号序列X进行编码的最短平均查找长度。

解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}.由折半查找有l3=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建立的二叉排序树是一棵严格平衡二叉树,故有l3=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.

通过上述计算的平均查找长度比较，用算法2.4和算法2.5编码的速度最优。

5结束语

在对符号序列的编码速度进行深入分析的基础上,设计了5种不同的编码算法.通过对这些编码算法的平均查找长度的比较,发现大概率优先查找算法或折半查找算法的平均查找长度是最短的.算例表明,对于一个具体的符号序列进行编码,为了得到最快的编码速度,只需要从大概率优先查找和折半查找这两种算法中选择平均查找长度最短的编码算法即可.

参考文献：

[1]叶芝慧，沈克勤.信息论与编码[M].北京：电子工业出版社 ,2013.

[2]程佳佳，熊志斌.哈夫曼算法在数据压缩中的应用[J] 科学技术与工程, 2010，2：35-37.

[3]邵军花,刘玉红,周东梅.香农编码的优化算法研究 [J]. 兰州交通大学学报,2010,29(6):110-113.

[4]郭蕾,李东辉 ,缪志甫. 结合压缩感知理论的快速分形编码[J]. 计算机工程与设计,2012,9，33(9)：3494-3497.

[5]汪大勇,孙世新,杨浩淼. 一种基于残差系数的快速编码算法[J]. 电子与信息学报, 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

文献标识码：A