算术编码
概述
算术编码（Arithmetic Coding，1976）是一种数据压缩方法，不受"整数码长"约束，可以将整个消息编码为一个 [0,1) 区间内的实数，压缩率逼近 Shannon 极限到任意精度。
关键内容
与 Huffman 编码的对比
| 特性 | Huffman 编码 | 算术编码 |
|---|---|---|
| 最优性 | 整数码长下最优 | 趋近 Shannon 极限 |
| 实现复杂度 | 简单 | 较复杂 |
| 编码速度 | 快 | 较慢 |
| 压缩率差距 | ≤ 1 bit/符号 | < 0.01 bit/符号 |
| 专利问题 | 无（已过期） | 曾有专利限制 |
| 使用场景 | JPEG, DEFLATE | H.264, JPEG2000 |
核心思想
算术编码将整个消息映射到 [0,1) 区间内的一个子区间，子区间的大小等于该消息的概率。消息越长，区间越小，最终用一个足够精确的实数来表示整个消息。
优势
- 不受"每个符号码长必须是整数"的约束
- 对高概率符号可以用少于 1 bit 的"平均码长"
- 在符号概率不是 2 的负整数幂时，压缩率显著优于 Huffman 编码
来源
- raw/books/信息论/06_huffman_1952_minimum_redundancy_codes.md — Huffman (1952) 深度解析