算术编码是图像压缩的主要算法之一。 是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0 ≤ n < 1.0)的小数n(百度百科)(你伤害辽我，还一笑而过~)

算术编码的基本原理是：根据信源的不同符号序列的概率，把[0，1]区间划分为互不重叠的子区间，子区间的宽度恰好是各符号序列的概率。这样信源发出的不同符号序列将与各子区间一一对应，每个子区间内的任意一个实数都可以用来表示对应的符号序列，这个二进制小数就是该符号序列所对应的码字，截取其长度与该序列的概率匹配，实现高效编码。 接下来我们看具体的步骤： 编码 1.假设对一段二进制a1,a2符号序列信源进行编码，先统计出a1,a2出现的概率。 2.计算出该序列的概率p=p(x1)…p(x2),然后根据下面的公式计算出截止长度 L = ⌈ l o g 2 1 p ( S ) ⌉ L=\left \lceil log_{2}\frac{1}{p(S)} \right \rceil L=⌈log2​p(S)1​⌉其中方框表示向上取整。 3.从左到右根据信源符号来截取对应的区间，如第一个符号为a1，则截取0到1区间的a1段，第二个符号为a2，则在上一步的基础上截取其中的a2段，即在0到a1区间取a2段，以此类推直到序列的最后一个符号。 4.在3计算出的序列区间内任取一个数作为码字，截取其二进制的小数点后前L位，即得信源序列的算数编码。

解码 根据算术编码的原理我们可以倒推出解码得步骤： 1.将编码转回十进制小数（主要由于编码时截取的操作使得有截止误差的存在，所以这里转回十进制最好加上一个0.5*2^(-L+1)的补偿量） 2.判断该小数落在哪个区间，如其落在第一个大区间内则可判断源信源序列的第一个符号为a1，又落在第一个大区间内的第二个小区间，则信源序列的第二个符号为a2，以此逐渐细化区间得到全部信源序列信源。

这里结合一个例题进行详细步骤说明： 例：设二进制无记忆信源S={0,1}，其p(0)=1/4,p(1)=3/4。对二元序列11110做算术编码解码。 解： p ( S ) = p ( 1 ) 6 ∗ p ( 0 ) 2 = ( 3 4 ) 4 ∗ 1 4 p(S)=p(1)^{6}*p(0)^{2}=(\frac{3}{4})^{4}*\frac{1}{4} p(S)=p(1)6∗p(0)2=(43​)4∗41​ L = ⌈ l o g 2 1 p ( S ) ⌉ = 4 L=\left \lceil log_{2}\frac{1}{p(S)} \right \rceil=4 L=⌈log2​p(S)1​⌉=4

因为x1=1，所以首先落在[ 1 4 \frac{1}{4} 41​,1]区间，如图所示： x2=1，所以落在 l o w = 1 4 + ( 1 − 1 4 ) ∗ 1 4 = 7 16 low=\frac{1}{4}+(1-\frac{1}{4})*\frac{1}{4}=\frac{7}{16} low=41​+(1−41​)∗41​=167​,即[ 7 16 \frac{7}{16} 167​,1]区间，如图所示。 x3=1,所以落在 l o w = 7 16 + ( 1 − 7 16 ) ∗ 1 4 = 37 64 low=\frac{7}{16}+(1-\frac{7}{16})*\frac{1}{4}=\frac{37}{64} low=167​+(1−167​)∗41​=6437​,即[ 37 64 \frac{37}{64} 6437​,1]区间。

x4=1,所以落在 l o w = 37 64 + ( 1 − 37 64 ) ∗ 1 4 = 175 256 low=\frac{37}{64}+(1-\frac{37}{64})*\frac{1}{4}=\frac{175}{256} low=6437​+(1−6437​)∗41​=256175​,即[ 175 256 \frac{175}{256} 256175​,1]区间。

x5=0,所以落在 h i g h = 175 256 + ( 1 − 175 256 ) ∗ 1 4 = 781 1024 high=\frac{175}{256}+(1-\frac{175}{256})*\frac{1}{4}=\frac{781}{1024} high=256175​+(1−256175​)∗41​=1024781​,即[ 175 256 \frac{175}{256} 256175​, 781 1024 \frac{781}{1024} 1024781​]区间。 0.5 ∗ ( 175 256 + 781 1024 ) 0.5*(\frac{175}{256}+\frac{781}{1024}) 0.5∗(256175​+1024781​)=0.7231445=0.10111… 取小数点后前4位得算术编码结果为1011。

解码： p ( S ) = 1 ∗ 2 − 1 + 0 ∗ 2 − 2 + 1 ∗ 2 − 3 + 1 ∗ 2 − 4 + 0.5 ∗ 2 − 5 = 0.701325 p(S)=1*2^{-1}+0*2^{-2}+1*2^{-3}+1*2^{-4}+0.5*2^{-5}=0.701325 p(S)=1∗2−1+0∗2−2+1∗2−3+1∗2−4+0.5∗2−5=0.701325(最后一项为了补偿截止误差) 因为p(S)>1/4=0.25, 即在[0.25,1]，所以第一个符号为1，此时low=0.25,high=1.

又p(S)>low+(high-low)*0.25=0.4375, 即在[0.4375,1]区间,所以第二个符号为1,low=0.4375,high=1.

又p(S)>low+(high-low)*0.25=0.578125, 即在[0.578125,1]区间,所以第三个符号为1,low=0.578125,high=1.

又p(S)>low+(high-low)*0.25=0.68359375, 即在[0.68359375,1]区间,所以第四个符号为1,low=0.68359375,high=1.

又p(S) printf("打开文件错误\n"); exit(0); } for(i=0;i if(source[j]=='0') ps = ps*p; else ps = ps*(1-p); } PS = log(1.0/ps)/log(2); N = (int)PS; if(PS-N>1e-6) N = N+1; // printf("N的值:%d\n",N); //算出区间的两端端点值 low=0; high=1; for(j=0;j temp = (int)(m*2); if(temp) code[len]='1'; else code[len]='0'; fputc(code[len],file); len=len+1; m = 2*m-temp; if(len==N) break; } fputc(10,file); /* printf("\n编码结果为:"); for(j=0;j printf("打开文件错误\n"); exit(0); } for(i=0;i if(code[f]==10) //获取第一行长度 10为换行符 asc码 break; } len=f; //printf("len:%d\n",len); //将编码转回十进制小数 P=0; for(j=0;j if((P>low)&(P decode[j]='1'; low = (high-low)*p+low; } fputc(decode[j],file); } fputc(10,file); /* printf("解码结果为:"); for(j=0;j printf("输入概率p:"); scanf("%f",&p); printf("输入长度L："); scanf("%d",&L); printf("输入分组数n："); scanf("%d",&n); if (L%n>1e-6|p>=1|p printf("打开文件错误\n"); exit(0); } //生成伯努利源 for(i=0;i k = rand()%100; if(k>100*p-1){ source[j]='1'; } else { source[j]='0'; } fputc(source[j],file); } fputc(10,file); } fclose(file); //编码 codes(p,L,n); //解码 decodes(p,L,n); return 0; }

参考资料:信息论与编码（曹雪虹著）

第一次认认真真写博客，有很多不足欢迎评论指正，另外还请多多点赞支持啊啊啊！