一种香农编码优化算法的改进

1、一种香农编码优化算法的改进余结;王防修;胡迪;熊海梦;胡义【摘 要】针对香农编码优化算法在编码效率方面存在的不足,提出一种基于信源符 号码字重新分配而使平均码长变短的优化算法。新算法在原优化算法的基础上,通 过判断优化码的码长是否随概率的递减而递增来决定该优化码是否需要进一步优化 鉴于改进算法只对优化码的码长不是随概率的递减而递增的情形才有效,首先设计 一个优化码能否改进的判断算法,通过对优化码的判断,然后对能进一步优化的优化 码用改进算法优化。改进算法用选择排序算法对优化码进行重新分配,使得分配后 的码字满足码长随概率的递减而递增。算例仿真表明,对能进一步优化的优化码,改 进算法可以进一步提

2、高优化算法的编码效率。期刊名称】武汉轻工大学学报年(卷),期】2015(034)002【总页数】4页(P83-86) 【关键词】 香农编码;优化算法;编码效率;改进算法;选择排序【作 者】 余结;王防修;胡迪;熊海梦;胡义【作者单位】 武汉轻工大学数学与计算机学院,湖北武汉 430023【正文语种】 中 文【中图分类】 TP391在数据传输和存储过程中，为提高通信效率，有必要对数据信息进行压缩处理。作为一种重要的变长编码1技术，香农编码对此具有重要的理论指导意义。因此， 对香农编码的研究与实现一直是人们关注的热点2-8。虽然文献9对香农编码算 法进行了优化，也一定程度上提高了香农编码的编码效率

3、，但通过算法测试发现， 经过该算法编码得到的码字有时会出现大概率符号对应长码字而小概率符号对应短 码字的情况，使得该算法的平均码长还可以进一步缩短。为了进一步提高该优化算 法的编码效率，本文提出了一种通过对码字进行升序排序和码字重新分配的方法对 算法加以改进，使得用改进算法得到的编码总是大概率事件对应短码字而小概率事 件对应长码字。算法仿真表明，与原优化算法相比，改进算法可以使信源符号的编 码效率得到进一步提高。设单信源X二x1,x2,.,xn,其中信源符号xi对应的概率为Ovpis1,i=12.,n和。 如果符号xi经过香农编码后得到的码字为bi，则依据香农第一定理，码字bi对应 的码长li

4、满足关系式口，i=1,2,.,n.香农编码的优化步骤如下：1）对n个信源符号xi的概率进行降序排列，即满足p1p2.pn.2）所有码字取相同的码长.4）将每个累加概率Pi转化为二进制数，取小数点后l位二进制数作为备用码字，即Pi=Pi-1+pi-1，i=2,3,.,n.和.i=12.,n和j=12.,l, bi,j表示码字bi的第j位二进制数，bi满足Pi=（0.bi.）2.即bi是Pi的小数点后的l位二进制数。5)对备用码字进行优化，使任意一个码字都不是其它码字的前缀10-11，同时每 个码字的码长尽可能短。其优化过程如下：初始化码字指示器i=1;设置码字指示器j=1和k max=0 ;如果

5、iHj,则计算bi与bj的不同二进制位的位置，即如果 1kk max，则 k max二k如果jn，则使j=j+1并返回步骤c.根据最终求得的k max更新备用码字bi，使得bi=bi(k max).如果ivn，则使i=i+1并返回步骤b.由于备用码字经过优化后，经常会出现大概率符号对应长码字而小概率符号对应短 码字的情形。因此，有必要对生成的码字进行调整，使得最终的码字满足大概率符 号对应短码字而小概率符号对应长码字。只有这样，才能使信源符号的平均码长最 短。设概率为pi的信源符号xi经过优化编码后的码字为bi，其中概率pi满足式(2)。 为了实现大概率符号对应短码字而小概率符号对应长码字，只

6、需要对bi根据码长 进行升序排序，使得最终获得I(bi1)l(bi2).l(bin).然后，重新分配信源符号Xj的码字为bij ,j=12.,n。如果优化码bi的码长是li ,i=1.,n,则有p2.pn时，如果出现对应的优化码的码长满足I1l2.pj ,s.t.lilj，则该优化码就可用改进算法优化。因此，判断优化码能否被进一步优化 的算法如下：初始化。使i=1,表示i指示第一个码字的码长；如果lili+1,则转至步骤d.如果ivn-1,则使i二i+1且重复步骤b.如果ivn-1,则优化码可以被进一步优化；如果i二n-1且ln-1ln，则优化码可以被进一步优化。3.2 基于选择排序的码字分配

7、所谓码字分配，就是指概率大的符号得到短码字而概率小的符号得到长码字。 因此，可以根据码长进行升序排序来实现码字的重新分配。这里不妨用选择排序算 法对码字重新排序的过程描述如下：计算码字的码长 li=len(bi) ,i=1,.,n.初始化码长指示器i=1;使h = i ,表示h是需要竞争的位置；j=i+1,如果 ljvlh，则 h=j ；如果jvn，则重复步骤d.如果 h/i,则 lh-li 和 bh-bi ；如果ivn-1,则返回步骤c.信源符号xi的码字对应为bi ,i=1,2,.,n.码字bi经过选择排序后，得到的码字满足I(b1)?(b2)s.?(bn).这样，信源符号xi的概率越大，

8、则其码长越短；反之，概率越小，码长越长。则 由).可知码字的平均码长越小，从而编码效率越高。下面几个算例使用VC6.0作为仿真工具，在CPU为3.2 GHz和内存为1.86 GB 的个人台式电脑上完成仿真。下面算例均要求用香农编码，优化编码和改进编码对 信源符号进行编码。算例1 现有12个信源符号，其概率分布如表1所示。 通过使用三种不同算法进行编码，可以得到如表2所示的编码结果。由信源的熵公式H(X)=-piIogpi.和公式(13)，可以求得编码效率为因此，求得三种不同算法的编码效率如表3所示。算例2 现有6个信源符号，其概率分布如表4所示。 通过使用三种不同算法进行编码，可以得到如表5所

9、示的编码结果。同样，求得三种不同算法的编码效率如表6所示。算例3 表7是4个信源符号的编码结果。根据编码效率的计算公式，可知香农编码的编码效率为n=0.769 350,而优化算 法的编码效率为n=0.923 220。对算例1和算例2的编码结果进行比较，可以看出本文算法较之香农编码优化算 法而言，其编码效率有不同程度的提高。算例 3 由于码长是随概率的递减而递增， 故优化码不能被进一步优化。其次，对不同个数的信源符号进行编码，编码效率也 可能会有所不同。由于本文提出的算法是香农编码优化算法的改进，它是在优化编码的基础上对优化 码进一步优化，故它的编码效率一般要高于优化编码算法。优化编码算法之所以

10、编码效率要高于香农编码，是因为优化编码算法可以得到更短的平均码长。同样，如果优化编码算法得到的码长不是随概率递减而递增，则与优化算法相比，用改进算法进行编码又可以得到更短的平均码长。所以一般情况下，优化编码的编码效率要高于香农编码，而改进算法的编码效率又要优于优化编码。 通过对改进算法的分析，可以得出如下结论。1)本文所提算法的编码编码效率一般要高于优化编码；2)只有当优化码的码长不是随概率递减而递增时，才考虑用改进算法对优化码进一 步优化；对不同个数的信源符号，改进算法对编码效率的提高会有所不同；即使信源符号的个数相同，改进算法对编码效率的提高也可能会有不同。【相关文献】叶芝慧，沈克勤信息论

11、与编码M.北京：电子工业出版社,2013.杨扬,申石磊支持更新的XML编码方案J.计算机工程与设计,2012,33(4) : 1629-1632.谭鹏许，陈越.基于广播加密的安全容错编码J.计算机工程与设计,2013，34(10) : 3417-3421.邢楠，朱虹.一种快速判断非唯一可译码的方法J.无线通信技术,2008，31(2) : 29-31. 刘忆宁信息论教学中的程序设计J.桂林电子科技大学学报,2008,28(4) : 338-341. 郭姝,施滔滔浅谈香农编码的JAVA实现及其效率分析J.中国西部科技,2009,8(27) : 44-46.张燕红，王燕几种常用图像压缩编码方法的研究及C#实现J.计算技术与自动化,2013，32(3)：60-63.张晓梅常见离散