基于Python的算术编码的设计与实现

基于Python的算数编码实验

一、实验目的

• 给出算术编码实现的详细原理。

• 编制编解码程序

• 设计并实现自适应算术编码（选做）

二、实验环境

硬件环境：windows 10; VScode

编程语言：python3.7

三、实验原理

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

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

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

编码过程：

• 编码器在开始时将“当前间隔” [ L， H) 设置为[0，1)。

• 对每一事件，编码器按步骤（a）和（b）进行处理

• 编码器将“当前间隔”分为子间隔，每一个事件一个。

• 个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件相对应，并使它成为新的“当前间隔”。

• 最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。

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

四、实验过程与结果

程序演示截图：