对 ANS 算法的简单介绍

ANS 算法来自于 Jagiellonian University 的 Jarek Duda 在 2014 年发表的一篇论文：Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding。
从标题来看，ANS 算法是一个既有 AC 算法的压缩率又有 Huffman 算法的压缩速度的无损压缩算法。我最近一直在研究怎么优化用户在移动端加载 3D 模型的体验。如果 ANS 算法所言非虚，那么我就可以通过不多的 CPU 资源(解压时间)来换大量的流量资源(下载时间)，从而降低用户在手机端加载模型的时间。
事实证明 ANS 算法确实很厉害，在权衡流量和 CPU 资源后，我们使用 ANS 把模型体积压缩到了上一代模型格式的 25%。20 万面的模型体积从 4 M(gzip后) 降低到了 1 M，在高通 610 CPU 的手机上，用微信浏览器解压大概需要 1.5~2 秒( 660 为 1秒)。也就是用 6 秒 的下载时间(根据我们的统计用户手机普遍下载速度为 500k/s) 换取了 2 秒的解压时间。而这只是非常低配的 610 处理器上面的表现。而且 CPU 性能的稳定性比网络性能的稳定性高得多。
在体验到 ANS 的巨大威力后，我实在按捺不住自己的好奇心，想去探究一下它的基本原理。

一. ANS 理论基础：香农熵

ANS 算法也是一种熵(Entropy)压缩算法，其理论基础来自于香农的信息熵理论。
在香农信息论中，有如下两个设定。

1.1 设定一：熵越高，信息越多

熵一般用来表示混乱程度和不确定性。概率越低的事件，熵越高。
熵越高，信息越多，也就是说概率越低，信息越多。
为什么呢？因为当一个人对一件事情了解得越多，当这件事情再次发生时，他从中获取的信息就越少。
怎么理解这一点呢？举个例子。
当一个人突然(第一次)对你说“我爱你”的时候，你的内心是非常激动的，甚至会出现傻哭、流泪、失眠和抓狂的现象，总结为“信息量太大一时无法接受”。当这个人第二次、第三次、第一万次说“我爱你”的时候，你的表现就会逐渐趋于平静，甚至说“好啦好啦，知道你爱我啦”。
发生次数越多的事件，它发生的概率越高。因此，当一件事情发生的概率越高，我们从中获取的信息就越少。也就是说，一个事件所包含的信息量和它的概率的倒数呈正相关。
假如以 b 进制的数 $x_b$ 来表示 e 事件的信息量，其发生的概率为 $p_e$，则:

$$x_b = log_b(f(\frac{1}{p_e}))$$

其中，函数 $f(\frac{1}{p_e})$ 为一个 $p_e$ 的倒数的增函数(正相关)。
如果我们简化 f 函数为 $f(x) = x$，则在信息都以二进制的比特来衡量的计算机系统中，上述公式可以表示为:

$$x = log_2(\frac{1}{p_e})$$

1.2 设定二：平均来说，1 比特信息(info)至少要 1 bit 消息(message)来保存

假如我们在抛硬币，用 0000000001 代表抛正面，0000000000 代表抛反面。正面和反面的概率都是 0.5，那根据我们上面的公式，每次抛硬币的结果所包含的信息量为 $log_2(\frac{1}{0.5}) = log_2(2) = 1$ 比特。但是我们用了 10 个比特来表示结果，平均每比特消息包含的信息量为 0.1 比特。这种情况下是可以无损压缩的。
如果我们用 1 代表正面，0 代表反面，那么我们正好用 1 比特来表示结果，平均每比特包含的消息量为 1 比特。这时候，我们就不能再压缩了。
假如我们把一条消息看做一个由各种符号(symbol)组成的序列，每个符号的概率为 $p_s$，则每个符号的信息量为 $log_2(\frac{1}{p_s})$。则压缩每个符号需要至少 $log_2(\frac{1}{p_s})$ 个比特。

二. ANS 基本思路：一个数字保存所有信息

ANS 的基本思路是用一个数字 x 来保存所有的信息。
x 也可以看成是一个比特序列，有 $log_2(x)$ 个比特。
而作为一个完美的压缩算法，我们设定 x 刚好包含 $log_2(x)$ 比特的信息量，也就是 1 比特位保存 1 比特信息。
假如 $p = \frac{1}{x}$, 则 $log_2(x) = log_2(\frac{1}{p})$。 根据上述设定一，x 包含的信息量与“从 x 个物体中选取 1 个物体”这一行为的信息量相同。
因此，我们有了以下对等关系:

x == $log_2(x)$ bits info == choosing One thing from x things

我们把消息看成一个符号的序列，并定义压缩函数 $x' = Encoding(x, s)$。$s$ 为即将压缩的符号，$x'$为压缩后的新的 $x$ 值，里面同时保存了 $x$ 和 $s$ 的信息。解压函数则为 $Decoding(x') = (x, s)$。那 ANS 是如何实现压缩和解压函数的呢？

首先我们已知，被压缩的符号 $s$ 的概率为 $p_s$，其所包含的信息量为 $log_2(\frac{1}{p_s})$。$x\prime$ 中包含的信息量为原本 $x$ 的信息量加上 $s$ 的信息量，也就是 $log_2(x) + log_2(\frac{1}{p_s}) = log_2(\frac{x}{p_s})$信息量。
如果 ANS 是接近完美的压缩算法，则 $x'$ 包含的信息量大约为 $log_2(x')$。也就是说 $log_2(x') \approx log_2(\frac{x}{p_s})$，即 $x' \approx \frac{x}{p_s}$。这中间的约等于越接近，则压缩的效率越好。

凭 $x' \approx \frac{x}{p_s}$ 线索似乎能够实现压缩函数，但怎么找到解压函数？
我们接着再看 ANS 是如何发挥它的想象力的。
我们已知 $x$ 包含 $log_2(x)$ 比特信息，可以看做“从 x 选 1”。那么，这个 “x 选 1” 到底是 x 个什么，选取 1 个什么呢？
因为 $x' \approx \frac{x}{p_s}$, 所以 $x \approx x' * {p_s}$。
因为 $p_s$ 为符号 $s$ 的概率，所以 ANS 把 $x\prime$ 看成是 “$x'$ 个符号”，而 $x$ 为“符号 $s$ 的个数”。符号 $s$ 不止一个，为了具化到选取某“一个”的行为上，ANS 把 $s$ 定义为“第 $x$ 个”符号。
也就是说，我们把 $x'$ 划分为 $x'$ 个区间，由每种符号按概率来分布。由于每种符号的概率是已知的，所以每种符号的分布方式也就是固定的了。也就是说，对于任意 $x'$, 它对应的符号 $s$ 和之前 $s$ 出现的个数($x$) 都是已知的了。
这样，我们就实现了 $x'$ 里面同时包含 $x$ 和 $s$ 的信息的要求: $x'$ 为第 $x$ 个 $s$ 出现时的 $x$ 的值。

三. ANS 的实现之 uABS：为二进制设计

上面讲到了 ANS 是如何用一个自然数 $x$ 和一个符号概率表来实现在一个 $x$ 中同时存储之前的所有信息和被压缩的符号 $s$ 的信息的。但是，我们还没提到具体的实现。
在计算机中的任何数据都以二进制形式存在。所以最直接的一个实现就是把消息看做一个 0 和 1 两种符号的序列。这种针对两种符号进行压缩的 ANS 实现被称之为 Uniform Binary Asymmetric System (uABS)。
uABS 中，$x$ 的初始值是 1，包含 $log_2(1) = 0$ 比特的信息。
假定 1 的概率是 $\frac{3}{4}$, 0 的概率是 $\frac{1}{4}$。我们可以画这么一个 x 和 0\1 两种符号的分布表。

x	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
s=0	0				1				2				3				4
s=1		0	1	2		3	4	5		6	7	8		9	10	11		12	13

假如我们要压缩的消息为 "0111", 则:

• $x$ 初始值为 1
• 压缩入 $0$, $x$ 成为第 1($x$) 个 $0$ 出现时对应的值，即 $4$
• 压缩入 1, $x$ 成为第 4($x$) 个 $1$ 出现时对应的值，即 $6$
• 压缩入 1, $x$ 成为第 6($x$) 个 $1$ 出现时对应的值，即 $9$
• 压缩入 1, $x$ 成为第 9($x$) 个 $1$ 出现时对应的值，即 $13$
• $x$ 最终为 $13$, 即 0b1101

至于如何找到这样的压缩和解压方程，里面涉及比较多的数学过程，我就不再细述，以下是结果。
假定 s 为 0 或者 1，$p_1$ 为 1 出现的概率。
压缩过程为:

$$\begin{aligned} x' = Encoding(x, s) = \begin{cases} \lfloor \frac{x}{1-p_1} \rfloor, & s = 0\\ \lceil \frac{x+1}{p_1} \rceil - 1, & s = 1\\ \end{cases} \end{aligned}$$

解压过程为：

$$\begin{aligned} s &= \lfloor (x + 1)p_1 \rfloor - \lfloor xp_1 \rfloor\\ \\ x &=\begin{cases} x - \lfloor(xp_1)\rfloor, &s=0\\ \lfloor xp_1 \rfloor, &s = 1\\ \end{cases} \end{aligned}$$

四. ANS 的实现之 rANS：为字符表设计

rANS 可以压缩 Range Variants, 即一系列符号，而不仅仅只是 0 和 1 两个符号。
一般来说，rANS 先选定一个范围 $2^n$, 这个范围不小于要压缩的符号的波动范围(range)。
就像我们在上面以一个表格来具化 s 的分布方式一样，rANS 如何根据 s 的频率抽象 s 的分布方式呢？
对于每个符号 s，使用 CDF(Cumulative Distribution Function) 计算其累加频次:

$CDF[s] = \sum_{i<s}f[i] = f[0] + ... + f[s-1]$

然后对于 $[0, 2^n-1]$ 范围内的任何一个数 y, 使用以下逻辑判断 y 解析为哪个符号:

$CDF[s] <= y < CDF[s+1]: symbol(y) = s$

于是压缩过程为：

$x' = (\lfloor \frac{x}{f[s]} \rfloor << n) + (x \% f[s]) + CDF[s]$

解压过程为：

$$\begin{aligned} mask &= 2^n -1\\ s &= symbol(x' \And mask)\\ x &= f[s] * (x' >> n) + (x' \& mask) – CDF[s]\\ \end{aligned}$$

详细的数学证明过程非我所长，就不再深入研究了。

五. 总结

ANS 算法基于香农熵理论“信息程度与熵呈正相关”以及“平均 1 比特信息要 1 比特消息存储”，推理出 $x' \approx \frac{x}{p_s}$ 的约等式。再根据“x 比特信息量等于从 x 物体选 1 的信息量” 联想到 “x’ 为 第 x 个 s”，从而依靠概率分布表实现在一个数字 x’ 中同时保存 x 和 s 的信息。因此，它有 AC 算法的压缩率，但是比它快(只需要一个 x 记录所有信息，AC 要两个)。它也有 Huffman 的速度，但是比它压缩率高(它可能以小数点个比特来记录新信息，Huffman 必须是整数个)。