自适应算术编码

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,自适应算术编码,自适应算术编码原理,算术编码有固定模式和自适应模式两种编码方法。,在自适应模式中，各个符号初始值设为相同值，它们依据出现的符号而相应的改变其概率值，若出现新的符号只需要在符号表中添加即可，只要编码器和译码器使用相同的初始值和相同的改变值得方法，那么它们的概率模型将保持一致。编码器接收到下一个符号对其编码，然后改变概率模型，解码器根据当前的模式译码，然后改变自己的概率模型。,编码举例,算术编码将整个要编码的数据映射到一个位于,0,1),的实数区间中。并且输出一个小于,1,同时大于,0,的小数来表示全部数据。利用这种方法算术编码可以让压缩率无限的接近数据的熵值，从而获得理论上的最高压缩率。,算术编码进行编码时，从实数区间,0,1),开始。按照符号的频度将当前的区间分割成多个子区间。根据当前输入的符号选择对应的子区间，然后从选择的子区间中继续进行下一轮的分割。不断的进行这个过程，直到所有符号编码完毕。对于最后选择的一个子区间，输出属于该区间的一个小数。这个小数就是所有数据的编码。现在来举个例子。假设一份数据由“,A”,、“,B”,、“,C”,三个符号组成。现在要编码数据“,BCCB”,，编码过程如图所示。,“,BCCB”,的编码过程,编码过程,由于是自适应模型，设三个符号的频度都是,1,。随着编码的进行再更新频度。另外，在计算时理论上要使用无限小数。这里为了说明方便，四舍五入到小数点后,4,位。,观察图可以发现算术编码的过程。首先，算术编码是从区间,0,1),开始的。这时三个符号的概率都是,1/3,，按照这个概率分割区间。第一个输入的符号是“,B”,，所以选择子区间,0.3333,0.6667),作为下一个区间。输入“,B”,后更新频度，根据新的概率对区间,0.3333,0.6667),进行分割。这时输入的符号是“,C”,，可以选择子区间,0.5834,0.6667),。继续更新频度、分割区间、选择子区间，直到符号全部编码完成。最后得到的区间是,0.6390,0.6501),。输出属于这个区间的一个小数，例如,0.64,。那么经过算术编码的压缩，数据“,BCCB”,最后输出的编码就是,0.64,。,解码过程,算术编码进行解码时仅输入一个小数。解码前首先需要对区间,0,1),按照初始时的符号频度进行分割。然后观察输入的小数位于那个子区间。输出对应的符号，选择对应的子区间，然后从选择的子区间中继续进行下一轮的分割。不断的进行这个过程，直到所有的符号都解码出来。整个过程相当于编码时的逆运算。,在本例中，输入的小数是,0.64,。首先，初始时三个符号的概率都是,1/3,，按照这个概率分割区间。观察图可以发现,0.64,落在子区间,0.3333,0.6667),中，于是可以解码出“,B”,。并且选择子区间,0.3333,0.6667),作为下一个区间。输出“,B”,后更新频度，根据新的概率对区间,0.3333,0.6667),进行分割。这时,0.64,落在子区间,0.5834,0.6667),中，于是可以解码出“,C”,。按照上述过程进行，直到所有的符号都解码出来。可见，只需要一个小数就可以完整还原出原来的所有数据。,自适应算术编码程序,在固定模式算术编码程序的基础上作一下调整即可得到自适应模式算术编码程序：,1.,新建符号频度表，并在编码解码子函数中初始化各符号频度为,1,；将符号概率表各符号概率初始化为,0.1,。,2.,在编码解码过程中，实时更新频度表、概率表。,源码见附录。,程序验证,结果分析,1.,自适应算术编码根据符号的概率实时调整小数的位数。这使得算术编码平均码长比固定模式短，数据压缩率高，可以无限的接近数据的熵极限。信息熵越小符号串的算术编码平均码长越短。,2.,由于实时更新频度及概率，所以自适应算术编码解码速度慢。,附录：自适应算术编码程序,/*,自适应模式算术编码,*/,#include,#include,#include,double proc10;/0-9概率,int,cum10;/0-9频度,double,result,areaBegin,areaEnd,;,int,cord1000,cordLength;,char str1000;,int,strLength,=0;,/-,/,readdat,/-,bool,readdat,(),printf,(*,自适应模式算术编码,*n);,printf(请输入字符串(0-9):n);,scanf(%s,str,);,while(strstrLength,!=0),strLength,+;,for(int,i=0;i9|,stri,0)return 1;,return 0;,附录：自适应算术编码程序,/-,/,encord,/-,void,encord,(),double w=0.0,len;,areaBegin,=0.0,areaEnd=1.0;,for(int,h=0;h10;h+),proch,=0.1;/,初始化概率表,cumh,=1;/,初始化频度表,for(int,i=0;i,strLength;i,+),int,n=stri-0,k;w=0.0;,for(k,=0;k,n;k,+),w+=,prock,;/,计算所在区间,len,=,areaEnd-areaBegin,;,/,计算新的区间,areaEnd,=,areaBegin+len,*(,w+prock,);,areaBegin,+=,len,*w;,cumn,+;/,对应符号频度加一,for(k,=0;k10;k+)/,概率重新计算,prock,=(double)cumk/(i+11);,result=,areaBegin,*0.01+areaEnd*0.99;/,选择适当的点,cordLength,=(int(-log(areaEnd-areaBegin)/log(2)+1;,printf(编码位数,:%,dn,cordLength,);,printf(编码结果,:);,double temp1=result;,int,temp2;,附录：自适应算术编码程序,for(int,j=0;j,cordLength;j,+)/,十进制转换成二进制,temp1*=2;,temp2=int(temp1);,temp1-=temp2;,cordj,=temp2;,printf(%d,temp2);,printf(n,);,/-,/,decord,/-,void,decord,(),int,k;,for(int,h=0;h10;h+),proch,=0.1;/,初始化概率表,cumh,=1;/,初始化频度表,printf,(译 码 :n);,result=0.0;double,wei,=0.5;,for(int,i=0;i,cordLength;i+,wei,*=0.5)/,二进制转换成十进制,result+=,wei,*,cordi,;,printf(译码选取的数：%fn,result,);,areaBegin,=0.0,areaEnd=1.0;,wei,=0.0;,int,temp;double,len,;,附录：自适应算术编码程序,for(int,j=0;j,wei,*,len,),wei,+=,proctemp,+;/,搜索所在区间,temp-;,areaEnd,=,areaBegin+wei,*,len,;/,计算新的区间,areaBegin,=,areaBegin+(wei-proctemp,)*,len,;,printf(%d,temp,);,cumtemp,+;/,对应频度加一,for(k,=0;k10;k+)/,概率重新计算,prock,=(double)cumk/(j+11);,printf(n,);,/-,/main,/-,void main(),if(readdat,(),printf(字符输入错误!n,);,else,encord,();,decord,();,