源编码与压缩

熵是无损压缩的理论下界——任何编码的期望码长都逃不过 H(X)。Kraft 不等式管前缀码能不能存在,Huffman 贪心逼近它,算术编码几乎摸到熵率。语言模型提供概率预测,再配合熵编码器就能组成压缩系统;模型的交叉熵对应它在数据上的理想平均码长。

引子:压缩到底在跟谁较劲

前两章反复出现一个数:熵 H(X)。它被说成"平均要问几次""平均要花几个 bit"。这一章把它兑现成一件很实在的事——⁠压缩⁠。

任务很朴素:给一串符号编码成二进制,平均码长越短越好,而且要能一字不差地还原(无损)。问题是,能压到多短?有没有一堵墙,谁都翻不过去?

有。那堵墙就是熵。这一章讲清三件事:墙在哪(源编码定理)、怎么造码逼近墙(Huffman、算术编码)、以及为什么"语言模型"和"压缩器"其实是同一样东西。

前缀码与 Kraft 不等式

先解决"能不能无歧义解码"。最实用的一类编码是前缀码(prefix code):没有任何码字是另一个码字的前缀。这样解码时读到一个完整码字就能立刻切分,不需要任何分隔符。

哪些码长的组合能凑成前缀码?Kraft 不等式 给出充要条件:对码长为 l_1, l_2, \ldots, l_n 的二进制前缀码,存在这样的码,当且仅当

\sum_i 2^{-l_i} \leq 1

直觉⁠:把码字想成一棵二叉树上的叶子。长度 l_i 的码字,占据了 2^{-l_i} 比例的"码空间"。总占用不能超过 1,否则必然有码字冲突。

这个不等式还悄悄告诉你一件事:想让某些码字更短(减小 l_i),就必须让另一些更长。⁠码长是零和的⁠——短一点的地方,总要在别处补回来。

Shannon 源编码定理:熵是下界

Shannon 源编码定理(无损) 说:对任何唯一可解码的编码,期望码长 L 满足

L \geq H(X)

而且总存在编码,使 H(X) \leq L < H(X) + 1。

这句话有两层。第一层:熵 是无损压缩的硬下界⁠,谁也压不到熵以下。第二层:这个下界几乎可达——那个 +1 的间隙,可以靠"把多个符号打包成一组再编码"摊薄到任意小。

证明骨架⁠(值得记):把 Kraft 不等式和 Gibbs 不等式一拼,

L - H(X) = \sum_x p(x)(l_x + \log_2 p(x)) \geq 0

当 l_x = -\log_2 p(x) 时取等号——⁠理想码长就是自信息⁠。

麻烦在于:自信息通常不是整数,而码字长度必须是整数。这个"取整损失",正是接下来 Huffman 与算术编码在拉锯的东西。

Huffman 编码:贪心逼近

Huffman 编码 用一个贪心过程,造出期望码长最优的整数前缀码⁠。规则:反复取当前概率最小的两个节点,合并成一个父节点(概率相加),直到只剩一个根;合并时给两条边分别标 0 / 1,从根到叶的路径就是码字。

结果自然是:高频符号靠近根、码字短;低频符号远离根、码字长。

这个例子里,概率恰好都是 2 的幂。算一下期望码长:

L = 0.5\times 1 + 0.25\times 2 + 0.125\times 3 + 0.125\times 3 = 1.75\ \text{bit}

正好等于熵 H = 1.75 bit——完美命中下界。

但这是特例。一旦概率不是 2 的幂,整数码长就凑不出理想的 -\log_2 p(x),Huffman 每个符号最多会浪费 1 bit。这个浪费从哪来?就是上一节那个"取整损失"。

算术编码:摆脱整数比特

算术编码(arithmetic coding) 直接绕开了 Huffman 的整数瓶颈。

它的思路很不一样:不给单个符号分配整数码字,而是把整条消息映射成 [0,1) 区间里的一个小区间。每读一个符号,就按它的概率把当前区间按比例细分,选中对应的子区间;读完整条消息,输出一个足以唯一确定该区间的二进制小数。

这么做换来两个关键优势:

• 不再要求整数比特⁠。一个概率 0.9 的符号可以只花约 0.15 bit,Huffman 做不到(它至少 1 bit)。
• 能逼近熵率⁠。长消息下,平均码长可以任意接近 H(X),把 Huffman 那个 +1 间隙几乎抹平。

代价也有两条:计算比 Huffman 复杂;而且需要一个精确的概率模型。记住第二条——"提供精确概率模型"这件事,正是语言模型在做的,后面就靠它接上。现代实用变体是 range coding 和 ANS(Asymmetric Numeral Systems),后者是 zstd、LLM 压缩基准里的常客。

熵率:符号间的依赖

到这里都默认符号是独立的,H(X) 是单符号的熵。但真实数据(文本、音频)符号间有强依赖,得换一个量:⁠熵率(entropy rate)。

H_\text{rate} = \lim_{n\to\infty} \frac{1}{n} H(X_1, X_2, \ldots, X_n)

对常见的平稳信源,它也等于无限历史下的平均条件熵,把符号之间的依赖都算进去了。这里的极限和等价关系需要平稳性等条件;对个人知识库先记住"长期每符号还剩多少不可预测性"这个直觉即可。

英文是最好的例子。按单字符独立假设,约 4.7 bit;考虑字母频率,降到约 4.1;再考虑上下文依赖,Shannon 估计的熵率只剩约 1.0–1.3 bit/字符⁠。依赖越强,熵率越低,可压缩的空间越大。所有实用压缩器(以及语言模型)榨的,就是这份冗余。

AEP 与典型集:为什么长序列能贴近熵

单个符号的理想码长 -\log_2p(x) 往往不是整数,为什么把序列拉长后,平均码长却能逼近熵?连接这两件事的是渐近等分性质(Asymptotic Equipartition Property, AEP)。

对独立同分布信源生成的长序列 X^n=(X_1,\ldots,X_n),大概率会看到:

-\frac{1}{n}\log_2 p(X^n)\approx H(X)

也就是说,绝大部分概率质量集中在一组典型序列上。这组序列大约有 2^{nH(X)} 条,每条的概率大约是 2^{-nH(X)}。因此只需约 nH(X) bit 就能给典型序列编号;少数非典型序列单独处理,其额外代价会随着 n 增大被摊薄。

这就是"单个符号只能做到 H\leq L<H+1,长块却能把每符号码长压到 H"背后的原因。对有依赖的平稳遍历信源,同样的直觉由熵率接管。AEP 也解释了为什么后面的 信道编码定理 总在谈长码字和渐近极限。

语言模型怎样接上压缩

把上面的链条接起来,会得到信息论里最漂亮的一个等价。

一个语言模型,每一步给每个 token 输出一个概率分布 q。若拿它去驱动算术编码,一段文本的理想码长就是逐 token 的 -\log_2q(x_i\mid x_{<i}) 之和;忽略有限精度和收尾开销后,平均每 token 码长就是模型在这段文本上的交叉熵(见 交叉熵)。而源编码定理说,这个码长的下界是数据真实的熵率 H_\text{rate}。于是:

模型的交叉熵损失,对应把它作为概率模型时的理想压缩比特率。损失越低 = 预测越准 = 配合熵编码器后通常压得越狠。若模型精确匹配数据分布,其交叉熵会达到数据熵率。

这不只是比喻,但要把角色分清:⁠语言模型提供概率,算术编码 / ANS 才把概率变成可还原的比特流⁠。解码端还必须共享同一模型,模型权重本身的存储和传输成本也要计入;只有在大量数据上摊销后,才可以近似忽略这笔固定成本。因此,预测能力和压缩能力高度相关,却不是任何场景下都能无条件画等号。

分词那一层的 BPE 也带有压缩算法的血统:它贪心合并高频相邻符号,让常见片段用更少 token 表示。但序列变短不等于每字节信息量必然下降⁠——词表变大、token 概率和模型能力也会改变。更准确地说,BPE 是在序列长度、词表大小和可学习性之间做工程权衡。算法细节见 Token 与采样,压缩视角怎么帮助理解 scaling law,展开在 LLM 中的信息论。

参考

• 论文⁠: "A Mathematical Theory of Communication" (Shannon, 1948 — 源编码定理与英文熵率估计的原始出处)
• 教材⁠: "Elements of Information Theory" (Cover & Thomas — 第 5 章 Data Compression,Kraft/Huffman/算术编码)
• 基准/项目⁠: "Hutter Prize" 与 "Language Modeling Is Compression" (Delétang et al., 2023 — 用 LLM 做无损压缩,实证损失即比特率)

关键词: 前缀码 prefix code, Kraft 不等式, 源编码定理 source coding theorem, Huffman 编码, 算术编码 arithmetic coding, ANS, 熵率 entropy rate, AEP, 典型集 typical set, 无损压缩, 语言模型与压缩, Hutter Prize, BPE