【2017年整理】算术编码工作原理

《【2017年整理】算术编码工作原理》由会员分享，可在线阅读，更多相关《【2017年整理】算术编码工作原理（5页珍藏版）》请在金锄头文库上搜索。

1、算术编码工作原理在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。例 : 对一个简单的信号源进行观察，得到的统计模型如下： 60% 的机会出现符号 中性 20% 的机会出现符号 阳性 10% 的机会出现符号 阴性 10% 的机会出现符号 数据结束符. (出现这个符号的意思是该信号源 内部中止 ，在进行数据压缩时这样的情况是很常见的。当第一次也是唯一的一次看到这个符号时，解码器就知道整个信号流都被解码完成了。 )算术编码可以处理的例子不止是这种只有四种符号的情况，更复杂

2、的情况也可以处理，包括 高阶 的情况。所谓高阶的情况是指当前符号出现的概率受之前出现符号的影响，这时候之前出现的符号，也被称为 上下文 。比如在英文文档编码的时候，例如，在字母 Q 或者 q 出现之后，字母 u 出现的概率就大大提高了。这种模型还可以进行 自适应的变化，即在某种上下文下出现的概率分布的估计随着每次这种上下文出现时的符号而自适应更新，从而更加符合实际的概率分布。不管编码器使用怎样的模型，解码器也必须使用同样的模型。一个简单的例子 以下用一个符号串行怎样被编码来作一个例子： 假如有一个以A、B、C 三个出现机会均等的符号组成的串行。若以简单的分组编码会十分浪费地用 2 bits 来

3、表示一个符号： 其中一个符号是可以不用传的(下面可以见到符号 B 正是如此)。为此， 这个串行可以三进制的 0 和 2 之间的有理数表示， 而且每位数表示一个符号。例如， “ABBCAB” 这个串行可以变成 0.011201(base3)(即 0 为 A, 1 为 B, 2 为 C)。用一个定点二进制数字去对这个数编码使之在恢复符号表示时有足够的精度，譬如0.001011001(base2) 只用了 9 个 bit，比起简单的分组编码少(1 9/12)x100% = 25%。 这对于长串行是可行的因为有高效的、适当的算法去精确地转换任意进制的数字。编码过程的每一步，除了最后一步，都是相同的。编

4、码器通常需要考虑下面三种数据： 下一个要编码的符号 当前的区间(在编第一个符号之前，这个区间是0,1), 但是之后每次编码区间都会变化) 模型中在这一步可能出现的各个符号的概率分布(像前面提到的一样，高阶或者自适应的模型中，每一步的概率并不必须一样)编码其将当前的区间分成若干子区间，每个子区间的长度与当前上下文下可能出现的对应符号的概率成正比。当前要编码的符号对应的子区间成为在下一步编码中的初始区间。例 : 对于前面提出的 4 符号模型: 中性对应的区间是 0, 0.6) 阳性对应的区间是 0.6, 0.8) 阴性对应的区间是 0.8, 0.9) 数据结束符对应的区间是 0.9, 1)当所有的

5、符号都编码完毕，最终得到的结果区间即唯一的确定了已编码的符号串行。任何人使用该区间和使用的模型参数即可以解码重建得到该符号串行。实际上我们并不需要传输最后的结果区间，实际上，我们只需要传输该区间中的一个小数即可。在实用中，只要传输足够的该小数足够的位数(不论几进制)，以保证以这些位数开头的所有小数都位于结果区间就可以了。例 : 下面对使用前面提到的 4 符号模型进行编码的一段信息进行解码。编码的结果是0.538(为了容易理解，这里使用十进制而不是二进制；我们也假设我们得到的结果的位数恰好够我们解码。下面会讨论这两个问题)。像编码器所作的那样我们从区间0,1)开始，使用相同的模型，我们将它分成编

6、码器所必需的四个子区间。分数 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) 区间；所以消息的第二个符号一定

7、是 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

8、 或者是.539，这表明使用十进制而不是二进制会带来效率的降低。这是正确的是因为三位十进制数据能够表达的信息内容大约是 9.966 位；我们也能够将同样的信息使用二进制分数表示为.10001010（等同于 0.5390625），它仅需 8 位。这稍稍大于信息内容本身或者消息的信息熵，大概是概率为 0.6%的 7.361 位信息熵。（注意最后一个 0 必须在二进制分数中表示，否则消息将会变得不确定起来。）编辑 精度和再正规化上面对算术编码的解释进行了一些简化。尤其是，这种写法看起来好像算术编码首先使用无限精度精度的数值计算总体上表示最后节点的分数，然后在编码结束的时候将这个分数转换成最终的形式。

9、许多算术编码器使用优先精度的数值计算，而不是尽量去模拟无限精度，因为它们知道解码器能够匹配、并且将所计算的分数在那个精度四舍五入到对应值。一个例子能够说明一个模型要将间隔0,1分成三份并且使用 8 位的精度来实现。注意既然精度已经知道，我们能用的二进制数值的范围也已经知道。符号概率（使用分数表示）减到 8 位精度的间隔（用分数表示）减到 8 位精度的间隔（用二进制表示） 二进制范围A 1/3 0, 85/256) 0.00000000, 0.01010101) 00000000 - 01010100B 1/3 85/256, 171/256) 0.01010101, 0.10101011) 0

10、1010101 - 10101010C 1/3 171/256, 1) 0.10101011, 1.00000000) 10101011 - 11111111一个称为 再归一化 的过程使有限精度不再是能够编码的字符数目的限制。当范围减小到范围内的所有数值共享特定的数字时，那些数字就送到输出数据中。尽管计算机 能够 处理许多位数的精度，编码所用位数少于它们的精度，这样现存的数据进行左移，在右面添加新的数据位以尽量扩展能用的数据范围。注意这样的结果出现在前面三个例子中的两个里面。符号 概率 范围 能够输出的数据位 再归一化后的范围A 1/3 00000000 - 01010100 0 000000

11、00 - 10101001B 1/3 01010101 - 10101010 None 00101010 - 11010101C 1/3 10101011 - 11111111 1 01010110 - 11111111编辑 算术编码和其他压缩方法的联系编辑 哈夫曼编码在算术编码和哈夫曼编码之间有很大的相似性 - 实际上，哈夫曼编码只是算术编码的一个特例 - 但是由于算术编码将整个消息翻译成一个表示为 基数 b,而不是将消息中的每个符号翻译成一系列的以 b 为基数的数字，它通常比哈夫曼编码更能达到最优熵编码。编辑 区间编码算术编码与区间编码有很深的相似渊源，它们如此相似以至于通常认为它们的性能

12、是相同的，如果确实有什么不同的话也只是区间编码仅仅落后几个位的值而已。区间编码与算术编码不同，通常认为它不被任何公司的专利所涵盖。区间编码的原理是这样的，它没有像算术编码那样从0,1开始并根据每个字符出现的概率把它分成相应的不同的小区间，它从如 000,000,000,000 到 999,999,999,999 这样一个很大的非负整数区间开始，并且根据每个字符的概率划分成小的子区间。当子区间小到一定程度最后结果的开头数字出现的时候，那些数字就能够“左移”出整个运算，并且用“右边”的数字替换-每次出现移位时，就大体相当于最初区间的一个回归放大（retroactive multiplication

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

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

15、t 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)