💻 computer science

Efficiency of ANS Entropy Encoders

本文通过证明其冗余度实际上为 $O(\sigma/n)$ ，推翻了关于表格化非对称数字系统（tANS）冗余度为 $O(\sigma/n^2)$ 的猜想，从而确立了其最优冗余界限，同时还提出并分析了一种具有固定精度的更快的 rANS 变体。

原作者： Dmitry Kosolobov

发布于 2026-02-04

📖 1 分钟阅读☕ 轻松阅读

原作者： Dmitry Kosolobov

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

大局观：如何高效地打包行李箱

想象一下，你正试图打包一个行李箱（你的数据）并将其寄往世界各地。你希望行李箱尽可能小，以节省运费（带宽/存储）。

在数据压缩领域，有两种主要的打包方式：

哈夫曼编码 (Huffman Coding)： 就像按衣物类型进行分类，把所有衬衫装进一个袋子，裤子装进另一个袋子。它很快，但有时会在袋子里留下一些空隙。
算术编码 (Arithmetic Coding)： 就像把每一件物品都挤进真空密封袋。它极其高效（体积极小），但打包和拆解的过程非常耗时。

ANS (非对称数值系统) 是由 Jarek Duda 发明的一种新方法，它声称是“两者的结合”。它能像算术编码那样紧凑地压缩数据，同时像哈夫曼编码一样快速打包。它已成为现代文件格式（如图像和视频）的标准。

问题所在：“剩余”空间

虽然大家都知道 ANS 既快又好，但没有人 100% 确定它与理论上的完美极限相比，究竟留下了多少“浪费的空间”（冗余）。

把冗余想象成行李箱中多余的空气。

旧的猜测： 一些专家认为浪费的空间微乎其微，几乎为零。
作者的发现： Kosolobov 证明了浪费的空间实际上比之前认为的要大。它不是微乎其微的；它是一个小但可察觉的量，取决于你有多少种不同的物品类型（符号）。

主要研究结果（“TANS”变体）

本文重点讨论了最流行的 ANS 版本，称为 tANS（表格化 ANS）。

1. 上界 (最坏情况)
Kosolobov 计算了 tANS 最终会使用的最大额外空间。

公式： 额外空间大约与不同符号类型 ( $\sigma$ ) 除以总项目数 ( $n$ ) 成正比。
类比： 假设你有一个装有 1,000 件物品的行李箱。如果你有 10 种不同类型的物品，那么“浪费的空气”很少。但如果你有 500 种不同类型的物品，浪费的空气就会变得很显著。
结论： 本文证明了浪费约为每个符号 $O(\sigma/n)$ 比特。这是一个“紧凑”的界限，意味着它是最准确的估计。

2. 下界 (“你无法做得更好”的证明)
作者不仅猜测了最大值，还证明了你无法做得更好。

实验： 他创建了一个特定的、棘手的序列数据（就像一个装满了特定交替物品的行李箱），这会迫使 ANS 编码器留下特定数量的额外空间。
结果： 他表明，对于某些数据模式，浪费至少是 $\sigma/4$ 比特。
意义： 这反驳了 ANS 发明者 (Duda) 的一个猜测，即浪费可以小到 $O(\sigma/n^2)$ 。Kosolobov 说：“抱歉，那太乐观了。这里有证据表明，实际的浪费要大得多。”

3. “R”因子 (初始设置成本)
始终会添加到行李箱中的固定成本 $r$ 比特（其中 $n = 2^r$ ），无论数据是什么。

类比： 这就像行李箱本身的重量。即使你里面装的是空的，行李箱本身也是有重量的。论文承认这是由于系统启动方式而产生的不可避免的“人工产物”，但它是一个固定成本，而不是每个项目的成本。

第二项贡献：一种新的“固定精度”rANS

本文还介绍了一种新的 ANS 变体，称为 具有固定精度的 rANS。

标准 rANS 的问题：
标准 rANS 非常出色，因为它不需要巨大的查找表（节省内存），这对于自适应系统（即数据随过程变化而变化）非常完美。然而，它有一个缓慢的步骤：除法。

类比： 想象你在打包，每当你添加一件物品，你都必须停下来做一个复杂的数学题（除法）来确定它应该放在哪里。这会减慢你的速度。

新的解决方案：
Kosolobov 创建了一个版本，简化了“数学题”。

工作原理： 他设定了一个规则（参数 $k$ ），保证除法的结果始终落在特定的、很小的范围内。
益处： 因为结果是可预测的，计算机不需要进行缓慢、沉重的除法运算。它可以利用更快速、更简单的技巧（如位移操作）来获得答案。
权衡：
- 编码 (打包)： 它比使用除法的标准 rANS 快，但比使用预计算常数的“超快”rANS 稍慢。
- 解码 (拆解)： 它比标准版本慢。
何时使用： 如果你正在构建一个需要根据不断变化的数据进行实时自适应的系统（此时无法预先计算常量），并且在打包阶段对速度有极高要求，那么这个版本非常有用。

论文主张总结

我们修正了数学： 我们现在确切知道流行的 tANS 编码器会留下多少“浪费的空间”。它比人们认为的要多 ( $O(\sigma/n)$ )，我们也证明了你无法将其做得更小。
我们揭穿了一个神话： 对于标准的初始化方法，浪费可以小到 $O(\sigma/n^2)$ 这一观点是错误的。
我们制造了一个新工具： 我们创建了一个新的 rANS 版本，可以避免缓慢的除法运算，从而在特定的自适应场景下更快，尽管这会在解码期间带来轻微的速度损失。

这篇论文是一项“理论性的管道工程”：它测量管道、寻找泄漏，并建议了一种新的阀门设计，确保我们理解这种强大的压缩技术的极限。

技术摘要：ANS 熵编码器的效率

问题陈述
由 Duda 于 2009 年提出的不对称数字系统（ANS）已成为一种主流的熵编码器类别，它在提供与算术编码相当的压缩率的同时，具备哈夫曼编码的速度。尽管其在现代压缩器和媒体格式中得到了广泛应用，但其冗余度（即编码后的比特长度与信息论下界之间的差异）的精确渐近行为此前尚未得到充分理解。以往的分析依赖于对数据源的概率假设，或提供了非严谨的界限。具体而言，Duda 曾推测，在适当的初始化条件下，流行的表驱动 ANS（tANS）变体的冗余度可以低至每个符号 $O(\sigma/n^2)$ 比特。本文旨在不依赖概率假设，而是基于经验熵，为 tANS 建立紧凑的最坏情况渐近界限，并分析一种新型的范围 ANS（rANS）变体。

方法论
作者通过将 ANS 编码器建模为对正整数状态 $w$ 的操作来分析它们，该状态随着符号的编码而增长。分析重点关注两种主要变体：

表驱动 ANS (tANS/FSE)： 该变体使用预计算表（置换/shuffling）来均匀分布符号，旨在最小化冗余度。作者分析了 Duda 提出的“精确初始化”方法（以及一个简化版本），该方法利用优先队列在编码表中分布符号出现次数。
范围 ANS (rANS)： 该变体避免了大型表格，但通常在编码过程中需要昂贵的整数除法运算。

本文采用确定性的最坏情况分析，研究每个符号的比特增长 $\log w_{i+1} - \log w_i$ 。通过对这些增量求和，作者推导出了上界；通过构建使编码器行为并非最优的特定对抗序列，推导出了下界。分析过程明确考虑了“r-bit 伪影”（初始状态大小）以及由置换机制引入的开销。

核心贡献与结果

tANS 冗余度的紧确界限：
本文证明了使用 Duda 精确初始化的 tANS 冗余度为 $O(\sigma/n)$ 比特/符号，反驳了其冗余度可达 $O(\sigma/n^2)$ 的猜想。
- 上界： 对于长度为 $n=2^r$ 且符号频率为 $f_a$ 的序列，总编码长度受限于：
  $\sum_{a} f_a \log \frac{n}{f_a} + \sigma \log e + r$
  这得出每个符号的冗余度约为 $\frac{\sigma}{n} \log e + \frac{r}{n}$ 。
- 下界： 作者构造了一个特定的序列（其中 $\sigma \approx n/3$ ，符号频率为 3 或 1），证明了可以达到 $\frac{\sigma-1}{4} + r - 2$ 比特的冗余度。这证实了对于任何仅基于已知频率（而不处理序列本身）生成表的初始化方法， $\Omega(\sigma)$ 加性项是必要的。
具有固定精度的 rANS：
本文引入了一种由整数 $k \ge 1$ 参数化的新型 rANS 变体，称为“具有固定精度的 rANS”。
- 机制： 该变体将整数除法 $\lfloor x/f_a \rfloor$ 的结果限制在 $[2^k, 2^{k+1})$ 范围内。这一约束使得除法可以通过更快速的无分支算术和位运算来执行（避免了缓慢的显式除法指令），同时保持 rANS 的特性。
- 冗余度界限： 该变体的冗余度受限于：
  $\frac{n \log e}{2^{k-1}} + r + k$
  这代表了一种权衡：增加 $k$ 会降低冗余度，但可能会影响除法优化的速度。
实验验证：
作者实现了具有固定精度（ $k=3$ ）的 rANS，并将其与标准 rANS（使用显式除法）以及快速 rANS 变体（使用乘法/移位结合预计算常数）进行了对比。
- 结果： $k=3$ 的变体编码速度快于带有显式除法的标准 rANS，但慢于快速 rANS 变体。解码速度始终慢于两者。 $k=3$ 变体的压缩率与标准 rANS 相当。作者认为该变体适用于无法预计算除法优化常数的自适应场景。

意义与主张
本文的主要意义在于提供了关于 tANS 冗余度的第一个严谨的最坏情况渐近界限，修正了对其效率极限的理论理解。通过证明其冗余度为 $\Theta(\sigma/n)$ 而非 $O(\sigma/n^2)$ ，作者阐明了使用表驱动 ANS 的基本成本。

此外，本文强调了 $r$ -bit 冗余（初始状态的伪影）和 $\sigma$ 项是标准初始化方法的固有属性。作者认为，虽然分析序列本身的方法可以避免这种效应，但由于性能成本，这些方法在实践中往往难以实现。

“具有固定精度的 rANS”的引入为无法预计算除法优化常数的自适应压缩场景提供了一个实用的解决方案，在牺牲部分解码速度的前提下实现了比标准 rANS 更快的编码速度。

开放问题
论文最后提出了几个开放问题：

构建一种真正的 FIFO（队列式）ANS 编码器，使其性能能够匹配当前的 LIFO（栈式）变体，以更好地支持自适应编码。
开发一种快速、简单的 tANS 初始化方法，使其在不引入优先队列和浮点运算开销的情况下，仍能提供 Duda 精确初始化的理论保证。
确定 tANS 冗余度项的紧确常数，因为目前的上下界并不一致。
研究频率表的实际编码器，因为在小数据块场景下，频率表往往占据压缩数据的大部分体积，这可能使得哈夫曼编码在特定语境下比 ANS 更具优势。

大局观：如何高效地打包行李箱

问题所在：“剩余”空间

主要研究结果（“TANS”变体）

第二项贡献：一种新的“固定精度”rANS

论文主张总结

类似论文