算术编码的数据压缩

算术编码是在无损和有损数据压缩算法中使用的通用算法。

这是一种熵编码技术，其中，与很少见的符号相比，经常见到的符号用更少的比特进行编码。与诸如霍夫曼编码的众所周知的技术相比，它具有一些优点。本文将详细描述算术编码的CACM87实现，使您对实现它所需的所有细节都有很好的了解。

从历史上看，这篇文章是我二十多年前写的《使用算术编码的数据压缩》的更新。该文章发表在《多布博士杂志》的印刷版上，这意味着要进行大量编辑以避免页数过多。特别是Dobb博士的那篇文章结合了两个主题：算术编码的描述以及对使用PPM（部分匹配的预测）的压缩的讨论。

由于这一新文章将在网络上发布，因此空间因素不再是一个很大的因素，我希望这可以使我对算术编码的细节做到合理。 PPM是一个很有价值的话题，将在以后的文章中进行讨论。我希望这项新的努力将使我在1991年想要做的这个问题的解释冗长而烦人。

我认为理解算术编码的最好方法是将其分为两部分，在本文中我将使用该思想。首先，我将描述使用标准C ++数据类型实现的常规浮点算术进行算术编码的工作方式。这样可以实现完全可理解但不切实际的实现。换句话说，它可以工作，但是只能用于编码非常短的消息。

本文的第二部分将描述一个实现，在该实现中，我们切换为对无界二进制数进行特殊类型的数学运算。这本身就是一个令人难以置信的话题，因此，如果您已经了解算术编码，那么它会有所帮助-您不必为尝试一次学习两件事而烦恼。

最后，我将介绍用现代C ++编写的工作示例代码。它不一定是世界上最优化的代码，但是它可移植并且易于添加到现有项目中。对于学习和尝试这种编码技术来说，它应该是完美的。

关于算术编码，首先要了解的是它产生的结果。算术编码采用由符号（几乎总是八位字符）组成的消息（通常是文件），并将其转换为大于或等于零且小于一的浮点数。这个浮点数可能会很长-实际上您的整个输出文件是一个长数字-这意味着它不是您习惯于在常规编程语言中使用的普通数据类型。我对算法的实现将必须从头开始一点一点地创建此浮点数，然后同样地读取它并对其进行一点点解码。

该编码过程是逐步完成的。在对文件中的每个字符进行编码时，会将几位添加到编码后的消息中，因此随着算法的进行，它会随着时间的推移逐渐建立。

关于算术编码的第二点要理解的是，它依赖于模型来表征正在处理的符号。该模型的工作是告诉编码器给定消息中字符的概率是多少。如果模型给出消息中字符的准确概率，则将对它们进行非常接近的最佳编码。如果模型错误表示符号的概率，则您的编码器实际上可能会扩展一条消息，而不是对其进行压缩！

术语算术编码必须涵盖两个独立的过程：对消息进行编码和对其进行解码。我将首先看一下示例C ++代码的编码过程，该示例代码使用C ++双重数据以非常有限的形式实现了该算法。第一部分中的代码仅用于说明-不要尝试对其进行任何实际压缩。

要执行算术编码，我们首先需要定义一个合适的模型。请记住，模型的功能是提供消息中给定字符的概率。算术编码模型的概念是，每个符号都将拥有自己的介于0和1之间的实数数字线的唯一部分。需要注意的是，有许多不同的方法可以模拟字符概率。有些模型是静态的，永远不会改变。其他字符在处理完每个字符后更新。对我们而言唯一重要的两件事是：1）模型试图准确地预测字符出现的可能性； 2）编码器和解码器始终具有相同的模型。

例如，我们可以从只能编码100个不同字符的字母的编码器开始。在一个简单的静态模型中，我们将从大写字母开始，然后是小写字母。这意味着第一个符号“ A”将拥有从0到.01的数字行，“ B”将拥有.01到.02的数字，依此类推。 （在所有情况下，严格来说，这都是半封闭的时间间隔，因此“ A”的概率范围实际上是＆gt; = 0且＆lt; .01。）

使用此模型，我的编码器可以通过输出小于.02且大于或等于.01的浮点数来表示单个字母“ B”。因此，例如，想要创建单个字母的算术编码器可以输出.15并完成。

不过，仅输出单个字符的编码器用处不大。编码符号字符串涉及稍微复杂一些的过程。在此过程中，第一个字符定义了数字行的范围，该范围与模型分配给它的部分相对应。对于字符“ B”，这意味着消息在.01到.02之间。

然后，消息中的下一个字符会进一步将现有范围与其当前对数字行的所有权进行划分。因此，拥有数字行末尾的其他某个字母（从.99到1.0）会将范围从[.01，.02）更改为[.0199，.020）。范围的这种逐步细分只是简单的乘法和加法，并且通过简单的代码示例可以最好地理解。我在C ++中的第一个过程（远离可用的编码器）可能看起来像这样：

双高= 1.0;双低= 0.0;字符c; while（input＆gt;＆gt; c）{std :: pair＆lt;双重，双重＆gt; p =模型。 getProbability（c）;双倍范围=高-低;高=低+范围* p。第二;低=低+范围* p。首先; }输出＆lt;＆lt;低+（高-低）/ 2;

在处理完整个消息之后，我们得到了一个最终范围，[低，高]。编码器在该范围的正中输出一个浮点数。

首遍编码器在附加项目中显示为fp_proto.cpp。为了使其正常工作，我还需要定义一个简单的模型。在这种情况下，我创建了一个可以编码100个字符的模型，每个字符的固定概率为0.01，从第一个位置的“ A”开始。为简单起见，我仅充实了该类，足以对ASCII字符集的大写字母进行编码：

struct {static std :: pair＆lt;双重，双重＆gt; getProbability（char c）{if（c＆gt; =＆＃39; A＆＃39;＆amp;＆amp; c＆lt; =＆＃39; Z＆＃39;）return std :: make_pair（（c-＆＃39; A＆＃39;）* .01，（c-＆＃39; A *＃01 + .01）;否则将＆＃34;字符超出范围＆＃34; ;模型;

因此，在此概率模型中，“ A”拥有0.0到0.01的范围，“ B”拥有0.01到.02的范围，“ C”拥有0.02到.03的范围，依此类推。 （请注意，这不是一个准确或有效的模型，但在这一点上它的简单性很有用。）对于一个代表性的示例，我将此编码器称为字符串“ WXYZ”。让我们看一下编码器中发生的情况。

我们首先将上限和下限设置为1.0和0.0。编码器调用模型以获取字母“ W”的概率，该概率返回间隔[0.22，0.23）-沿着模型中“ W”拥有的概率线的范围。如果您越过接下来的两行，现在会看到低设置为0.22，高设置为0.23。

如果检查一下它是如何工作的，您会发现在对每个字符进行编码时，高和低之间的范围会越来越窄，但高总是会大于低。另外，low的值总是在增加，而high的值总是在减少。这些不变量对于使算法正常工作很重要。

因此，在对第一个字符进行编码之后，我们知道，无论对什么其他值进行编码，消息中的最终数字都将小于.23且大于或等于.22。低和高都将大于等于0.22且小于.23，低将严格小于高。这意味着在解码时，无论此后发生什么，我们都将能够确定第一个字符为“ W”，因为最终的编码数字将落入“ W”拥有的范围内。缩小过程大致如下图所示：

逐步缩小编码器范围让我们看看处理第二个字符“ X”时这种缩小的工作方式。模型针对此字符返回范围为[.23，.24），随后重新计算高和低结果为[.2223，.2224）和间隔。因此高和低仍在[.22，.23）的原始范围内，但间隔已变窄。

我将详细讨论如何选择需要输出的确切值，但至少在理论上，对于此特定消息，间隔[0.22232425,0.22232426）中的任何浮点数都应正确解码为所需值。

我发现编码算法非常直观。解码器可以逆转该过程，并且不再复杂，但是步骤似乎不太明显。解码此消息的首过算法如下所示：

无效解码（双消息）{双高= 1.0;双低= 0.0;对于（;;）{double range = high-low; char c =模型。 getSymbol（（消息-低）/范围）; std :: cout＆lt;＆lt; C ;如果（c ==＆＃39; Z＆＃39;）返回; std ::对＆lt;双重，双重＆gt; p =模型。 getProbability（c）;高=低+范围* p。第二;低=低+范围* p。首先; }}

解码器中的数学运算基本上从编码方面反转数学运算。要解码一个字符，概率模型只需要找到范围覆盖消息当前值的字符。当解码器首先以0.22232425的样本值启动时，模型会看到该值介于'W'拥有的间隔之间：[0.22,0.23），因此模型返回W。在fp_proto.cpp中，简单的模型如下所示：

静态char getSymbol（double d）{if（d＆gt; = 0.0＆amp; d＆lt; 0.26）return＆＃39; A＆＃39; + static_cast＆lt;整数＆gt; （d * 100）;否则会抛出＆＃34;消息超出范围＆＃34; ; }

在编码器中，随着每个字符的处理，我们不断缩小输出值的范围。在解码器中，我们对正在检查下一个字符的消息部分进行相同的缩小。解码完“ W”后，现在高和低将定义为[0.22,0.23）的间隔，范围为.01。因此，计算下一个要解码的概率值（消息-低）/范围的公式将为.2324255，该表达式恰好位于由'X'覆盖的范围的中间。

随着字符被解码，这种缩小将继续，直到到达消息的硬编码字母“ Z”为止。成功！

至此演示的算法可以在附加项目中使用fp_proto.cpp进行测试。您需要非常清楚，到目前为止我们还没有看到真正有效或有用的编码器。但是，它确实以某种精度演示了算法的一般流程。到目前为止的主要观察结果是：

根据字符在概率范围[0，1）中的位置对字符进行编码。我们使用变量高和低来跟踪当前状态。有效的输出结果将是[低，高]范围内的任何数字。在对每个字符进行编码时，它会以与其在概率范围内的位置完全对应的方式压缩范围[低，高]。我们有一些不变量是由算法中使用的数学得出的。低的值永不减少，高的值永不增加，低始终小于高。

这个演示算法的最大问题是它依赖C ++的double值来保持消息状态。浮点变量的精度有限，这意味着最终，随着高低之间的范围持续缩小，它们之间的距离变得太小而无法用浮点变量表示。使用此处使用的模型，您可以编码10个左右的字符，但此后该算法将无法工作。

本文的其余部分将介绍一个功能齐全的算法。从概念上讲，它看起来非常像已经介绍的代码。最大的区别在于，编码器和解码器中使用的变量high，low和message不再是C ++类型的double。相反，它们将是任意长的二进制变量。

为了使我们的程序能够处理任意长度的二进制数，将一次对它们进行一次处理，读取位，执行计算，然后输出位，然后由于不再需要而将其丢弃。如何完成此操作的详细信息是该算法中所有工作都发挥作用的地方。

除了这些修改之外，本文的其余部分还将涵盖其他一些尚未处理的问题，包括：

如何处理流的结尾。如何从[低，高]范围内选择实际输出编号。为什么算术编码优于霍夫曼编码作为熵编码器。

在本篇的第二部分中，您将不得不绕过一些非常规数学。本文第一部分中描述的算法仍将如实执行，但是将不再使用double类型的变量来实现。它会用整数变量和整数数学来实现，尽管会以有趣的方式进行。

我们实现的基本概念是：高，低和实际编码的消息的值将是无限制长度的二进制数。换句话说，当我们完成对Gutenberg项目的Moby Dick编码时，高和低将为数百万个比特长，而输出值本身将为数百万个比特长。这三个值仍将代表一个大于或等于0且小于1的数字。

一个更有趣的方面是，即使游戏中的三个数字长达数百万个位，但是每次我们处理一个字符时，我们都只会执行一些简单的整数数学运算-32位，或者如果您愿意的话，可能是64位。

回想一下，在该算法的参考版本中，low和high的初始化如下：

这两个数字的值前都有一个隐含的小数点，这意味着高（十六进制）实际上是0.FFFFFFFF，或二进制是0.1111…1111，而低是0.0。同样，我们输出的数字将在第一位之前有一个隐含的小数点。

但这并不完全正确-在第一个实现中，最高值为1.0。值0.FFFFFFF接近，但仅比1.0小一点。如何处理？

这是一些令人费解的数学发挥作用的地方。尽管高位内存中有32位，但我们认为它在二进制数1的右端有无限长的尾迹。因此，不仅是0.FFFFFFFF，F串（或1​​串）继续延伸到无穷大-它们在那里，但还没有转移到内存中。

尽管可能并不明显，但Google可以帮助您说服以0.1开头的1的无限字符串实际上等于1。（简而言之：2x-x = 1.0，因此x = 1.0。）同样，low是被认为是一个无限长的二进制字符串，其中0悬挂在最后一个二进制位置。

请记住，最终实现将完全使用整数数学实现。以前，模型以一对浮点数返回概率，这些浮点数代表特定符号所拥有的范围。

在该算法的更新版本中，符号仍然在数字线上具有大于等于0且小于1的特定范围。院长这实际上并不会对我们的模型代码产生太大影响。我们在上一节中使用的示例模型返回了例如字符“ W”的.22和.23。现在，它将改为以称为prob的结构返回{22，23，100}。

在讨论最终的有效代码之前，我将介绍一些实现基本算法的代码，但是这些代码在实际问题上有一些捷径。此未完成的代码如下所示：

无符号整数高= 0xFFFFFFFFU;无符号整数低= 0;字符c; while（输入＆gt; c）{int range =高-低+ 1;概率p =模型。 getProbability（c）;高=低+（范围* p。上限）/ p。分母;低=低+（范围* p。较低）/ p。分母;对于（;;）{if（high＆lt; 0x80000000U）output_bit（0）;否则（低> = 0x80000000U）output_bit（1）;否则破裂;低＆lt;＆lt; = 1;高＆lt;＆lt; = 1;高| = 1; }}

该循环的第一部分在概念上和功能上与第1部分中给出的浮点代码相同。我们采用范围-即高低之间的差，并将该范围的一些子集分配给要编码的字符，具体取决于模型返回的概率。结果是，低一点变大，高一点变小。

代码的第二部分更加有趣。 while循环是新的，它的作用也很新-简化的浮点算法没有这样的功能。它在高和低之间执行范围检查，以寻找值具有相同最高有效位的情况。

第一个检查是查看高电平是否已降至0x80000000以下，在这种情况下，其MSB为0。因为我们知道低总是小于高，因此其MSB也将为0。并且由于两个值彼此之间更接近，这两个值的MSB将永远为0。

另一个范围检查将查看低端是否已增加到0x7FFFFFFF以上，在这种情况下，低端和高端的MSB值均为1，而MSB始终为1。

在这两种情况下，请记住，我们要处理三个不变量：高仅减少，低仅增加，并且高始终大于低。因此，一旦高位的前导位为0，它就永远不会改变。一旦低位的前导位为1，它就永远不会改变。在这种情况下，我们可以将该位输出到输出流-我们可以100％确定地知道它是什么，所以让我们将其移出输出流并摆脱它。

在输出了该位之后，我们将其丢弃。 向左高低移动一位将丢弃该MSB。 我们将1移到高的最低有效位，将0移到低的最低有效位。 因此，我们通过排除不再对计算精度有任何影响的位来继续保持32位精度。 在此特定实现中，我们仅将32位保留在工作寄存器中，其中一些其他数字已经发送到输出，而其他一些数字待输入。 下图显示了在任意压缩运行期间数学系统现在如何工作。 即使我们使用的是32位数学，该算法现在也可以处理 ......