Abh*_*hek 9 compression algorithm encoding entropy lossless-compression
任何人都可以解释数据压缩的算术编码与实现细节？我已经通过互联网浏览并找到了标记纳尔逊的帖子,但是在尝试了很长时间之后,实施的技术确实不清楚.
马克纳尔逊关于算术编码的解释可以在
http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/
Cya*_*yan 14
算术压缩的主要思想是使用所需的精确数据长度来编码概率的能力.
Shannon证明了这一数据量,可以简单地使用以下公式计算:-log2(p)
例如,如果p = 50%,则需要1位.如果p = 25%,则需要2位.
这对于2的幂的概率来说足够简单(在这种特殊情况下,霍夫曼编码就足够了).但如果概率为63%怎么办？然后你需要-log2(0.63)= 0.67位.听起来很棘手......
如果您的概率很高,此属性尤为重要.如果你能够以95%的准确率预测某些东西,那么你只需要0.074位代表一个好的猜测.这意味着你要压缩很多.
现在,怎么做？
嗯,它比听起来更简单.您将根据概率划分范围.例如,如果您有100个可能的事件范围,第一个事件的概率为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个.