任何人都可以用实现细节解释数据压缩的算术编码吗？我通过互联网浏览并找到了马克纳尔逊的帖子，但在尝试了几个小时后，我确实不清楚实现的技术。
Mark nelson 关于算术编码的解释可以位于
http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/
问问题
4578 次
3 回答
15
算术压缩的主要思想是它能够使用所需的确切数据长度对概率进行编码。
这个数据量是已知的，由 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 个。
于 2012-04-16T17:17:28.810 回答
2
也许这个脚本可能有助于构建一个更好的算术编码器心智模型：gen_map.py。最初创建它是为了方便算术编码器库的调试并简化其单元测试的生成。然而，它创建了很好的 ASCII 可视化，这对于理解算术编码也很有用。
一个小例子。想象一下，我们有一个由 3 个符号组成的字母表：0，1和2概率1/10，2/10和7/10对应。我们要对序列进行编码[1, 2]。脚本将给出以下输出（暂时忽略-b N选项）：
$ ./gen_map.py -b 6 -m "1,2,7" -e "1,2"
000000111111|1111|111222222222222222222222222222222222222222222222
------011222|2222|222000011111111122222222222222222222222222222222
---------011|2222|222-------------00011111122222222222222222222222
------------|----|-------------------------00111122222222222222222
------------|----|-------------------------------01111222222222222
------------|----|------------------------------------011222222222
==================================================================
000000000000|0000|000000000000000011111111111111111111111111111111
000000000000|0000|111111111111111100000000000000001111111111111111
000000001111|1111|000000001111111100000000111111110000000011111111
000011110000|1111|000011110000111100001111000011110000111100001111
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
001100110011|0011|001100110011001100110011001100110011001100110011
010101010101|0101|010101010101010101010101010101010101010101010101
前 6 行（====行前）表示从 0.0 到 1.0 的范围，该范围以与符号概率成比例的间隔递归细分。注释的第一行：
[1/10][ 2/10 ][ 7/10 ]
000000111111|1111|111222222222222222222222222222222222222222222222
然后我们再次细分每个区间：
[ 0.1][ 0.2 ][ 0.7 ]
000000111111|1111|111222222222222222222222222222222222222222222222
[ 0.7 ][.1][ 0.2 ][ 0.7 ]
------011222|2222|222000011111111122222222222222222222222222222222
[.1][ .2][ 0.7 ]
---------011|2222|222-------------00011111122222222222222222222222
请注意，某些区间没有细分。当没有足够的空间来表示给定精度（由-b选项指定）内的每个子区间时，就会发生这种情况。
每行对应于输入中的一个符号（在我们的例子中 - 序列[1, 2]）。通过跟踪每个输入符号的子间隔，我们将得到一个最终的间隔，我们想要用最少的比特进行编码。在我们的例子中，它2是第二行的第一个子区间：
[ This one ]
------011222|2222|222000011111111122222222222222222222222222222222
以下 7 行（之后====）表示相同的区间 0.0 到 1.0，但根据二进制符号进行细分。每行都是一个输出，通过在 0 和 1 之间进行选择，您可以选择左半子间隔或右半子间隔。例如，位01对应于[0.25, 05)第二行的子间隔：
[ This one ]
000000000000|0000|111111111111111100000000000000001111111111111111
算术编码器的思想是输出位（0 或 1），直到相应的区间完全在（或等于）输入序列确定的区间内。在我们的例子中，它是0011. 该~~~~行显示了我们在哪里有足够的位来明确识别我们想要的间隔。
由|符号组成的垂直线表示可用于对输入序列进行编码的位序列（行）的范围。
于 2015-10-12T01:22:49.450 回答
1
首先感谢您向我介绍算术压缩的概念！
我可以看到这个方法有以下步骤：
- 创建映射：计算每个字母出现的比例，给出每个字母的范围大小。然后对它们进行排序并分配从 0 到 1 的实际范围
- 给定一条消息，计算范围（非常简单的恕我直言）
- 找到最优代码
第三部分有点棘手。使用以下算法。
令 b 为最优表示。将其初始化为空字符串 ('')。令 x 为最小值， y 为最大值。
- 双倍 x 和 y：x=2*x, y=2*y
- 如果它们都大于 1，则将 1 添加到 b。转到步骤 1。
- 如果两者都小于 1，则将 0 附加到 b。转到步骤 1。
- 如果 x<1，但 y>1，则将 1 附加到 b 并停止
b 基本上包含您正在传输的数字的小数部分。例如。如果 b=011，则分数对应于二进制的 0.011。
您不了解实施的哪一部分？
于 2012-04-13T21:15:46.137 回答