algorithm - 数据压缩 : Arithmetic coding unclear

Question

任何人都可以用实现细节解释数据压缩的算术编码吗？我浏览了互联网并找到了 mark nelson 的帖子，但在尝试了很多小时后，我确实不清楚实现的技术。

Mark nelson对算术编码的解释可以在

http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/

Answer 1

算术压缩的主要思想是它能够使用所需数据长度的确切数量来编码概率。

这个数据量是已知的，由 Shannon 证明，并且可以使用以下公式简单地计算:-log2(p)

例如，如果 p=50%，则需要 1 位。如果 p=25%，则需要 2 位。

这对于 2 的幂的概率来说已经足够简单了(在这种特殊情况下，霍夫曼编码就足够了)。但是如果概率是 63% 呢？然后你需要 -log2(0.63) = 0.67 位。听起来很棘手...

如果你的概率很高，这个属性就特别重要。如果你能以 95% 的准确率预测某些东西，那么你只需要 0.074 位来表示一个好的猜测。这意味着您将进行大量压缩。

现在，该怎么做？

嗯，它比听起来简单。您将根据概率划分您的范围。例如，如果范围为 100，有 2 个可能的事件，第一个事件的概率为 95%，则前 95 个值将表示“事件 1”，最后 5 个剩余值将表示“事件 2” .

好的，但是在计算机上，我们习惯于使用 2 的幂。例如，对于 16 位，您有 65536 个可能值的范围。做同样的事情:取范围的第一个 95%(即 62259)说“事件 1”，其余的说“事件 2”。你显然有一个“舍入”(精度)的问题，但只要你有足够的值来分配，就没有太大关系。此外，您不限于 2 个事件，您可以有无数个事件。重要的是根据每个事件的概率分配值。

好的，但现在我有 62259 个可能的值可以说“事件 1”，有 3277 个可能的值可以说“事件 2”。我应该选择哪一个？好吧，他们中的任何一个都可以。无论是 1、30、5500 还是 62256，它仍然表示“事件 1”。

事实上，决定选择哪个值并不取决于当前的猜测，而是取决于接下来的猜测。

假设我有“事件 1”。所以现在我必须选择 0 到 62256 之间的任何值。在下一次猜测中，我有相同的分布(95% 事件 1，5% 事件 2)。我将简单地分配具有这些概率的分布图。除了这次，它分布在 62256 个值上。我们继续这样，每次猜测都会缩小值的范围。

所以实际上，我们正在定义“范围”，每次猜测都会缩小范围。然而，在某些时候，存在准确性问题，因为只剩下很少的值。

这个想法是简单地再次“扩大”范围。例如，每次范围低于 32768 (2^15)，您输出最高位，并将其余位乘以 2(有效地将值左移一位)。通过不断地这样做，您正在一点一点地输出比特，因为它们是由一系列猜测确定的。

现在与压缩的关系变得明显:当范围迅速缩小(例如:5%)时，您输出大量位以使范围回到限制之上。另一方面，当概率很高时，范围会非常缓慢地缩小。在输出第一位之前，您甚至可以进行大量猜测。这就是将事件压缩到“一点点”的原因。

我特意使用了“概率”、“猜测”、“事件”等术语来使本文保持通用。但是对于数据压缩，您只需将它们替换为您想要的数据建模方式即可。例如，下一个事件可以是下一个字节；在这种情况下，您有 256 个。