基于Python的算数编码实验

一、实验目的

给出算术编码实现的详细原理。
编制编解码程序
设计并实现自适应算术编码（选做）

二、实验环境

硬件环境：windows 10; VScode

编程语言：python3.7

三、实验原理

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

算术编码的基本原理：根据信源可能发现的不同符号序列的概率，把[0，1]区间划分为互不重叠的子区间，子区间的宽度恰好是各符号序列的概率。这样信源发出的不同符号序列将与各子区间一一对应，因此每个子区间内的任意一个实数都可以用来表示对应的符号序列，这个数就是该符号序列所对应的码字。显然，一串符号序列发生的概率越大，对应的子区间就越宽，要表达它所用的比特数就减少，因而相应的码字就越短。

在给定符号集和符号概率的情况下,算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计,然后再编码。这个估计越准,编码结果就越接近最优的结果。

编码过程：

编码器在开始时将“当前间隔” [ L， H) 设置为[0，1)。
对每一事件，编码器按步骤（a）和（b）进行处理
编码器将“当前间隔”分为子间隔，每一个事件一个。
个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件相对应，并使它成为新的“当前间隔”。
最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。

解码过程：解码前首先需要对区间[0,1)按照初始时的符号频度进行分割。然后观察输入的小数位于那个子区间。输出对应的符号，选择对应的子区间，然后从选择的子区间中继续进行下一轮的分割。不断的进行这个过程，直到所有的符号都解码出来。

四、实验过程与结果

程序演示截图：

五、实验心得

实践中加深了对算术编码的理解

进一步提升了编程能力

算术编码是一种到目前为止编码效率最高的统计熵编码方法,它比著名的Huffman编码效率提高10％左右,但由于其编码复杂性和实现技术的限制以及一些专利权的限制,所以并不象Huffman编码那样应用广泛。算术编码有两点优于Huffman码： ①它的符号表示更紧凑； ②它的编码和符号的统计模型是分离的，可以和任何一种概率模型协同工作。后者非常重要, 因为只要提高模型的性能就可以提高编码效率。