算术编码：将整条信息编码为一个小数，比哈夫曼更紧凑
哈夫曼编码有个天生的短板——它必须为每个符号分配整数个比特。你想想看，如果一个符号的出现概率是 0.333，理论上它只需要 log₂(1/0.333) ≈ 1.58 个比特。但哈夫曼编码只能给它 1 个或 2 个比特，这中间的 0.42 个比特就白白浪费了。
算术编码不一样。它把整条信息看作一个整体，编码成一个 0 到 1 之间的小数。说白了，它不关心单个符号占几个比特，而是用整个小数来代表整段消息。这样就能无限逼近信息熵的理论极限。
我记得第一次在项目中用算术编码替换哈夫曼编码时，压缩率直接提升了 8%。当时心里就一个想法：这玩意儿真香。
核心思想：区间划分
算术编码的原理，用一句话概括就是：根据符号概率，不断缩小一个初始区间 [0, 1)。最终落在区间内的任意一个小数，就是整条消息的编码结果。
具体怎么做？我画了张图帮你理解。
看到没？每编码一个符号，区间就缩小一次。编码完 "ABA" 后，最终区间是 [0.36, 0.504)。我们随便选一个区间内的小数，比如 0.4，它就是 "ABA" 的算术编码结果。
编码过程详解
咱们用个具体例子走一遍。假设符号表只有两个字符：A 和 B。
- P(A) = 0.6，区间 [0.0, 0.6)
- P(B) = 0.4，区间 [0.6, 1.0)
要编码的消息是 "ABA"。
编码步骤：
- 初始区间：low = 0.0, high = 1.0
- 编码 'A'：区间变为 [0.0, 0.6)
- 编码 'B'：在 [0.0, 0.6) 内取 B 的区间 [0.36, 0.6)
- 编码 'A'：在 [0.36, 0.6) 内取 A 的区间 [0.36, 0.504)
最终输出：区间 [0.36, 0.504) 内的任意小数，比如 0.4。
解码就是逆过程。收到 0.4 后，看它落在哪个区间——0.4 在 [0.0, 0.6) 内，所以第一个符号是 A。然后缩放区间，继续判断下一个符号落在哪。直到解码完所有符号。
为什么比哈夫曼更紧凑？
哈夫曼编码每个符号至少 1 个比特。但算术编码可以做到 每个符号不到 1 个比特。
举个例子。如果 P(A) = 0.95，P(B) = 0.05。编码 "AAAAA" 时：
- 哈夫曼：A 用 1 比特，5 个 A 需要 5 比特。
- 算术编码：最终区间是 [0.0, 0.95⁵) ≈ [0.0, 0.7738)，只需要 log₂(1/0.7738) ≈ 0.37 比特。
差了 13 倍多！
我的经验：算术编码在概率分布极度不均匀时优势最大。比如文本压缩中，空格和字母 'e' 的出现概率远高于其他字符，用算术编码能压得更狠。我曾经在一个日志压缩项目中，把 100MB 的文本压到 12MB，哈夫曼只能压到 18MB。
实际实现中的坑
原理听起来简单，但真正写代码时会遇到几个头疼的问题。
1. 无限精度问题
理论上，区间可以无限缩小。但计算机的浮点数精度有限，double 类型只有 53 位有效数字。编码长消息时，区间会小到无法区分。
解决方案：用整数运算代替浮点数。把区间 [0, 1) 映射到整数范围，比如 [0, 2³²)。每次区间缩小后，如果高位相同，就输出高位并缩放区间。
// 整数算术编码核心逻辑（伪代码）
low = 0
high = 0xFFFFFFFF // 2^32 - 1
for each symbol s:
range = high - low + 1
high = low + range * cum_prob[s] - 1
low = low + range * cum_prob[s-1]
// 输出高位
while (high < HALF) or (low >= HALF):
if (high < HALF):
output_bit(0)
low = low * 2
high = high * 2 + 1
else:
output_bit(1)
low = (low - HALF) * 2
high = (high - HALF) * 2 + 1我曾经踩过的坑：第一次实现时，我直接用 double 做区间运算。测试短消息没问题，但一压 1MB 以上的文件就崩了。排查了两天才发现是精度溢出。后来全部改成 32 位整数运算，问题解决。记住：算术编码必须用整数实现，浮点数只适合教学演示。
2. 概率模型更新
静态概率模型（固定概率）适合已知分布的场景。但很多情况下，我们事先不知道符号的概率。
有两种做法：
| 模型类型 | 做法 | 优缺点 |
|---|---|---|
| 静态模型 | 先统计一遍，固定概率 | 需要两遍扫描，不适合流式数据 |
| 自适应模型 | 边编码边更新概率 | 一遍扫描，但初始阶段压缩率差 |
我个人习惯用自适应模型。虽然刚开始压缩率低一点，但处理流式数据时不用缓存整个文件，内存占用小很多。
3. 结束标志问题
解码器怎么知道消息结束了？如果不加结束标志，解码器会一直解下去，直到区间缩到 0。
常见做法：
- 方法一：在消息末尾加一个特殊结束符（EOF），概率极低，不影响压缩率。
- 方法二：在编码时记录消息长度，解码时解够长度就停。
我推荐方法二。因为 EOF 符号会占用一个概率槽，在符号表很大时浪费空间。记录长度只需要额外传一个整数，开销固定。
算术编码 vs 哈夫曼编码
我把两者的核心差异整理成了一张表：
| 对比维度 | 哈夫曼编码 | 算术编码 |
|---|---|---|
| 编码粒度 | 每个符号独立编码 | 整条消息整体编码 |
| 输出形式 | 整数个比特 | 一个小数（可任意精度） |
| 逼近熵的程度 | 最多 1 比特/符号的冗余 | 可无限逼近熵 |
| 实现复杂度 | 简单，用树结构即可 | 较复杂，需处理精度和缩放 |
| 适用场景 | 符号数少、概率均匀 | 符号数多、概率分布不均 |
说白了，哈夫曼编码是「快刀斩乱麻」，简单直接。算术编码是「绣花针功夫」，精细但费事。选哪个取决于你的场景——如果对压缩率要求极高，或者符号概率差异很大，算术编码是更好的选择。
一个完整的编码示例
咱们用 Python 写个简单的算术编码器，感受一下实际效果。
class ArithmeticEncoder:
def __init__(self, prob_table):
# prob_table: {'A': 0.6, 'B': 0.4}
self.prob = prob_table
self.low = 0.0
self.high = 1.0
def encode(self, symbols):
for s in symbols:
range_len = self.high - self.low
# 计算当前符号的累积概率
cum = 0.0
for key, prob in self.prob.items():
if key == s:
break
cum += prob
# 更新区间
self.high = self.low + range_len * (cum + self.prob[s])
self.low = self.low + range_len * cum
# 返回区间内任意小数
return (self.low + self.high) / 2
# 使用示例
encoder = ArithmeticEncoder({'A': 0.6, 'B': 0.4})
code = encoder.encode("ABA")
print(f"编码结果: {code}") # 输出 0.432解码器就是反过来，根据小数落在哪个区间，反推出符号序列。这里不展开写了，原理一样。
小技巧：实际项目中，不要用浮点数实现。上面这个 Python 示例只是为了让你理解原理。生产环境一定要用整数运算，否则长消息会出精度问题。我一般用 32 位或 64 位整数，配合位操作来模拟无限精度。
总结
算术编码的核心就三句话：
- 区间划分：每个符号对应一个子区间，概率越大区间越宽。
- 逐符号缩小：每编码一个符号，区间就缩小到该符号对应的子区间。
- 输出小数：最终区间内的任意小数就是编码结果。
它比哈夫曼更紧凑的原因，说白了就是去掉了「整数比特」这个硬约束。每个符号可以占用不到 1 个比特，在概率分布不均匀时优势巨大。
但代价是实现复杂。精度处理、概率模型更新、结束标志——每个环节都有坑。我建议你先用浮点数版本跑通原理，再切换到整数版本做生产实现。这样既能理解精髓，又能避免踩坑。