ANS coding - baidut/co-codec GitHub Wiki

Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding 一文提出了一种新的熵编码方式。论文摘要的大致意思如下： 现代的数据压缩技术主要通过两种方式进行熵编码：哈夫曼编码（HC）和算术编码。前者速度更快，但压缩率低；后者几乎接近熵编码理论的压缩率极限，但是计算开销很大。

ANS-Asymmetric numeral systems 是一种新的无损压缩的方法，它实现了速度和压缩率的折衷。这种方法最新的实现的性能在与算术编码近似的压缩率的同时比HC编码快了50%（符号表大小为256）。 下面通过状态机模型解释算术编码和ANS编码的区别。 算术编码和ANS编码都是将符号序列处理成单个数的方法。 它的每个状态是由两个数决定的一个范围确定的，通过对一个范围不断按照概率分布划分子范围，最后取范围内任一个数得到最后的数，如下图。状态变迁规则：当需要在已压缩的数后再插入一个符号时，它将数的范围按照概率分布递增或递减的顺序依次划分给每个符号，取插入符号所在子范围。

而ANS方法的每个状态只由一个数确定，如果已压缩的数为X，让各个符号以不同的概率密度分布到自然数域，每个符号形成一个队列，然后取所插入符号对应的队列的第X个数作为X’，反复迭代地进行这个过程插入下一个符号，直到完成所有符号的编码。下图为二进制的情况：

X = 5， 当下一个符号s=0时X’ =8；当s=1时，X’ =16。