算术编码

算术编码是一种无损数据压缩方法，利用概率模型将符号序列转换为紧凑的比特流。它不为每个符号分配独立的码字，而是通过逐步缩小的数值区间来表示整个序列。算术编码将符号概率估计与编码这两项任务分离，使同一编码器能够配合不同的统计模型使用。(www2.isye.gatech.edu)

编码与解码

在理想化的构造中，编码从半开区间 ([0,1)) 开始。对于每个符号，按照模型的概率分布将当前区间按比例划分为若干子区间，并将该符号对应的子区间作为新的当前区间。(arxiv.org)

设当前区间为 ([L,U))，(C(s)) 为按约定顺序排在符号 (s) 之前的所有符号的累积概率。若 (s) 的概率为 (p(s))，则区间更新公式为

[ L'=L+(U-L)C(s),\qquad U'=L+(U-L)\bigl(C(s)+p(s)\bigr). ]

处理完全部符号后，编码器输出足够多的二进制位，以确定最终区间内的一个数值。解码器重建各步的区间划分，并在每一步根据包含编码值的子区间确定相应符号。编码器与解码器必须在概率、符号顺序、数值运算规则和消息终止方式上保持一致。(www2.isye.gatech.edu)

示例演算

考虑一个固定模型，其中 (p(A)=1/2)、(p(B)=1/4)、(p(C)=1/4)，符号顺序为 (A,B,C)。对消息 AB 应用区间更新规则，结果如下：

二进制小数 (0.0101_2=5/16) 位于最终区间内。其对应的二进制前缀区间 ([5/16,6/16)) 也完全包含在最终区间中。这些计算说明，二进制表示可以在不为各符号分配独立码字的情况下区分消息。

解码器仍须知道消息包含两个符号，或者遇到显式编码的消息结束符；仅凭编码值本身，无法确定何时应停止解码。(www2.isye.gatech.edu)

压缩效率

理想情况下，最终区间的宽度等于模型赋予该序列的概率 (P(x))。因此，所需的描述长度近似等于该序列的自信息，

[ -\log_2 P(x), ]

以比特为单位，此外还需计入消息终止和实现带来的额外开销。对于建模准确的独立信源，随着消息长度增加，平均码率趋近于其信息熵，这与信源编码定理一致。(arxiv.org)

与逐符号进行的霍夫曼编码不同，算术编码不要求每个符号都独立占用整数个比特。因此，即使高概率符号的平均比特贡献远小于一个比特，它仍能接近理想码率。这里指的是符号在整个序列中的平均贡献，并非物理上存在不足一个的比特。(www2.isye.gatech.edu)

概率模型

静态模型在一条消息或一个数据块内使用固定概率。自适应模型则随着符号的处理不断更新概率估计；解码器利用已恢复的符号进行相同的更新，因此无需传输每次更新的结果。依赖上下文的模型根据先前的符号或编码与解码双方均可获得的其他信息估计概率。压缩效果取决于模型预测数据的准确程度，而不只是编码机制本身。(www2.isye.gatech.edu)

实际实现

实际实现通常使用位宽有限的整数寄存器，而非无限精度的小数。重归一化在编码过程中对区间进行缩放，并输出已经确定的数位；延迟输出比特或进位处理机制则用于处理尚未确定的数位。要确保正确解码，必须采用一致的舍入规则，并保证各子区间的宽度不为零。(arxiv.org)

实现技术包括低精度区间计算，以及用于减少高成本算术运算的移位与加法操作。多符号编码器还需要进行累积频数查找和更新，因此数据结构的选择十分重要。编码、建模和概率估计可以作为独立组件实现。(researchcommons.waikato.ac.nz)

发展与应用

伊恩·H. 威滕、拉德福德·M. 尼尔和约翰·G. 克利里于1987年发表了一种具有广泛影响的实现。随后，阿利斯泰尔·莫法特、尼尔和威滕在1998年的《算术编码再探》（Arithmetic Coding Revisited）中介绍了多项改进，包括支持更宽的概率范围，以及降低算术运算成本。(doi.org)

算术编码也应用于多媒体压缩。H.264/AVC 标准规定的基于上下文的自适应二进制算术编码（CABAC）利用自适应概率上下文对二进制判定结果进行编码。即使整个视频压缩流程包含有损操作，算术编码阶段本身仍是无损的。(itu.int)

参考来源

1. Arithmetic Coding for Data Compressionwww2.isye.gatech.edu
2. Introduction to Arithmetic Coding -- Theory and Practicearxiv.org
3. Arithmetic coding revisitedresearchcommons.waikato.ac.nz
4. ITU-T Rec. H.264 (08/2024): Advanced video coding for generic audiovisual servicesitu.int
5. ITU-T Rec. H.264 (06/2019): Advanced video coding for generic audiovisual servicesitu.int