算术编码简单研究

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

目录

[隐藏]

• 1 算术编码工作原理
• 2 精度和再正规化
• 3 算术编码和其他压缩方法的联系
  • 3.1 哈夫曼编码
  • 3.2 区间编码
• 4 关于算术编码的美国专利
• 5 参考
• 6 外部链接

[编辑] 算术编码工作原理

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

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

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

同样的消息能够使用同样短的分数来编码实现如 .534、.535、.536、.537或者是.539，这表明使用十进制而不是二进制会带来效率的降低。这是正确的是因为三位十进制数据能够表达的信息内容大约是9.966位；我们也能够将同样的信息使用二进制分数表示为.10001010（等同于0.5390625），它仅需8位。这稍稍大于信息内容本身或者消息的信息熵，大概是概率为0.6%的 7.361位信息熵。（注意最后一个0必须在二进制分数中表示，否则消息将会变得不确定起来。）

[编辑] 精度和再正规化

上面对算术编码的解释进行了一些简化。尤其是，这种写法看起来好像算术编码首先使用无限精度精度的数值计算总体上表示最后节点的分数，然后在编码结束的时候将这个分数转换成最终的形式。许多算术编码器使用优先精度的数值计算，而不是尽量去模拟无限精度，因为它们知道解码器能够匹配、并且将所计算的分数在那个精度四舍五入到对应值。一个例子能够说明一个模型要将间隔[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	00101010 - 11010101
C	1/3	10101011 - 11111111	1	01010110 - 11111111

[编辑] 算术编码和其他压缩方法的联系

[编辑] 哈夫曼编码

在算术编码和哈夫曼编码之间有很大的相似性 -- 实际上，哈夫曼编码只是算术编码的一个特例 -- 但是由于算术编码将整个消息翻译成一个表示为 基数 b,而不是将消息中的每个符号翻译成一系列的以b为基数的数字，它通常比哈夫曼编码更能达到最优熵编码。

[编辑] 区间编码

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

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

[编辑] 关于算术编码的美国专利

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

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

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