Arithmetic-coding.md

算数编码

算数编码是一种熵编码

编码示例

• 开始编码原始区间

  示例字符：AABABCABAB
  ----------
  字符 = 概率数区间
  A   = 0.5 [0, 0.5]
  B   = 0.4 [0.5 0.9]
  C   = 0.1 [0.9, 1]
  

1. 第一个字母 A 根据 A 区间开始编码 A:[0-0.5]

   A   =   [0, 0.25] 
   B   =   [0.25, 0.45]
   C   =   [0.45, 0.5]
   

2. 第二个字母 A 根据 A 区间开始编码 A:[0-0.25]

   A [0, 0.125]
   B:[0.125, 0.225]
   C:[0.225, 0.25]
   

3. 第三个字母 B 根据 B 区间开始编码 B:[0.125-0.225]

   A:[0.125, 0.175]
   B:[0.175, 0.215]
   C:[0.215, 0.225]
   

4. 所有字母编码后汇总

   当前字符   =   当前目标区间
   A       =   [0, 0.5]
   A       =   [0, 0.25]
   B       =   [0.125, 0.225]
   A       =   [0.125, 0.175]
   B       =   [0.15, 0.17]
   C       =   [0.168, 0.17]
   A       =   [0.168, 0.169]
   B       =   [0.1685, 0.1689]
   A       =   [0.1685, 0.1687]
   B       =   [0.1686, 0.16868]
   

• 至此 最后的区间[0.1686, 0.16868]已经是最终的编码结果

解码示例

1. [0.1686, 0.16868]在原始区间[0, 0.5] 第一个字母为 A
2. [0.1686, 0.16868]在原始区间[0, 0.25] 第二个字母仍然为A
3. [0.1686, 0.16868]在原始区间[0.125, 0.225] 第二个字母为B
4. [0.1686, 0.16868]在原始区间[0.125, 0.175] 第二个字母为A

....依次处理

解码方必须知道 1.概率分布 2. 流的长度; 不知道1就无法划分区间；不知道2就无法在正确的位置停下来，很有可能一直分下去结果解出来的码超过明文长度

重新归一化

让我们指出与编码程序相关的几个相当明显的考虑因素。 显然，如果当前区间完全包含在 0 和 ½ 之间，编码结果的当前比特将是零。 同样，如果当前区间完全包含在 ½ 和 1 之间，编码结果的当前比特将有一个值 1。 然而，如果当前区间的左端点小于 ½，右端点大于 ½，但两者与 ½ 的差异不超过 ¼，当前结果比特将是未知的。 另一方面，可以肯定的是，下一个结果比特将与当前比特的值相反。 当我们为这次迭代获得每个当前结果比特后，我们可以将区间长度加倍。 所有这些都使得引入一种克服算术编码上述缺点的当前区间长度加倍程序成为可能。

这个程序在标准中被称为重新归一化。 通过重新归一化，编码结果比特在编码过程中立即输出（在完成之前），并且当前区间长度加倍。 每次选择新的当前区间时，都会迭代执行重新归一化。 迭代继续进行，直到当前区间完全包含在以下三个区间之一：[0, 0.5), [0.25, 0.75), [0.5, 1)

上下文二进制算术编码