一种香农编码优化算法的改进
2015-12-17王防修熊海梦
余 结，王防修，胡 迪，熊海梦，胡 义
(武汉轻工大学 数学与计算机学院,湖北 武汉 430023)
一种香农编码优化算法的改进
余结，王防修，胡迪，熊海梦，胡义
(武汉轻工大学 数学与计算机学院,湖北 武汉 430023)
摘要：针对香农编码优化算法在编码效率方面存在的不足，提出一种基于信源符号码字重新分配而使平均码长变短的优化算法。新算法在原优化算法的基础上，通过判断优化码的码长是否随概率的递减而递增来决定该优化码是否需要进一步优化。鉴于改进算法只对优化码的码长不是随概率的递减而递增的情形才有效，首先设计一个优化码能否改进的判断算法，通过对优化码的判断，然后对能进一步优化的优化码用改进算法优化。改进算法用选择排序算法对优化码进行重新分配，使得分配后的码字满足码长随概率的递减而递增。算例仿真表明，对能进一步优化的优化码，改进算法可以进一步提高优化算法的编码效率。
关键词：香农编码；优化算法；编码效率；改进算法；选择排序
1引言
在数据传输和存储过程中，为提高通信效率，有必要对数据信息进行压缩处理。作为一种重要的变长编码[1]技术，香农编码对此具有重要的理论指导意义。因此，对香农编码的研究与实现一直是人们关注的热点[2-8]。虽然文献[9]对香农编码算法进行了优化，也一定程度上提高了香农编码的编码效率，但通过算法测试发现，经过该算法编码得到的码字有时会出现大概率符号对应长码字而小概率符号对应短码字的情况，使得该算法的平均码长还可以进一步缩短。为了进一步提高该优化算法的编码效率，本文提出了一种通过对码字进行升序排序和码字重新分配的方法对算法加以改进，使得用改进算法得到的编码总是大概率事件对应短码字而小概率事件对应长码字。算法仿真表明，与原优化算法相比，改进算法可以使信源符号的编码效率得到进一步提高。
2香农编码优化算法及其存在的问题
(1)
2.1香农编码的优化算法
香农编码的优化步骤如下：
1)对n个信源符号xi的概率进行降序排列，即满足
p1≥p2≥…≥pn.
(2)
2)所有码字取相同的码长
(3)
4)将每个累加概率Pi转化为二进制数，取小数点后l位二进制数作为备用码字，即
Pi=Pi-1+pi-1，i=2,3,…,n.
(4)
(5)
i=1,2,…,n和j=1,2,…,l，bi,j表示码字bi的第j位二进制数，bi满足
Pi=(0.bi…)2.
(6)
即bi是Pi的小数点后的l位二进制数。
5)对备用码字进行优化，使任意一个码字都不是其它码字的前缀[10-11]，同时每个码字的码长尽可能短。
其优化过程如下：
a.初始化码字指示器i=1；
b.设置码字指示器j=1和kmax=0；
c.如果i≠j，则计算bi与bj的不同二进制位的位置，即
bi(k-1)=bj(k-1).
(7)
和
bi,k≠bj,k.
(8)
其中bi(l)表示取码字bi的前l位，而bi,k表示码字bi的第k位二进制位，则k表示bi与bj互为前缀码的最小位置。
如果k>kmax，则kmax=k
(9)
d.如果j e.根据最终求得的kmax更新备用码字bi，使得bi=bi(kmax). (10) f.如果i 由于备用码字经过优化后，经常会出现大概率符号对应长码字而小概率符号对应短码字的情形。因此，有必要对生成的码字进行调整，使得最终的码字满足大概率符号对应短码字而小概率符号对应长码字。只有这样，才能使信源符号的平均码长最短。 3算法改进 设概率为pi的信源符号xi经过优化编码后的码字为bi，其中概率pi满足式(2)。为了实现大概率符号对应短码字而小概率符号对应长码字，只需要对bi根据码长进行升序排序，使得最终获得 l(bi1)≤l(bi2)≤…≤l(bin). (11) 然后，重新分配信源符号xj的码字为bij，j=1,2,…,n。 如果优化码bi的码长是li，i=1,,…,n，则有 (12) 即改进码的平均码长一般要小于优化码，故改进码的编码效率一般要高于优化码。 不是任何优化码都能用改进的算法进一步优化，只有当优化码的码长不是单调递增时才行。即当p1≥p2≥…≥pn时，如果出现对应的优化码的码长满足l1≤l2≤…≤ln，则该优化码就一定无法被改进算法优化；反之，如果∃i a.初始化。使i=1，表示i指示第一个码字的码长； b.如果li>li+1，则转至步骤d. c.如果i d.如果i e.如果i=n-1且ln-1>ln，则优化码可以被进一步优化。 3.2基于选择排序的码字分配 所谓码字分配，就是指概率大的符号得到短码字而概率小的符号得到长码字。 因此，可以根据码长进行升序排序来实现码字的重新分配。这里不妨用选择排序算法对码字重新排序的过程描述如下： a.计算码字的码长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的码字对应为bi，i=1,2,…,n. 码字bi经过选择排序后，得到的码字满足 l(b1)≤l(b2)≤…≤l(bn). (13) 这样，信源符号xi的概率越大，则其码长越短；反之，概率越小，码长越长。则由 (14) 可知码字的平均码长越小，从而编码效率越高。 4算法仿真 下面几个算例使用VC6.0作为仿真工具，在CPU为3.2 GHz和内存为1.86 GB的个人台式电脑上完成仿真。下面算例均要求用香农编码，优化编码和改进编码对信源符号进行编码。 算例1现有12个信源符号，其概率分布如表1所示。 表1 12个信源符号的概率分布 通过使用三种不同算法进行编码，可以得到如表2所示的编码结果。 表2 12个信源符号的编码结果比较 由信源的熵公式 (15) 和公式(13)，可以求得编码效率为 (16) 因此，求得三种不同算法的编码效率如表3所示。 表3 12个信源符号的编码效率比较 算例2现有6个信源符号，其概率分布如表4所示。 表4 6个信源符号的概率分布 通过使用三种不同算法进行编码，可以得到如表5所示的编码结果。 表5 6个信源符号的编码结果比较 同样，求得三种不同算法的编码效率如表6所示。 表6 6个信源符号的编码效率比较 算例3表7是4个信源符号的编码结果。 根据编码效率的计算公式，可知香农编码的编码效率为η=0.769 350，而优化算法的编码效率为η=0.923 220。 表7 4个信源符号的编码结果比较 对算例1和算例2的编码结果进行比较，可以看出本文算法较之香农编码优化算法而言，其编码效率有不同程度的提高。算例3由于码长是随概率的递减而递增，故优化码不能被进一步优化。其次，对不同个数的信源符号进行编码，编码效率也可能会有所不同。 5结论 由于本文提出的算法是香农编码优化算法的改进，它是在优化编码的基础上对优化码进一步优化，故它的编码效率一般要高于优化编码算法。 优化编码算法之所以编码效率要高于香农编码，是因为优化编码算法可以得到更短的平均码长。同样，如果优化编码算法得到的码长不是随概率递减而递增，则与优化算法相比，用改进算法进行编码又可以得到更短的平均码长。所以一般情况下，优化编码的编码效率要高于香农编码，而改进算法的编码效率又要优于优化编码。通过对改进算法的分析，可以得出如下结论。 1)本文所提算法的编码编码效率一般要高于优化编码； 2)只有当优化码的码长不是随概率递减而递增时，才考虑用改进算法对优化码进一步优化； 3)对不同个数的信源符号，改进算法对编码效率的提高会有所不同； 4)即使信源符号的个数相同，改进算法对编码效率的提高也可能会有不同。 参考文献： [1]叶芝慧，沈克勤.信息论与编码[M].北京：电子工业出版社 ,2013. [2]杨扬,申石磊.支持更新的XML编码方案[J].计算机工程与设计, 2012,33(4)：1629-1632. [3]谭鹏许,陈越. 基于广播加密的安全容错编码[J].计算机工程与设计, 2013，34(10)：3417-3421. [4]邢楠,朱虹. 一种快速判断非唯一可译码的方法[J].无线通信技术, 2008，31(2)：29-31. [5]刘忆宁.信息论教学中的程序设计[J]. 桂林电子科技大学学报,2008,28(4)：338-341. [6]郭姝,施滔滔.浅谈香农编码的JAVA实现及其效率分析[J]. 中国西部科技, 2009,8(27)：44-46. [7]张燕红 ,王燕.几种常用图像压缩编码方法的研究及C#实现[J]. 计算技术与自动化,2013，32(3)：60-63. [8]张晓梅.常见离散信源编码方法的比较[J].福建电脑, 2009(5)：64-66. [9]邵军花 ,刘玉红.香农编码的优化算法研究[J].兰州交通大学学报,2010,29(6):110-113. [10]谢勰.关于Shannon编码的若干注记[J].西安邮电学院学报, 2009,14(3)：58-60. [11]舒季君,沈传龙.d-L前缀码的完全化构造方法[J].杭州师范学院学报, 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 基金项目：河南省教育厅科学技术研究重点项目课题(15B520026，15B520025). 作者简介：董萍(1980-)，女，讲师，E-mail：dongpingms2008@163.com. 收稿日期：2015-04-08. 中图分类号：TP 391 文献标识码：A2.2 香农编码优化算法存在的不足
3.1 优化码进一步优化的判断依据
