实验三算术编码
一、实验目的
1．进一步学习C++语言概念和熟悉VC 编程环境。
2．学习算术编码基本流程, 学会调试算术编码程序。
3. 根据给出资料，自学自适应0 阶算术编、解码方法。
二、实验内容与原理
（一）实验原理：
1．算术编码基本原理
这是将编码消息表示成实数0 和1 之间的一个间隔，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。首先借助下面一个简单的例子来阐释算术编码的基本原理。考虑某条信息中可能出现的字符仅有a b c 三种，我们要压缩保存的信息为bccb。在没有开始压缩进程之前，假设对a b c 三者在信息中的出现概率一无所知（采用的是自适应模型），暂认为三者的出现概率相等各为1/3，将0 - 1 区间按照概率的比例分配给三个字符，即a 从0.0000 到0.3333，b 从0.3333 到0.6667，c 从0.6667 到1.0000。进行第一个字符b编码，b 对应的区间0.3333 -0.6667。这时由于多了字符b，三个字符的概率分布变成：Pa = 1/4，Pb = 2/4，Pc = 1/4。按照新的概率分布比例划分0.3333 - 0.6667 这一区间，划分的结果可以用图形表示为：+-- 0.6667 Pc = 1/4 | +-- 0.5834 | | Pb = 2/4 | | | +-- 0.4167 Pa = 1/4 | +-- 0.3333 接着拿到字符c，现在要关注上一步中得到的c 的区间0.5834 -0.6667。新添了c 以后，三个字符的概率分布变成Pa = 1/5，Pb = 2/5，Pc = 2/5。用这个概率分布划分区间0.5834 - 0.6667：+-- 0.6667 | Pc = 2/5 | +-- 0.6334 | Pb = 2/5 || +-- 0.6001 Pa = 1/5 | +-- 0.5834 输入下一个字符c，三个字符的概率分布为：Pa = 1/6，Pb = 2/6，Pc = 3/6。接着来划分c 的区间0.6334 - 0.6667：+-- 0.6667 | | Pc = 3/6 | | +-- 0.6501 | Pb = 2/6 | | +-- 0.6390 Pa = 1/6 | +-- 0.6334 输入最后一个字符b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的b 的区间为0.6390 -0.6501，最后在这个区间内随便选择一个容易变成二进制的数，例如0.64，将它变成二进制0.1010001111，去掉前面没有太多意义的0 和小数点，可以输出1010001111，这就是信息被压缩后的结果，由此完成了一次最简单的算术压缩过程。如何解压缩呢？那就更简单了。解压缩之前仍然假定三个字符的概率相等。解压缩时面对的是二进制流1010001111，先在前面加上0 和小数点把它变成小数0.1010001111，也就是十进制0.64。这时我们发现0.64 在分布图中落入字符b 的区间内，立即输出字符b，并得出三个字符新的概率分布。类似压缩时采用的方法，我们按照新的概率分布划分字符b 的区间。在新的划分中，我们发现0.64 落入了字符c 的区间，我们可以输出字符c。同理，我们可以继续输出所有的字符，完成全部解压缩过程。
2．小数存储方法
如果信息内容特别丰富，我们要输出的小数将会很长很长，该如何在内存中表示如此长的小数呢？其实，没有任何必要在内存中存储要输出的整个小数。从上面的例子可以知道，在编码的进行中，会不断地得到有关要输出小数的各种信息。具体地讲，当我们将区间限定在0.6390 -0.6501 之间时，我们已经知道要输出的小数第一位（十进制）一定是6，那么我们完全可以将6 从内存中拿掉，接着在区间0.390 - 0.501 之间继续我们的压缩进程。内存中始终不会有非常长的小数存在。使用二进制时也是一样的，我们会随着压缩的进行不断决定下一个要输出的二进制位是0 还是1，然后输出该位并减小内存中小数的长度，具体可以参考E1/E2/E3 放大原理，及它们之间关系的描述。
3．静态模型与自适应模型
（1）静态模型上面的简单例子采用的是自适应模型，那么如何实现静态模型呢？其实很简单。对信息bccb 我们统计出其中只有两个字符，概率分布为Pb = 0.5，Pc = 0.5。在压缩过程中不必再
更新此概率分布，每次对区间的划分都依照此分布即可，对上例也就是每次都平分区间。这样，压缩过程可以简单表示为：输出区间的下限输出区间的上限压缩前0.0 1.0 输入b 0.0 0.5 输入c 0.25 0.5 输入c 0.375 0.5 输入b 0.375 0.4375 最后的输出区间在0.375 - 0.4375 之间，甚至连一个十进制位都没有确定，也就是说，整个信息根本用不了一个十进制位。
（2）自适应模型既然使用静态模型可以很好地接近熵值，为什么还要采用自适应模型呢？要知道，静态模型无法适应信息多样性，例如，上面得出的概率分布没法在所有待压缩信息上使用，为了能正确解压缩，我们必须再消耗一定的空间保存静态模型统计出的概率分布，保存模型所用的空间将使我们重新远离熵值。其次，静态模型需要在压缩前对信息内字符的分布进行统计，这一统计过程将消耗大量的时间，使得本来就比较慢的算术编码压缩更加缓慢。另外还有最重要的一点，对较长的信息，静态模型统计出的符号概率是该符号在整个信息中的出现概率，而自适应模型可以统计出某个符号在某一局部的出现概率或某个符号相对于某一上下文的出现概率，换句话说，自适应模型得到的概率分布将有利于对信息的压缩（可以说结合上下文的自适应模型的信息熵建立在更高的概率层次上，其总熵值更小），好的基于上下文的自适应模型得到的压缩结果将远远超过静态模型。
（3）自适应模型的阶通常用“阶”(order)这一术语区分不同的自适应模型。前面例子中采用的是0 阶自适应模型，该例子中统计的是符号在已输入信息中的出现概率，没有考虑任何上下文信息。如果我将模型变成统计符号在某个特定符号后的出现概率，那么，模型就成为了1 阶上下文自适应模型。举个例子要对一篇英文文本进行编码，已经编码了10000 个英文字符，刚刚编码的字符是t，下一个要编码的字符是h。我们在前面的编码过程中已经统计出前10000 个字符中出现了113 次字母t，其中有47 个t 后面跟着字母h。我们得出字符h 在字符t 后的出现频率是47/113，我们使用这一频率对字符h 进行编码，需要-log2(47/113) = 1.266 bit。对比0 阶自适应模型，如果前10000 个字符中h 的出现次数为82 次，则字符h 的概率是82/10000，我们用此概率对h 进行编码，需要-log2(82/10000) = 6.930 bit。考虑上下文因素的优势显而易见。还可以进一步扩大这一优势，例如要编码字符h 的前两个字符是gt，而在已经编码的文本中gt 后面出现h 的概率是80%，那么我们只需要0.322 bit就可以编码输出字符h。此时，使用的模型叫做2 阶上下文自适应模型。最理想的情况是采用3 阶自适应模型。此时，如果结合算术编码，对信息的压缩效果将达到惊人的程度。采用更高阶的模型需要消耗的系统空间和时间至少在目前还无法让人接受，使用算术压缩的应用程序大多数采用2 阶或3 阶的自适应模型。
（二）实验内容
1．复习C++代码基本语法（类和虚函数等面向对象数据结构定义）
2．根据实验提供的源代码，学习算术编码实现流程，培养实际动手调试能力和
相应的编程技巧。
三、实验仪器、设备
1．计算机－系统最低配置256M 内存、P4 CPU。
2．C++ 编程软件－Visual C++ 7.0 （Microsoft Visual Studio 2003）
Visual C++ 8.0 （Microsoft Visual Studio 2005）
四、实验步骤
项目文件建立步骤同实验二，下面列出对给定序列的算术编码步骤：
步骤1：编码器在开始时将“当前间隔”[ L，H) 设置为[0，1)。
步骤2：对每一事件，编码器按步骤（a）和（b）进行处理
（a）编码器将“当前间隔”分为子间隔，每一个事件一个。
（b）一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件相对应，并使它成为新的“当前间隔”。
步骤3：最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。
六、实验结论：
