重定向;重新导向;字符;字元;文件; 档案;快捷方式; 捷径;项目;专案;计划;计划;计划;计算机; 电脑; 电脑; 算术编码是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足（0.0 ≤ "n" formula_5 现在要对dataX做编码，假设length(X) = N initiation: lower = formula_6 upper = formula_7 for i=2:N lower = formula_8 upper = formula_9) end 假设 lowerformula_10 且C和b为整数(b越小越理想)，则dataX可以被编码成formula_11 且formula_11为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 formula_13 若实际上输入的资料为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 formula_14 upper 所以编码结果为 formula_15,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 formula_16 and formula_17 are both satisfied, then check = 0; else formula_18 formula_19 j = j+1 end X(i) = n; formula_20 formula_21 end 资料长度. 假设formula_4是预测的X[i] = n的机率,formula_23是实际上的X[i] = n的机率 也就是说,若length(X) = N,当中会有formula_23N个elements等于n 则formula_25 另一方面，由于编码的假设 formula_26 formula_27 formula_28 在机率的预测完全准确的情况下,formula_29 Totoal coding length b 的范围是 formula_30 formula_31 算术编码的总资料长度的上限比霍夫曼编码更低 自适应算术编码. 与其他类似的数据压缩方法相比，算术编码的一个优点是适应的便利性。适应是在处理数据时改变频率（或概率）表。只要解码中的频率表以与编码相同的方式和相同的步骤被替换，解码的数据就匹配原始数据。通常，同步基于在编码和解码过程期间出现的符号的组合。 精度和再正规化. 上面对算术编码的解释进行了一些简化。尤其是，这种写法看起来好像算术编码首先使用无限精度精度的数值计算总体上表示最后节点的分数，然后在编码结束的时候将这个分数转换成最终的形式。许多算术编码器使用有限精度的数值计算，而不是尽量去模拟无限精度，因为它们知道解码器能够匹配、并且将所计算的分数在那个精度四舍五入到对应值。一个例子能够说明一个模型要将间隔[0,1]分成三份并且使用8位的精度来实现。注意既然精度已经知道，我们能用的二进制数值的范围也已经知道。 一个称为"再归一化"的过程使有限精度不再是能够编码的字符数目的限制。当范围减小到范围内的所有数值共享特定的数字时，那些数字就送到输出数据中。尽管计算机"能够"处理许多位数的精度，编码所用位数少于它们的精度，这样现存的数据进行左移，在右面添加新的数据位以尽量扩展能用的数据范围。注意这样的结果出现在前面三个例子中的两个里面。 算术编码和其他压缩方法的关系. 霍夫曼编码. 算术编码和哈夫曼编码的相似程度很高——事实上，哈夫曼编码只是算术编码的一个特例。但是，算术编码将整个消息翻译成一个表示为基数 "b"，而不是将消息中的每个符号翻译成一系列的以 "b" 为基数的数字，因此通常比哈夫曼编码更能达到最优熵编码。 因为算术编码不能一次压缩一个数据，所以在压缩iid字符串时它可以任意接近熵。相反，使用霍夫曼编码（到字符串）的扩展不会达到熵，除非字母符号的所有概率都是 2 的幂，在这种情况下，霍夫曼和算术编码都实现熵。 当霍夫曼编码二进制字符串时，即使熵低（例如（{0, 1}）具有概率{0.95, 0.05}），也不可能进行压缩。霍夫曼编码为每个值分配 1 位元，产生与输入长度相同的代码。相比之下，算术编码可以更加地压缩位元，接近最佳压缩比 formula_32 解决霍夫曼编码次优性的一种简单方法是连接符号（阻塞）以形成新的字母表，其中每个新符号表示来自原始字母表的原始符号序列（在这种情况下是位元）。在上面的例子中，在编码之前对三个符号的序列进行分组将产生具有以下频率的新「超符号」： 通过这种分组，霍夫曼编码每三个符号平均为 1.3 位元，或每符号 0.433 位元，而原始编码中每符号一位元，即 formula_33 压缩。允许任意大的序列随意接近熵（就像算术编码一样），但需要大量代码才能这样做，因此不如算术编码那么实用。 另一种方法是通过基于霍夫曼的 Golomb-Rice 编码编码游程长度。这种方法允许比算术编码或甚至霍夫曼编码更简单和更快的编码/解码，因为后者需要表查找。在 {0.95, 0.05} 示例中，具有四位余数的 Golomb-Rice 代码实现了压缩率 formula_34 ，远远低于使用三位块的压缩率。 Golomb-Rice 代码仅适用于伯努利输入，例如本例中的输入，因此它不能代替所有情况下的阻塞。 区间编码. 算术编码与区间编码有很深的相似渊源，以至于人们通常认为两者的性能是相同的，如果确实有什么不同的话也只是区间编码仅仅落后几个位的值而已。区间编码与算术编码不同，通常认为它不被任何公司的专利所约束。 区间编码的原理是这样的，它没有像算术编码那样从 [0,1] 开始并根据每个字符出现的概率把它分成相应的不同的小区间，它从如 000,000,000,000 到 999,999,999,999 这样一个很大的非负整数区间开始，并且根据每个字符的概率划分成小的子区间。当子区间小到一定程度最后结果的开头数字出现的时候，那些数字就能够“左移”出整个运算，并且用“右边”的数字替换——每次出现移位时，就大体相当于最初区间的一个回归放大（retroactive multiplication）。 关于算术编码的美国专利. 许多算术编码所用的不同方法受美国专利的保护。其中一些专利对于实现一些国际标准中定义的算术编码算法是很关键的。在这种情况下，这些专利通常按照一种"合理和非歧视"（RAND）授权协议使用（至少是作为标准委员会的一种策略）。在一些著名的案例中（包括一些涉及IBM的专利）这些授权是免费的，而在另外一些案例中，则收取一定的授权费用。RAND条款的授权协议不一定能够满足所有打算使用这项技术的用户，因为对于一个打算生产拥有所有权软件的公司来说这项费用是“合理的”，而对于自由软件和开源软件项目来说它是不合理的。 在算术编码领域做了很多开创性工作并拥有很多专利的一个著名公司是IBM。一些分析人士感到那种认为没有一种实用并且有效的算术编码能够在不触犯IBM和其它公司拥有的专利条件下实现只是数据压缩界中的一种持续的都会传奇（尤其是当看到有效的算术编码已经使用了很长时间最初的专利开始到期）。然而，由于专利法没有提供“明确界线”测试所以一种威慑心理总让人担忧法庭将会找到触犯专利的特殊应用，并且随着对于专利范围的详细审查将会发现一个不好的裁决将带来很大的损失，这些技术的专利保护然而对它们的应用产生了一种阻止的效果。至少一种重要的压缩软件bzip2，出于对于专利状况的担心，故意停止了算术编码的使用而转向Huffman编码。 关于算术编码的美国专利列在下面。 注意：这个列表没有囊括所有的专利。关于更多的专利信息请参见后面的链接。 （页面存档备份，存于互联网档案馆;网际网路档案馆;互联网档案馆;互联网档案馆;） 算术编码的专利可能在其它国家司法领域存在，参见软件专利中关于软件在世界各地专利性的讨论。 参考. "上面文章的一个早期版本（公开内容）张贴在PlanetMath （页面存档备份，存于互联网档案馆;网际网路档案馆;互联网档案馆;互联网档案馆;）."