技术

ANS 熵编码原理:为什么 Zstandard/Brotli 都在用它替代算术编码

📅 2026-08-31 · ✍️ 闪压资讯 · ⏱ 4 分钟阅读

为什么需要"另一种"熵编码

聊压缩原理绕不开熵编码。霍夫曼和算术编码的核心都是"高频符号分配短码、低频符号分配长码",让平均码长逼近信息熵。霍夫曼实现简单,但码长必须取整,碰到概率分布极不均匀时会浪费比特;算术编码把整条消息映射成 0 到 1 区间的一个小数,理论上能贴到熵,却需要高精度乘法,还背着二十世纪末的专利包袱。

有没有办法既保留算术编码"逼近熵"的能力,又只做整数运算、还避开专利?ANS(Asymmetric Numeral Systems,不对称数系)登场了。它由 Jarek Duda 提出,核心想法是:把"压缩"理解为"在更大的数系里找一个小数表示",而不是"给每个符号分配码字"。

ANS 的核心思想:把消息塞进一个大整数

ANS 的目标是:把一串符号塞进一个整数 x,只要 x 唯一,就能反解出原始序列。它的构造方式是让"概率越高的符号"占用的字节越少。

以 rANS(range ANS)为例,维护一个状态 x,对每个到来的符号 s,根据其概率在某个区间做一次"重映射":若符号概率是 p,状态数被缩放成原来的 1/p 倍。这意味着高概率符号把 x 缩得小,低概率符号把 x 撑得大。最终的整数 x 加上解码所需的起点信息,就是压缩后的数据。

编码可概括为 x' = (x / p) * n + (x mod p) + base,其中 n 是符号表大小,base 是该符号在概率表里的偏移,解码是其逆运算。整个过程只涉及整数除法和取模,不需要浮点,也不需要存一棵巨大的码树。

tANS:把 ANS 装进 CPU 友好的表

rANS 的瓶颈是每次编码都要做整数除法,在现代压缩器眼里仍是热点。tANS(tabled ANS)把状态转移预先算成一张表,编码时直接查表,牺牲一点理论最优性换取吞吐。

Zstandard 的 FSE(Finite State Entropy)模块就是 tANS:把状态空间切成若干区间,每个区间对应一张"用当前状态和输入符号换下一个状态"的表,编码时 next_state = table[symbol][state_in_bucket],解码反向查表。这种设计让熵编码阶段可以流水线化、SIMD 向量化,在多核 CPU 上的吞吐再上一个台阶。

为什么 ANS 成了现代压缩器的默认选项

DEFLATE 用的是霍夫曼,这是 ZIP、gzip、PNG 的标配;新一代 Zstandard、Brotli、Zopfli 的熵编码后端都换成了 ANS。原因有几个共同点。

性能上,ANS 的解码吞吐通常比算术编码快数倍,因为不需要乘以极小的小数,也不需要维护比特级累加器。对解压缩速度敏感的场景(网页加载、本地解包),这点非常关键。

码率上,ANS 在大状态空间下能逼近真熵,几乎和算术编码持平;霍夫曼在小概率符号上要付出整数码长代价。在文本、源代码这种字符分布偏斜的数据上,ANS 比霍夫曼多省的几个百分点,在大量小文件归档里就是实实在在的存储与带宽。

工程上,ANS 没有专利纠纷,实现全部公开,集成进商业产品时无需顾虑;同时它和字典编码天然合拍——Zstandard 的流水线是先用 LZ77 把重复片段抽成"字面量 + 回指对"序列,再交给 FSE 做熵编码。字面量和回指距离都各有偏斜的概率分布,正好是 tANS 最擅长吃的输入。

对普通压缩软件用户的意义

ANS 是底层零件,普通用户看不见它。但当你在闪压里压一份文本、源代码或日志归档时,后端大概率跑的就是 ANS 或它的工程化变体。不需要懂它怎么算,只需要知道:主流压缩工具背后的"最后一步"基本都被 ANS 接管了。

这也是为什么同级别的压缩器这几年体积差距越来越小、速度差距却越拉越大——大家都用 ANS 之后,压缩率几乎贴近,差别更多体现在吞吐和内存占用上。理解这一点,再看各种"压缩速度排行榜""压缩率横评",就有了底层的判断框架。

为什么需要"另一种"熵编码

ANS 的核心思想:把消息塞进一个大整数

tANS:把 ANS 装进 CPU 友好的表

为什么 ANS 成了现代压缩器的默认选项

对普通压缩软件用户的意义

相关阅读