> 算术编码 | 分数位 | 最优 <
// 算术编码 - 使用分数比特接近信息熵极限的编码
接近最优
压缩效率接近理论上的信息熵极限。
分数位比特
根据符号概率使用分数位比特进行编码。
流式处理
可以在数据到达时逐步编码和解码。
>> 技术说明
算术编码的工作原理:
算术编码将整条消息表示为区间 [0,1) 内的一个数。每个符号根据自身概率不断收缩该区间。最终得到的区间再被编码为二进制小数，从而实现非常接近熵极限的压缩率。
编码过程示例:
文本: "AAB" 概率: A=0.67, B=0.33 1. 起始: [0, 1) 2. 'A': [0, 0.67) 3. 'A': [0, 0.45) 4. 'B': [0.30, 0.45) 输出: [0.30, 0.45) 区间内的任意数 二进制: 0.010011...
为什么选择算术编码:
- >更高的压缩比
- >接近信息熵极限
- >支持任意概率分布
- >用于 JPEG2000 / H.264 等标准
- >相关专利已到期（2024）
>> 常见问题
什么是算术编码？
算术编码是一种熵编码方式，会把一串符号转换为一个分数值。与只使用整比特的 Huffman 编码不同，算术编码可以为每个符号分配分数比特。
它为什么比 Huffman 更好？
算术编码可以实现任意接近熵极限的压缩，而 Huffman 编码受限于每个符号必须使用整数个比特。对于概率分布高度不均匀的场景，算术编码的效果通常好得多。
精度参数是什么意思？
精度控制内部计算使用的比特数。更高的精度可以编码更长的消息，但会占用更多内存。对于短文本，一般 16 位精度就足够。
算术编码常用于哪些地方？
算术编码广泛应用于 H.264/H.265 视频、JPEG2000 图像以及 ZIP 的 DEFLATE64 模式等现代压缩标准。过去曾受专利限制，但关键专利已经到期。
// 计算示例
| Step | Symbol | low | high |
|---|---|---|---|
| 0 | — | 0 | 1 |
| 1 | A | 0 | 0.5 |
| 2 | B | 0.25 | 0.375 |
| 3 | C | 0.34375 | 0.375 |
// 代码示例
Model P(A)=0.5 P(B)=0.25 P(C)=0.25 -> A:[0,0.5) B:[0.5,0.75) C:[0.75,1)
Update width = high - low
high = low + width * cum_high(symbol)
low = low + width * cum_low(symbol)
Output any value in [0.34375, 0.375) e.g. 0.34375 = 0.01011b (5 bits = 1 + 2 + 2)
Entropy -log2 P(A) - log2 P(B) - log2 P(C) = 1 + 2 + 2 = 5 bits
>> 更多问题
问：为什么算术编码通常比霍夫曼编码更好？
答：霍夫曼为每个符号分配整数个比特（至少 1 位）。算术编码把整条消息编码为 [0, 1) 内的一个分数，接近熵极限，即使概率超过 50% 的符号在霍夫曼下也要占 1 位。
问：ABC 区间示例是怎么算的？
答：设 A=0.5、B=0.25、C=0.25，每个符号都会缩小区间：[0,1) → [0,0.5) → [0.25, 0.375) → [0.34375, 0.375)。区间内任一数，如二进制 0.01011（=0.34375），就能用 5 位编码“ABC”，恰为熵。
问：算术编码用在哪里？
答：用于 H.264/HEVC 的 CABAC、JPEG 2000 与 JBIG2 的 MQ 编码器，以及 range coding（AV1）和 ANS（zstd、JPEG XL）等变体。早期专利曾阻碍普及，现在大多已过期。