算术编码

1 基本原理

算术编码是一种无损数据压缩算法，它将整个待编码的消息视为一个[0,1)区间内的实数（或二进制小数），通过根据符号概率分布不断细分区间来实现编码。与霍夫曼编码等将每个符号映射为固定长度码字的方法不同，算术编码能够为整个消息分配一个接近理论熵极限的码长，特别适用于符号概率分布不均匀或存在高阶依赖性的场景。其核心思想是利用累积概率递推地更新当前区间，最终输出的实数（或对应的二进制序列）即为压缩结果。解码时则通过相同的概率模型反向恢复出原始符号序列。

1.1 概率模型与符号区间

算术编码要求预先为每个可能的符号定义其在[0,1)区间上对应的子区间，子区间的长度与该符号的概率成正比。例如，若符号A的概率为0.6，符号B的概率为0.4，则可约定A对应[0, 0.6)，B对应[0.6, 1.0)。这些子区间互不重叠，且覆盖整个[0,1)区间。实际实现中，概率分布可以是静态的（固定不变），也可以是自适应的（随已编码符号动态调整）。

1.2 递归区间划分过程

编码开始时，当前区间初始化为[0,1)。每读入一个符号，就在当前区间内取出该符号对应的子区间，并将该子区间作为新的当前区间。重复此过程，随着符号的逐个处理，区间不断缩小，其长度等于所有已编码符号概率的乘积。最终得到的区间无论选择其中的哪个实数，都能唯一解码出原始符号序列。

1.3 终止与码字输出

当所有符号处理完毕，编码器从最终区间中选取一个足够短的小数（通常是区间下界），并将其转换为二进制表示输出。为了确保解码器能够明确终止，通常需要在消息末尾添加一个特殊的终止符号（EOF），或约定输出比特数的计算方式。输出码字的长度理论上可以无限接近消息的熵。

2 编码与解码算法

2.1 编码流程

2.1.1 初始化与符号处理

编码器初始化当前区间为[low, high) = [0, 1)。对于每个待编码的符号，根据概率模型查找该符号对应的子区间[low_sym, high_sym)，然后按以下公式更新区间：

• 新的区间长度 = (high - low) × (high_sym - low_sym)
• 新的low = low + (high - low) × low_sym
• 新的high = low + 新区间长度

2.1.2 区间缩放与溢出处理

在实际的有限精度实现中，区间上下界以整数表示，区间长度会随编码进程不断缩小。当区间长度缩小到某一阈值以下时，需要执行重归一化：将区间成倍放大，同时输出高位比特，以防止精度溢出。常见的做法是当区间完全落入[0, 0.5)或[0.5, 1)时，输出对应比特并放大区间；当区间横跨0.5时，则采用进位锁定机制，暂缓输出直至区间明确。

2.2 解码流程

2.2.1 从码值恢复符号

解码器维护一个码值（tag），该码值为编码器输出的实数（或二进制流中已读入的部分）。解码时，解码器通过比较码值落在当前区间的哪个符号子区间内，来确定下一个符号。具体地，设当前区间为[low, high)，计算tag相对当前区间的位置：pos = (tag - low) / (high - low)，然后查找pos落在哪个符号的累积概率区间中。每确定一个符号后，解码器按与编码器完全相同的方式更新区间，并重复以上步骤。

2.2.2 自适应概率更新

若采用自适应模型，解码器在每次输出一个符号后，立即更新该符号的计数和概率分布，使得后续符号的区间划分与编码器保持严格同步。这种“边解码边学习”的机制使得同一模型无需事先传输，只需在编解码两端使用相同的初始统计和方法即可。

3 实现细节与优化

3.1 有限精度处理

3.1.1 整数算术编码

为避免浮点数运算误差并提高效率，实际实现使用固定精度的整数（如32位无符号整数）表示区间。将[0,1)映射为一个整数范围，例如[0, 2^32)。区间上下界使用整数加减乘除运算，概率值用整数频数表示。通过控制总频数的幂次（如使用2的整数次幂），可以用移位操作替代部分除法，提升速度。

3.1.2 重归一化与进位控制

当整数区间缩小到[0, 2^31)（或某个阈值）以下时，触发重归一化：输出当前最高位比特，并将区间加倍。若区间横跨0.5的边界（即low < 2^31且high ≥ 2^31），则暂时不输出比特，而是记录一个“待定比特”并进入进位锁定状态，待后续区间明确后再决定进位。常见的处理方式是维护一个“未决比特计数器”，并在后续比特输出时进行“纠偏”。

3.2 模型选择

3.2.1 静态模型 vs 自适应模型

• 静态模型：编解码双方使用相同的固定概率表，适用于已知概率分布的场合（如某些特定文件格式）。优点是实现简单，无需传递模型信息，但需要事先统计或约定。
• 自适应模型：初始时假设所有符号等概率，每次编码/解码一个符号后，根据实际出现次数更新概率。无需提前传输概率表，适用于通用压缩工具（如算术编码版的gzip、H.264中的CABAC）。

3.2.2 上下文建模

为捕捉符号之间的相关性，算术编码常与上下文模型结合。例如，在图像压缩中，每个像素的概率不仅取决于其自身值，还取决于相邻已编码像素的状态。上下文模型将符号划分为若干“上下文”，每个上下文拥有独立的概率表，从而更精准地估计概率，提升压缩率。

4 应用领域

4.1 图像压缩（JPEG 2000、JBIG）

JPEG 2000标准采用二进制算术编码（EBCOT，带上下文建模）作为其核心熵编码器，相比JPEG的霍夫曼编码，在低比特率下能获得更好的压缩质量。JBIG（二值图像压缩标准）同样基于算术编码，专门用于传真和文档图像的无损压缩。

4.2 视频压缩（H.264/AVC、HEVC）

H.264/AVC和HEVC（H.265）标准中的CABAC（Context-Adaptive Binary Arithmetic Coding）模块就是算术编码的典型应用。CABAC结合二进制化、上下文建模和自适应概率更新，在视频编码中取得了非常高的压缩效率，成为现代视频编码的标准配置。

4.3 文本与数据存档

算术编码在通用数据压缩工具（如PAQ、ZPAQ系列）中被广泛使用，这些工具通过复杂的预测模型（如混合模型、神经网络）搭配算术编码，不断刷新无损压缩比赛（如Hutter Prize）的记录。此外，某些存档格式（如7z中的BZip2变体）也包含算术编码的选项。

5 优点与局限性

5.1 接近熵极限的压缩率

算术编码能够以几乎任意精度逼近信息熵，对于概率分布极不均匀（如一个符号概率99%，其余1%）的源，其优势尤其明显。相比之下，霍夫曼编码至少需要1比特/符号，而算术编码可以用小数比特表示高概率符号。理论上，算术编码可以达到任意接近熵的码率，属于最优熵编码之一。

5.2 计算复杂度与实现难度

算术编码的运算量高于霍夫曼编码，涉及多次乘除法和区间维护；特别是有限精度下的重归一化和进位控制逻辑较为繁琐。自适应模型在每处理一个符号后都需要更新概率表（可能包含除法或查表），对实时性要求高的场景需要精心优化。不过现代硬件（尤其是带有乘除法单元的CPU）已使算术编码的软实现足够快。

5.3 对错误传播的敏感性

算术编码是一种“无记忆”的流式编码：一旦码流中出现比特错误（例如传输过程中的失真），后续的所有解码都会完全错乱（因为区间划分依赖于历史结果）。这导致算术编码对信道错误极为敏感，不适合直接应用于有噪声的通信链路，通常需要搭配错误检测/纠正码或同步标记使用。

6 相关概念对比

6.1 算术编码 vs 霍夫曼编码

6.2 算术编码 vs 区间编码

区间编码（Range Encoding）是算术编码的一种变体，核心思想几乎相同，但在有限精度实现上略有差异。算术编码的传统重归一化机制有时会导致“进位传播”问题（多个比特等待进位），而区间编码通过维护一个“窗口”和不同的缩放策略，在不损失压缩率的前提下显著简化了进位控制。许多现代压缩库（如RANS、TANS即非对称数字系统）也借鉴了区间编码的思想。总体而言，区间编码与算术编码的关系属于“兄弟算法”，实际工程中常将二者混用称呼。

7 历史与发展

算术编码的概念最早可追溯到1948年香农（Shannon）的论文，他提出了用区间细分表示消息的设想，但未给出实用算法。1960年代，Elias等人给出了递归区间划分的数学描述。1970年代，Pasco、Rissanen和Langdon等人首次实现了有限精度的算术编码器，奠定了现代实现的基础。1980年代，Witten、Neal和Cleary发表了著名的《 Arithmetic Coding for Data Compression 》论文，并公开了参考实现，使算术编码进入实用阶段。此后，自适应模型、上下文建模等技术的引入使其成为图像、视频压缩标准（JPEG 2000、H.264/AVC）的核心组件。近年来，非对称数字系统（ANS）等改进方案结合算术编码的思想，在效率和实现简便性上取得了新的突破，应用于Facebook的Zstd压缩算法和Google的Draco网格压缩等现代工具中。