有人给内部工具设计一种二进制记录格式,订单状态一共五种:待支付、已支付、已发货、已完成、已取消。他想留点余量,用了三个字节存状态。上线半年后,导出文件到了两百多兆,运维问能不能压一压。把状态字段改成三位二进制,理论上能省下大半,但他不确定这样改会不会影响已经写出来的文件。

这个问题背后的东西,比「换个字段宽度」更普遍:一份数据里,不同符号出现的次数差得很远,用同样长度的编码去表示它们,本身就在浪费。哈夫曼编码和算术编码就是解决这件事的两种经典方案,一个用变长码表,一个用区间划分。它们被塞在 gzip、PNG、JPEG、MP3、视频编码里,只是平时藏在格式内部,看不见。

这篇从定长编码的浪费讲起,用一段可以手算的文本走一遍哈夫曼,再看算术编码怎么把「每个符号至少一位」这个限制绕过去,最后说清楚两种方法的代价和适用边界。下一篇讲 LZ 系列,那是另一条完全不同的路:不统计符号,转而找重复片段。

现象真实原因第一步查什么
五个状态用三个字节,文件比预期大很多定长编码没有利用「大部分记录都是已支付」这个分布统计各状态的出现次数,算一下熵和平均编码长度
压完只比理论下限大几个百分点哈夫曼每个符号至少占一位,码表本身也要占空间看符号种类有多少、码表多大、数据量够不够摊平开销
改了码表后,旧解码器读新文件乱码码字和符号的对应关系变了,格式没有版本号或码表没随文件传检查文件头有没有版本字段,码表是否能被解码端还原
压缩流中间坏一个字节,后面全解错前缀码依赖流的同步,错一位就可能把后续码字全部读偏看格式有没有分块、校验和或定期重同步机制
极端偏斜的数据压缩比不理想大量同符号时,哈夫曼仍要给这个符号至少一位算熵是不是远低于 1 bit,考虑游程编码或算术编码
同一个文件 gzip 比 zstd 又慢又大两者用的匹配策略和熵编码阶段不同,不是同一套算法做基准测试,分别记录压缩比、压缩耗时和解压耗时
文本压缩得很好,二进制数据几乎压不动文本符号种类少、分布偏,二进制字段通常接近均匀看数据的符号种类数和字节熵,不要用文本的经验套二进制

定长编码的浪费:每个状态都占同样的位置

定长编码的逻辑很直观:有五种状态,三位二进制刚好能表示八个值,于是每个状态都用三位。这样做的好处是解码简单,第几位对应哪个字段都是固定的,随机访问也方便。问题是它假设每个状态出现的概率一样,而现实几乎从不这样。

如果八成记录是「已支付」,其余四种平分剩下的两成,那么平均每个状态的信息量只有不到 1.2 bit,定长编码却固定花 3 bit。省下来的空间不是小数:一亿条记录,每条多花近两位,就是两百多兆比特,也就是二十多兆字节。数据越大,定长编码的浪费越明显。

解决思路是让编码长度跟着概率走:常见的符号给短码,罕见的符号给长码。只要短码省下的位数多于长码多花的位数,平均长度就会下降。哈夫曼编码给出的是一种最优的构造方法,在「每个符号单独编码、码长必须是整数位」这个前提下,它能让平均码长最小。

定长编码不是一无是处。字段位置固定,意味着可以不解码前面直接跳到后面,适合需要随机访问的场景。压缩和随机访问经常是矛盾的,选哪个取决于你怎么读这份数据。

还有一个隐含成本是字段对齐。三字节的状态后面接四字节的时间戳,很多语言读取时会按四字节对齐,实际占用可能比账面上的七字节更多。变长编码把这层对齐彻底打散,省了空间,却让「按固定偏移取值」这件事失效,读取时必须从头解码。

哈夫曼编码:按频率从下往上搭一棵树

哈夫曼的做法可以手算:把所有符号按出现次数排好,每次取出次数最少的两个,合成一个新节点,新节点的次数是两者之和;把这个新节点放回去,继续取最少的两个,直到只剩一个根节点。从根往下走,左边记 0,右边记 1,走到叶子就得到这个符号的码字。

拿一段经典文本 ABRACADABRA 举例。A 出现五次,B 和 R 各两次,C 和 D 各一次,一共十一个字符。按上面的规则合并,最后得到的码表是 A 占一位,C 和 D 占三位,B 和 R 也占三位。用这个码表编码,整段文本只需要 23 位。

import heapq, math, collections

text = "ABRACADABRA"
freq = collections.Counter(text)
n = len(text)

heap, order, tree = [], 0, {}
for ch, f in freq.items():
    heapq.heappush(heap, (f, order, ch))
    order += 1

while len(heap) > 1:
    f1, _, left = heapq.heappop(heap)
    f2, _, right = heapq.heappop(heap)
    heapq.heappush(heap, (f1 + f2, order, (left, right)))
    order += 1

def walk(node, prefix=""):
    if isinstance(node, str):
        tree[node] = prefix or "0"
        return
    walk(node[0], prefix + "0")
    walk(node[1], prefix + "1")

walk(heap[0][2])
encoded = "".join(tree[ch] for ch in text)
entropy = -sum((f / n) * math.log2(f / n) for f in freq.values())

print("freq:", dict(freq))
print("codes:", tree)
print("encoded:", encoded)
print(f"bits={len(encoded)} entropy={entropy:.3f} fixed8={n * 8}")

本机实际输出:

freq: {'A': 5, 'B': 2, 'R': 2, 'C': 1, 'D': 1}
codes: {'A': '0', 'C': '100', 'D': '101', 'B': '110', 'R': '111'}
encoded: 01101110100010101101110
bits=23 entropy=2.040 fixed8=88

按每个字符固定八位存,需要 88 位;按哈夫曼码表,只需要 23 位,平均每个字符 2.09 位,离熵算出来的 2.04 位只差一点点。这就是「按频率发码」的效果:出现五次的 A 只花一位,出现一次的 C 和 D 花三位,平均下来比定长省了近四分之三。

码表里有一个必须成立的性质:任何一个码字都不能是另一个码字的前缀。A 是 0,那么其他码字就不能以 0 开头,否则解码时读到 0 不知道该停还是继续。上面这棵树从叶子到根构造,天然满足前缀码的要求。如果随便按频率分配长短码而不检查前缀关系,压缩流就会变成歧义流,解码器只能靠猜。

哈夫曼的天花板:整数位和码表开销

哈夫曼不是万能的。它的第一个限制是码长必须是整数。一个符号如果熵只有 0.08 位,哈夫曼仍然要给它至少一位,剩下的 0.92 位就浪费了。极端情况下,一个文件里 99% 是同一个字节,哈夫曼只能压到原来的一小部分,却永远到不了熵算出来的理论值。

第二个限制是码表。解码端必须知道每个码字对应哪个符号,所以码表要么写进文件头,要么根据数据统计重建。数据量很小时,码表本身的开销可能比省下的还大。一个几十字节的文件,加上码表和块头,压完可能比原文件更大,这不是算法坏了,是固定成本摊不平。

第三个限制是统计。标准哈夫曼需要先扫一遍数据统计频率,再扫一遍编码,两遍才能完成。流式场景里,数据边到边压,没有机会回头统计,只能用自适应哈夫曼或者预先约定的码表。自适应版本会根据已读到的内容动态调整树,压缩比略差,但不用两遍。

哈夫曼编码的两个阶段
扫描统计频率
构造码树
写入码表
逐符号替换码字
解码端反向查表

还有一个工程细节:当多个符号频率相同时,树的形状不唯一,码表也不唯一。编码器和解码器必须用同一套规则,否则同一份数据在两个实现里得到不同的码字。实际格式通常把码表直接写进文件,或者用固定规则构造,避免这种不确定性。

自适应哈夫曼是另一种取舍。它不预先统计全局频率,而是从一棵只有根节点的空树开始,每读一个符号就更新一次频率、调整一次树。优点是只需一遍、适合流式;缺点是开头没有统计数据,码表要花一段时间才能收敛,压缩比通常比两遍版本低几个百分点。

算术编码:把整段数据压成一个区间

算术编码换了个思路:不再给每个符号单独发码字,而是把整段数据映射到零到一之间的一个区间。每读一个符号,就按它的概率把当前区间切一刀,保留对应的那一段;读得越多,区间越窄。最后只需要输出这个窄区间里的任意一个数,解码端按同样的概率表一步步还原。

用同一段文本的频率做演示,取前四个字符 ABRA。初始区间是零到一,A 的概率是 5/11,所以第一个字符之后区间变成零到 0.454545;B 的概率是 2/11,在剩余区间里再切一刀,区间缩到 0.206612 到 0.289256;接着是 R,再是 A。每读一个字符,区间宽度就乘上该字符的概率。

probs = {ch: f / n for ch, f in freq.items()}
cum, acc = {}, 0.0
for ch, p in probs.items():
    cum[ch] = (acc, acc + p)
    acc += p

low, high = 0.0, 1.0
for ch in "ABRA":
    w = high - low
    lo, hi = cum[ch]
    low, high = low + w * lo, low + w * hi
    print(f"{ch}: [{low:.6f}, {high:.6f}) width={high-low:.6f}")

本机实际输出:

A: [0.000000, 0.454545) width=0.454545
B: [0.206612, 0.289256) width=0.082645
R: [0.259204, 0.274230) width=0.015026
A: [0.259204, 0.266034) width=0.006830

四个字符之后,区间宽度只剩 0.00683,大约需要七位二进制小数才能唯一定位。整段十一个字符算下来,区间会更窄,但所需的位数接近熵给出的理论值,不会被「每个符号至少一位」卡住。这就是算术编码比哈夫曼强的地方:它把整段数据当成一个整体来分配位数,概率极低的符号可以只贡献零点几位。

上面是教学版,用浮点数演示区间收缩。真实实现不能用浮点,因为精度很快就不够,通常用整数区间和重归一化:当区间窄到一定程度,就把公共的高位输出,再把区间放大回可用范围。这套机制叫区间编码或范围编码,视频编码里的 CABAC、音频里的算术编码,都是它的工程版本。

它们藏在哪些格式里

这两种编码很少单独出现,更多时候是压缩流水线里的最后一步。gzip 和 PNG 先用 LZ 系列找重复,再把得到的长度、距离、字面量交给哈夫曼编码;JPEG 在量化之后,对直流系数做差分、对交流系数做游程,再把结果交给哈夫曼或算术编码;MP3 和 AAC 的量化频谱最后也要经过熵编码。

选哈夫曼还是算术编码,通常不是使用者能决定的,格式已经定死了。能决定的是「要不要用这个格式」和「参数怎么调」。比如同样是有损音频,AAC 在某些码率下比 MP3 好,一部分原因就是熵编码和量化策略更细;同样是无损压缩,zstd 在中等压缩级别下比 gzip 快很多,也不完全是熵编码的功劳,还跟匹配策略和窗口大小有关。

还有一个常见误解:以为「用了哈夫曼」就一定比「不用哈夫曼」小。哈夫曼只优化「给定符号流之后怎么表示」,如果前面的步骤没有把重复去掉,符号流本身还是很大,熵编码能做的有限。压缩比的大头往往在前面那一步:找重复、做预测、量化。

PNG 和 gzip 用的 DEFLATE 还有一个细节:数据会被切成若干块,每块可以独立选择码表,块与块之间的码表可以不同。这样既能适应局部分布变化,又能把错误限制在一块之内。代价是块头变多,小文件摊不平,所以小块并不总是更划算。

边界与代价

这两种方法都有明确的适用边界。哈夫曼适合符号种类不多、频率差异明显、数据量足够大的场景;算术编码适合概率分布连续、极端值多、愿意付出更多 CPU 的场景。两者都不适合「已经接近随机」的数据,因为没有什么分布可利用。

维度哈夫曼算术编码
压缩效率接近熵,但受整数位限制更接近熵,极端分布优势明显
实现复杂度树结构直观,解码查表快区间运算和重归一化复杂,容易写出边界错误
CPU 开销较低,硬件友好较高,逐符号做区间更新
错误传播错一位可能整段失步同样怕错,通常要配合校验和分块
专利与兼容长期公开,无授权障碍历史上有专利限制,部分场景改用变体

实际工程里,错误传播比压缩比更值得关注。前缀码和区间编码都依赖流的一致性,中间坏一个字节,后面的解码可能全部读偏。所以成熟格式会在外面套一层块结构、校验和重同步点,发现某块坏了就跳过,而不是让整段数据报废。自己设计格式时,这一层不能省。

不要自己实现算术编码的边界处理还直接上生产。区间收缩、进位、下溢这些边界条件很容易写错,错了不会立刻报错,只会在某些输入上解出错误数据。优先使用成熟库,或者先在大量随机数据上做往返测试。

最后一个代价是时间。压缩和解压都要花 CPU,而 CPU 在服务端是有限资源。一个接口为了省几兆带宽,把响应体用最高级别压缩,可能让 P99 延迟翻倍。判断标准还是端到端:传输省下的时间,能不能覆盖压缩和解压多花的时间。

当天能自己验证的五个练习

  1. 把示例文本换成一段中文,统计各字符频率,跑一遍哈夫曼,记录平均码长和熵的差距。
  2. 构造一个 99% 都是同一个字符的字符串,比较哈夫曼的平均码长和熵,算出浪费了多少位。
  3. 把哈夫曼码表里的某个码字改成另一个码字的前缀,写一个解码器,观察它为什么会读错。
  4. 用浮点算术编码示例编码不同长度的字符串,记录区间宽度和所需位数,画一张长度与位数的对照表。
  5. 用 gzip 和 zstd 压同一个文本文件,分别记录压缩比、压缩耗时、解压耗时,比较两种算法在你这台机器上的差异。

小结

三句话:定长编码假设所有符号一样常见,现实里大部分数据不是这样;哈夫曼用频率建树、给常见符号短码,逼近熵但受整数位和码表开销限制;算术编码把整段数据映射成区间,能突破每符号一位的限制,代价是实现复杂和 CPU 更高。这三者都不是「压一下就完事」的魔法,前置的统计和格式设计同样决定结果,选错场景一样白忙。

下一篇讲 LZ 系列。前面这些方法都在统计「单个符号出现多少次」,LZ 换了个问题:这段内容之前是不是出现过?出现过的部分能不能直接引用?这条思路撑起了 gzip、zip、PNG 的大部分压缩比。