自适应算术编码

自适应算术编码王杰201011110640研11班自适应算术编码统计编码技术需要利用信源符号的概率，获得这个概率的过程称为建模。不同准确度（通常也是不同复杂度）的模型会影响算术编码的效率。建模的方式：•静态建模：在编码过程中信源符号的概率不变（固定模式算术编码）。但一般来说事先知道精确的信源概率是很难的，而且是不切实际的。•自适应动态建模：信源符号的概率根据编码时符号出现的频繁程度动态地进行修改（自适应算术编码）。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。算术编码很容易与自适应建模相结合。自适应算术编码自适应算术编码：•在编码之前，假设每个信源符号的频率相等（如都等于1），并计算累积频率•从输入流中读入一个字符，并对该符号进行算术编码•更新该符号的频率，并更新累积频率•由于在解码之前，解码器不知道是哪个信源符号，所以概率更新应该在解码之后进行•对应的，编码器也应在编码后进行概率更新自适应算术编码下面是一个自适应算术编码和译码的例子：设某信源可能发出三种符号a，b，c，对符号序列bccb进行自适应算术编码：初始时刻，我们对a，b，c，三者出现的概率一无所知（即采用自适应模型），认为三者出现的概率相等，暂时都为1/3，频率都为1，则累积频率为3。将区间[0,1)按概率分布划分给三个字符，如下图所示：自适应算术编码向编码器输入第一个字符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位。最后的编码结果为：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。自适应算术编码实验结果及分析下面的图是固定模式和自适应模式算术编码和译码程序的运行结果，验证的数据是20080808，20080000，20000000。自适应算术编码自适应算术编码结果分析：1、固定模式算术编码的编码长度L(20080808)L(20080000)L(20000000)，这是因为0~9中符号8出现的概率最大为0.15，2和0出现的概率都为0.1，因此符号序列出现的概率P(20080808)P(20080000)P(20000000)(离散无记忆信源)，由于算术编码符合概率匹配原则：出现概率较大的符号取较短的码字，而对出现概率较小的符号取较长的码字，这就是出现这种运行结果的原因。2、自适应模式算术编码的编码长度L(20080808)L(20080000)L(20000000)，说明信源符号序列中相同的符号越多，所取的码字长度越短。原因：由于信源符号出现的概率是随着符号的输入而不断变化的，当输入的相同的符号数自适应算术编码越多时，那么该符号的概率将被更新的越大，比如向编码器或者译码器输入20080808（符号0~9的初始概率都相同为0.1），此时由于输入的0的数目大于其他1~9的数目，这样0出现的概率就变得最大，其次是8，再次为2，即信源符号序列20080808全部输入编码器或者译码器后，各符号的概率被更新，大小为：P(0)P(8)P(2)P(1/3/…/7/9)，然而在固定模式中，各信源符号的概率是固定不变的，因此这样就使得符号序列20080808出现的概率，就会大于固定模式中该序列的概率，由于算术编码符合概率匹配原则：出现概率较大的符号取较短的码字，而对出现概率较小的符号取较长的码字，因此对这个序列的编码，自适应模式比固定模式的码字短，符号序列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，如下页图。因此自适应算术编码适合用在相同符号数较多的场合。自适应算术编码总结直接对序列进行编码（不是码字的串联）：非分组码可证明是唯一可译码渐近接近熵界对不均衡的分布，比Huffman更有效只产生必要的码字但是实现更复杂允许将建模和编码分开，容易与自适应模型和上下文模型结合对错误很敏感，如果有一位发生错误就会导致整个消息译码错误