自适应算术编码

1、自适应算术编码,王杰 201011110640 研11班,自适应算术编码,统计编码技术需要利用信源符号的概率，获得这个概率的过程称为建模。不同准确度（通常也是不同复杂度）的模型会影响算术编码的效率。 建模的方式： 静态建模：在编码过程中信源符号的概率不变（固定模式算术编码）。但一般来说事先知道精确的信源概率是很难的，而且是不切实际的。 自适应动态建模：信源符号的概率根据编码时符号出现的频繁程度动态地进行修改（自适应算术编码）。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。 算术编码很容易与自适应建模相结合。,自适应算术编码,自适应算术编码：

2、 在编码之前，假设每个信源符号的频率相等（如都等于1），并计算累积频率 从输入流中读入一个字符，并对该符号进行算术编码 更新该符号的频率，并更新累积频率 由于在解码之前，解码器不知道是哪个信源符号，所以概率更新应该在解码之后进行 对应的，编码器也应在编码后进行概率更新,自适应算术编码,下面是一个自适应算术编码和译码的例子： 设某信源可能发出三种符号a，b，c，对符号序列bccb进行自适应算术编码： 初始时刻，我们对a，b，c，三者出现的概率一无所知（即采用自适应模型），认为三者出现的概率相等，暂时都为1/3，频率都为1，则累积频率为3。将区间0,1)按概率分布划分给三个字符，如下图所示：,自适

3、应算术编码,向编码器输入第一个字符b，落入区间0.3333,0.6667)。此时b的频率增加了1变为2，累积频率也增加了1变为4；概率分布更新为： 再输入字符c，落入区间0.5834,0.6667)。此时c的频率增加了1变为2，累积频率也增加了1变为5；概率分布更新为：,自适应算术编码,接着输入第三个字符c，落入区间0.6334,0.6667)。此时c的频率又增加了1变为3，累积频率也又增加了1变为6；概率分布更新为： 最后输入字符b，锁定区间0.6390,0.6501)，然后在这个区间内任意选择一个实数，例如0.64，再将其转化为二进制数l位（连续乘以2取整）。 即输出8位。最后的编码结果为

4、：11011011。,自适应算术编码,译码过程和编码过程类似： 设信源符号a，b，c的原概率皆为1/3。 1、11011011B=0.64D，落入区间0.3333,0.6667)，所以译码器译为b，概率分布更新为：,自适应算术编码,2、0.64落入区间0.5834,0.6667)，译为c，概率分布更新为： 3、 0.64落入区间0.6334,0.6667)，译为c，概率分布更新为： 4、0.64落入区间0.6501,0.6667)，译为b。 如果有停止位或者定长，则译码结束，译出的原序列为：bccb。,自适应算术编码,实验结果及分析 下面的图是固定模式和自适应模式算术编码和译码程序的运行结果，

5、验证的数据是20080808，20080000，20000000。,自适应算术编码,自适应算术编码,结果分析： 1、固定模式算术编码的编码长度L(20080808)P(20080000)P(20000000)(离散无记忆信源)，由于算术编码符合概率匹配原则：出现概率较大的符号取较短的码字，而对出现概率较小的符号取较长的码字，这就是出现这种运行结果的原因。 2、自适应模式算术编码的编码长度L(20080808)L(20080000)L(20000000)，说明信源符号序列中相同的符号越多，所取的码字长度越短。原因：由于信源符号出现的概率是随着符号的输入而不断变化的，当输入的相同的符号数,自适应算

6、术编码,越多时，那么该符号的概率将被更新的越大，比如向编码器或者译码器输入20080808（符号09的初始概率都相同为0.1），此时由于输入的0的数目大于其他19的数目，这样0出现的概率就变得最大，其次是8，再次为2，即信源符号序列20080808全部输入编码器或者译码器后，各符号的概率被更新，大小为：P(0)P(8)P(2)P(1/3/7/9)，然而在固定模式中，各信源符号的概率是固定不变的，因此这样就使得符号序列20080808出现的概率，就会大于固定模式中该序列的概率，由于算术编码符合概率匹配原则：出现概率较大的符号取较短的码字，而对出现概率较小的符号取较长的码字，因此对这个序列的编码，

7、自适应模式比固定模式的码字短，符号序列20080000和20000000同理。,自适应算术编码,3、与2同理，信源符号序列20080000中0的数目大于20080808，而20000000中0的数目又大于20080000，在自适应模式中，他们的概率大小将变为： P(20080808)P(20080000)P(20000000)(离散无记忆信源) ，由于算术编码符合概率匹配原则：出现概率较大的符号取较短的码字，而对出现概率较小的符号取较长的码字，因此自适应算术编码后，他们的码长大小为： L(20080808)L(20080000)L(20000000)。 然而当对序号序列12345678分别进行固定模式和自适应模式算术编码后，所得码长前者为26，后者为30，如下页图。因此自适应算术编码适合用在相同符号数较多的场合。,自适应算术编码,总结,直接对序列进行编码（不是码字的串联）：非