源编码与压缩

熵是无损压缩的理论下界——任何编码的期望码长都逃不过 H(X)。Kraft 不等式管前缀码能不能存在,Huffman 贪心逼近它,算术编码几乎摸到熵率。而最深的一句是:语言模型即压缩,一个完美 LLM 的交叉熵损失,就是数据熵率的估计。

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

前两章反复出现一个数:熵 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/字符⁠。依赖越强,熵率越低,可压缩的空间越大。所有实用压缩器(以及语言模型)榨的,就是这份冗余。

语言模型即压缩

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

一个语言模型,每一步给每个 token 输出一个概率分布 q。若拿它去驱动算术编码,压缩一段文本的平均码长,恰好就是模型在这段文本上的交叉熵 H(p,q)(见 交叉熵)。而源编码定理说,这个码长的下界是数据真实的熵率 H_\text{rate}。于是:

模型的交叉熵损失 = 用它做无损压缩的比特率。损失越低 = 压得越狠 = 越接近数据熵率。一个"完美"的语言模型,其交叉熵就等于数据熵率的下界。

这不是比喻。GPT / Claude 这类模型,⁠本质上就是极致的无损压缩器⁠。也正因如此,模型越强,在压缩基准(比如以 enwik9 维基文本为目标的 Hutter Prize)上表现越好——这两件事是同一件事的两个刻度。

分词那一层的 BPE 也是这个逻辑的工程近似:它用贪心合并,把高频子串压成单个 token,启发式地降低序列的比特成本——一种粗粒度的熵优化。BPE 算法细节见 Token 与采样,这里只需记住"BPE 是压缩问题的工程近似"这条联系。压缩视角怎么解释 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, 无损压缩, 语言模型即压缩, Hutter Prize, BPE