算术编码

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

算术编码工作原理

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

例: 对一个简单的信号源进行观察，得到的统计模型如下：

60%的机会出现符号中性
20%的机会出现符号阳性
10%的机会出现符号阴性
10%的机会出现符号数据结束符. (出现这个符号的意思是该信号源'内部中止'，在进行数据压缩时这样的情况是很常见的。当第一次也是唯一的一次看到这个符号时，解码器就知道整个信号流都被解码完成了)。

算术编码可以处理的例子不止是这种只有四种符号的情况，更复杂的情况也可以处理，包括高阶的情况。所谓高阶的情况是指当前符号出现的概率受之前出现符号的影响，这时候之前出现的符号，也被称为上下文。比如在英文文档编码的时候，例如，在字母Q或者q出现之后，字母u出现的概率就大大提高了。这种模型还可以进行自适应的变化，即在某种上下文下出现的概率分布的估计随着每次这种上下文出现时的符号而自适应更新，从而更加符合实际的概率分布。不管编码器使用怎样的模型，解码器也必须使用同样的模型。

一个简单的例子以下用一个符号序列怎样被编码来作一个例子：假如有一个以A、B、C三个出现机会均等的符号组成的序列。若以简单的分组编码会十分浪费地用2 bits来表示一个符号：其中一个符号是可以不用传的（下面可以见到符号B正是如此）。为此，这个序列可以三进制的0和2之间的有理数表示，而且每位数表示一个符号。例如，“ABBCAB”这个序列可以变成0.011201（base3，即0为A, 1为B, 2为C）。用一个定点二进制数字去对这个数编码使之在恢复符号表示时有足够的精度，譬如0.001011001(base2) –只用了9个bit，比起简单的分组编码少（1 – 9/12）x100% = 25%。这对于长序列是可行的因为有高效的、适当的算法去精确地转换任意进制的数字。

编码过程的每一步，除了最后一步，都是相同的。编码器通常需要考虑下面三种数据：

下一个要编码的符号
当前的区间（在编第一个符号之前，这个区间是[0,1）,但是之后每次编码区间都会变化)
模型中在这一步可能出现的各个符号的概率分布（像前面提到的一样，高阶或者自适应的模型中，每一步的概率并不必须一样）

编码器将当前的区间分成若干子区间，每个子区间的长度与当前上下文下可能出现的对应符号的概率成正比。当前要编码的符号对应的子区间成为在下一步编码中的初始区间。

例:对于前面提出的4符号模型：

中性对应的区间是[0, 0.6)
阳性对应的区间是[0.6, 0.8)
阴性对应的区间是[0.8, 0.9)
数据结束符对应的区间是[0.9, 1)

当所有的符号都编码完毕，最终得到的结果区间即唯一的确定了已编码的符号序列。任何人使用该区间和使用的模型参数即可以解码重建得到该符号序列。

实际上我们并不需要传输最后的结果区间，实际上，我们只需要传输该区间中的一个小数即可。在实用中，只要传输足够的该小数足够的位数（不论几进制），以保证以这些位数开头的所有小数都位于结果区间就可以了。

例:下面对使用前面提到的4符号模型进行编码的一段资讯进行解码。编码的结果是0.538（为了容易理解，这里使用十进制而不是二进制；我们也假设我们得到的结果的位数恰好够我们解码。下面会讨论这两个问题）。

像编码器所作的那样我们从区间[0,1)开始，使用相同的模型，我们将它分成编码器所必需的四个子区间。分数0.538落在NEUTRAL坐在的子区间[0,0.6)；这向我们提示编码器所读的第一个符号必然是NEUTRAL，这样我们就可以将它作为消息的第一个符号记下来。

然后我们将区间[0,0.6)分成子区间：

中性的区间是[0, 0.36) -- [0, 0.6)的60%
阳性的区间是[0.36, 0.48) -- [0, 0.6)的20%
阴性的区间是[0.48, 0.54) -- [0, 0.6)的10%
数据结束符的区间是[0.54, 0.6). -- [0, 0.6)的10%

我们的分数.538在[0.48, 0.54)区间；所以消息的第二个符号一定是NEGATIVE。

我们再一次将当前区间划分成子区间：

中性的区间是[0.48, 0.516)
阳性的区间是[0.516, 0.528)
阴性的区间是[0.528, 0.534)
数据结束符的区间是[0.534, 0.540).

我们的分数.538落在符号END-OF-DATA的区间；所以，这一定是下一个符号。由于它也是内部的结束符号，这也就意味着编码已经结束。（如果数据流没有内部结束，我们需要从其它的途径知道数据流在何处结束——否则我们将永远将解码进行下去，错误地将不属于实际编码生成的数据读进来。）

效率低下的来源

前一个例子中的消息0.538可能已经由同样短的分数 0.534, 0.535, 0.536, 0.537, 0.539 编码。这表明使用十进制而不是二进制引入了一些低效率。这是对的;三位十进制的资讯内容是 $3*\log _{2}(10)\approx 9.966$ 个位元;相同的消息可以在二进制分数 0.10001010 （相当于 0.5390625 十进制）中编码，仅花费 8 个位元。（最后的零必须在二进制小数中指定，否则消息将是不明确的，没有外部资讯，如压缩流大小。）

该 8 位元输出大于资讯内容或消息的熵，也就是：

\sum -\log _{2}(p_{i})=-\log _{2}(0.6)-\log _{2}(0.1)-\log _{2}(0.1)=7.381{\text{ bits}}

但是在二进制编码中必须使用整数码，因此该消息的编码器将使用至少8位，从而产生比熵内容大 8.4％的消息。随着消息大小的增加，这种至多 1 位的低效率导致相对较少的开销。

此外，要求保护的符号概率为 [0.6, 0.2, 0.1, 0.1) ，但本例中的实际频率为 [0.33, 0, 0.33, 0.33) 。如果为这些频率重新调整间隔，则消息的熵将是 4.755 位元，并且相同的中性负数据结束消息可以被编码为间隔 [0, 1/3) ; [1/9, 2/9) ; [5/27, 6/27) ; 和二进制间隔 [0.00101111011, 0.00111000111) 。这也是算术编码等统计编码方法如何产生大于输入消息的输出消息的示例，尤其是在概率模型关闭的情况下。

编码

若dataX有M个可能的值 $(X[i]=1,2,...orM)$ ,使用k进位的编码，且

  $P_{n}$ :the probability of x = n(from prediction)

  $S_{0}=0,S_{n}=\sum _{j=1}^{n}P_{j}$ 

現在要對dataX做編碼，假設length(X) = N

算术编码的运算方式

initiation: lower =  $S_{X[1]-1}$   upper =  $S_{X[1]}$ 

for i=2:N

     lower =  $S_{X[i]-1}\times (upper-lower)$ 

     upper =  $S_{X[i]}\times (upper-lower$ )

end

假设 lower $\leq C\cdot k^{-b}<(C+1)\cdot k^{-b}\leq upper$
且C和b为整数(b越小越理想)，则dataX可以被编码成 $C_{(k,b)}$
且 $C_{(k,b)}$
为k进为何b bits来表示C
ex = 01110
ans = b=5,C=14

示例

1.假设要对X来做二进制(k=2)的编码且经由事先的估计，X[i] = a 的几率为0.8,X[i] = b 的几率为0.2
$\Rightarrow P_{1}=0.8,P_{2}=0.2,S_{0}=0,S_{1}=0.8,S_{2}=1$
若实际上输入的资料为X = a a a b a a initial (X[1] = a): lower = 0, upper = 0.8
When i=2, (X[2] = a): lower = 0, upper = 0.64
When i=3, (X[3] = a): lower = 0, upper = 0.512
When i=4, (X[4] = b): lower = 0.4096, upper = 0.512
When i=5, (X[5] = a): lower = 0.4096, upper = 0.49152
When i=6, (X[6] = a): lower = 0.4096, upper = 0.475136
由于 lower = 0.4096, upper = 0.475136
lower $\leq 14\cdot 2^{-5}<15\cdot 2^{-5}\leq$ upper
所以编码结果为 $14_{(2,5)}=01110$ ,2进位,5bits

解码

假设编码的结果为Y,length(Y) = b,其他的假设和编码相同(k进位)

算术解码的运算方式

initiation: lower = 0, upper = 1, lower1 = 1, upper1 = 1

for i=1:N

     check = 1;
     while check =1
       if there exists an n such that 
           $lower+(upper-lower)S_{n-1}\leq lower1$  and 

           $lower+(upper-lower)S_{n}\leq upper1$  are both satisfied,

          then check = 0;
       else
           $upper1=lower1+(Y[j]+1)k^{-j}$ 

           $lower1=lower1+(Y[j])k^{-j}$ 

          j = j+1
       end
       X(i) = n;
        $lower=lower+(upper-lower)S_{n-1}$ 

        $upper=lower+(upper-lower)S_{n}$ 

end

资料长度

假设 $P_{n}$ 是预测的X[i] = n的几率, $Q_{n}$ 是实际上的X[i] = n的几率
也就是说,若length(X) = N,当中会有 $Q_{n}$ N个elements等于n 则 $upper-lower=\prod _{m=1}^{M}P_{m}^{Q_{m}N}$
另一方面，由于编码的假设
$k^{-b}\leq upper-lower<(2k)k^{-b}$
$-log_{k}(upper-lower)\leq b<-log_{k}(upper-lower)+1+log_{k}2$
$ceil(-N\sum _{m=1}^{M}Q_{m}log_{k}P_{m})\leq b\leq floor(-N\sum _{m=1}^{M}Q_{m}log_{k}P_{m}+log2)+1$
在几率的预测完全准确的情况下, $Q_{m}=P_{m}$
Totoal coding length b 的范围是
$ceil(-N\sum _{m=1}^{M}P_{m}log_{k}P_{m})\leq b\leq floor(-N\sum _{m=1}^{M}P_{m}log_{k}P_{m}+log2)+1$
$\Rightarrow ceil(-N{\frac {entropy}{logk}})\leq b\leq floor(-N{\frac {entropy}{logk}}+log2)+1$
算术编码的总资料长度的上限比霍夫曼编码更低

自适应算术编码

与其他类似的数据压缩方法相比，算术编码的一个优点是适应的便利性。适应是在处理数据时改变频率（或概率）表。只要解码中的频率表以与编码相同的方式和相同的步骤被替换，解码的数据就匹配原始数据。通常，同步基于在编码和解码过程期间出现的符号的组合。

精度和再正规化

上面对算术编码的解释进行了一些简化。尤其是，这种写法看起来好像算术编码首先使用无限精度精度的数值计算总体上表示最后节点的分数，然后在编码结束的时候将这个分数转换成最终的形式。许多算术编码器使用有限精度的数值计算，而不是尽量去模拟无限精度，因为它们知道解码器能够匹配、并且将所计算的分数在那个精度四舍五入到对应值。一个例子能够说明一个模型要将间隔[0,1]分成三份并且使用8位的精度来实现。注意既然精度已经知道，我们能用的二进制数值的范围也已经知道。

符号	概率（使用分数表示）	减到8位精度的间隔（用分数表示）	减到8位精度的间隔（用二进制表示）	二进制范围
A	1/3	[0, 85/256)	[0.00000000, 0.01010101)	00000000 – 01010100
B	1/3	[85/256, 171/256)	[0.01010101, 0.10101011)	01010101 – 10101010
C	1/3	[171/256, 1)	[0.10101011, 1.00000000)	10101011 – 11111111

一个称为再归一化的过程使有限精度不再是能够编码的字符数目的限制。当范围减小到范围内的所有数值共享特定的数字时，那些数字就送到输出数据中。尽管电脑能够处理许多位数的精度，编码所用位数少于它们的精度，这样现存的数据进行左移，在右面添加新的数据位以尽量扩展能用的数据范围。注意这样的结果出现在前面三个例子中的两个里面。

符号	概率	范围	能够输出的数据位	再归一化后的范围
A	1/3	00000000 – 01010100	0	00000000 – 10101001
B	1/3	01010101 – 10101010	None	01010101 – 10101010
C	1/3	10101011 – 11111111	1	01010110 – 11111111

算术编码和其他压缩方法的关系

霍夫曼编码

算术编码和哈夫曼编码的相似程度很高——事实上，哈夫曼编码只是算术编码的一个特例。但是，算术编码将整个消息翻译成一个表示为基数 b，而不是将消息中的每个符号翻译成一系列的以 b 为基数的数字，因此通常比哈夫曼编码更能达到最优熵编码。

因为算术编码不能一次压缩一个数据，所以在压缩iid字符串时它可以任意接近熵。相反，使用霍夫曼编码（到字符串）的扩展不会达到熵，除非字母符号的所有概率都是 2 的幂，在这种情况下，霍夫曼和算术编码都实现熵。

当霍夫曼编码二进制字符串时，即使熵低（例如（{0, 1}）具有概率{0.95, 0.05}），也不可能进行压缩。霍夫曼编码为每个值分配 1 位元，产生与输入长度相同的代码。相比之下，算术编码可以更加地压缩位元，接近最佳压缩比

1-[-0.95\log _{2}(0.95)+-0.05\log _{2}(0.05)]\approx 71.4\%.

解决霍夫曼编码次优性的一种简单方法是连接符号（阻塞）以形成新的字母表，其中每个新符号表示来自原始字母表的原始符号序列（在这种情况下是位元）。在上面的例子中，在编码之前对三个符号的序列进行分组将产生具有以下频率的新“超符号”：

000: 85.7%
001, 010, 100: 4.5% each
011, 101, 110: 0.24% each
111: 0.0125%

通过这种分组，霍夫曼编码每三个符号平均为 1.3 位元，或每符号 0.433 位元，而原始编码中每符号一位元，即 $56.7\%$ 压缩。允许任意大的序列随意接近熵（就像算术编码一样），但需要大量代码才能这样做，因此不如算术编码那么实用。

另一种方法是通过基于霍夫曼的 Golomb-Rice 编码编码游程长度。这种方法允许比算术编码或甚至霍夫曼编码更简单和更快的编码/解码，因为后者需要表查找。在 {0.95, 0.05} 示例中，具有四位余数的 Golomb-Rice 代码实现了压缩率 $71.1\%$ ，远远低于使用三位块的压缩率。 Golomb-Rice 代码仅适用于伯努利输入，例如本例中的输入，因此它不能代替所有情况下的阻塞。

区间编码

算术编码与区间编码有很深的相似渊源，以至于人们通常认为两者的性能是相同的，如果确实有什么不同的话也只是区间编码仅仅落后几个位的值而已。区间编码与算术编码不同，通常认为它不被任何公司的专利所约束。

区间编码的原理是这样的，它没有像算术编码那样从 [0,1] 开始并根据每个字符出现的概率把它分成相应的不同的小区间，它从如 000,000,000,000 到 999,999,999,999 这样一个很大的非负整数区间开始，并且根据每个字符的概率划分成小的子区间。当子区间小到一定程度最后结果的开头数字出现的时候，那些数字就能够“左移”出整个运算，并且用“右边”的数字替换——每次出现移位时，就大体相当于最初区间的一个回归放大（retroactive multiplication）。

关于算术编码的美国专利

许多算术编码所用的不同方法受美国专利的保护。其中一些专利对于实现一些国际标准中定义的算术编码算法是很关键的。在这种情况下，这些专利通常按照一种合理和非歧视（RAND）授权协议使用（至少是作为标准委员会的一种策略）。在一些著名的案例中（包括一些涉及IBM的专利）这些授权是免费的，而在另外一些案例中，则收取一定的授权费用。RAND条款的授权协议不一定能够满足所有打算使用这项技术的用户，因为对于一个打算生产拥有所有权软件的公司来说这项费用是“合理的”，而对于自由软件和开源软件项目来说它是不合理的。

在算术编码领域做了很多开创性工作并拥有很多专利的一个著名公司是IBM。一些分析人士感到那种认为没有一种实用并且有效的算术编码能够在不触犯IBM和其它公司拥有的专利条件下实现只是数据压缩界中的一种持续的都会传奇（尤其是当看到有效的算术编码已经使用了很长时间最初的专利开始到期）。然而，由于专利法没有提供“明确界线”测试所以一种威慑心理总让人担忧法庭将会找到触犯专利的特殊应用，并且随着对于专利范围的详细审查将会发现一个不好的裁决将带来很大的损失，这些技术的专利保护然而对它们的应用产生了一种阻止的效果。至少一种重要的压缩软件bzip2，出于对于专利状况的担心，故意停止了算术编码的使用而转向Huffman编码。

关于算术编码的美国专利列在下面。

Patent 4,122,440—（IBM）提交日期March 4, 1977,批准日期Oct 24, 1978（现在已经到期）
Patent 4,286,256—（IBM）批准日期Aug 25, 1981（大概已经到期）
Patent 4,467,317—（IBM）批准日期Aug 21, 1984（大概已经到期）
Patent 4,652,856—（IBM）批准日期Feb 4, 1986（大概已经到期）
Patent 4,891,643—（IBM）提交时间1986/09/15,批准日期1990/01/02
Patent 4,905,297—（IBM）批准日期Feb 27, 1990
Patent 4,933,883—（IBM）批准日期Jun 12, 1990
Patent 4,935,882—（IBM）批准日期Jun 19, 1990
Patent 4,989,000—（???）提交时间1989/06/19,批准日期1991/01/29
Patent 5,099,440
Patent 5,272,478—（Ricoh）

注意：这个列表没有囊括所有的专利。关于更多的专利资讯请参见后面的链接。[1] （页面存档备份，存于互联网档案馆）

算术编码的专利可能在其它国家司法领域存在，参见软件专利中关于软件在世界各地专利性的讨论。

参考

上面文章的一个早期版本（公开内容）张贴在PlanetMath （页面存档备份，存于互联网档案馆）.

外部链接

The on-line textbook: Information Theory, Inference, and Learning Algorithms （页面存档备份，存于互联网档案馆）, by David J.C. MacKay, explains arithmetic coding in Chapter 6.
本条目引用的公有领域材料。材料来自NIST的文档：Black, Paul E. arithmetic coding. 算法与数据结构辞典（英语：Dictionary of Algorithms and Data Structures）.
"Arithmetic Coding" site on Compression-links.info (free open version of DataCompression.info) （页面存档备份，存于互联网档案馆） - collection of links pertaining to arithmetic coding
Newsgroup posting （页面存档备份，存于互联网档案馆） with a short worked example of arithmetic encoding (integer-only).
AIC-Context Adaptive Binary Arithmetic Coding （页面存档备份，存于互联网档案馆） very clear concept and demonstration for fresher.