--- title: 源编码与压缩 url: https://doc.liz6.com/theory/01-information-theory/03-source-coding-and-compression locale: zh area: theory tags: - theory - 信息论 date: 2026-07-18 modified: 2026-07-29 description: 熵是无损压缩的理论下界——任何编码的期望码长都逃不过 H(X)。Kraft 不等式管前缀码能不能存在,Huffman 贪心逼近它,算术编码几乎摸到熵率。语言模型提供概率预测,再配合熵编码器就能组成压缩系统;模型的交叉熵对应它在数据上的理想平均码长。 --- # 源编码与压缩 > 熵是无损压缩的理论下界——任何编码的期望码长都逃不过 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$。这句话有两层。第一层:[熵](/theory/01-information-theory/01-entropy-and-information-measures.md) 是无损压缩的**硬下界**,谁也压不到熵以下。第二层:这个下界几乎可达——那个 $+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 模型的交叉熵损失,对应把它作为概率模型时的理想压缩比特率。损失越低 = 预测越准 = 配合熵编码器后通常压得越狠。若模型精确匹配数据分布,其交叉熵会达到数据熵率。这不只是比喻,但要把角色分清:**语言模型提供概率,算术编码 / ANS 才把概率变成可还原的比特流**。解码端还必须共享同一模型,模型权重本身的存储和传输成本也要计入;只有在大量数据上摊销后,才可以近似忽略这笔固定成本。因此,预测能力和压缩能力高度相关,却不是任何场景下都能无条件画等号。分词那一层的 **BPE** 也带有压缩算法的血统:它贪心合并高频相邻符号,让常见片段用更少 token 表示。但**序列变短不等于每字节信息量必然下降**——词表变大、token 概率和模型能力也会改变。更准确地说,BPE 是在序列长度、词表大小和可学习性之间做工程权衡。算法细节见 [Token 与采样](/ai/01-models-and-context/02-tokens-and-sampling.md),压缩视角怎么帮助理解 scaling law,展开在 [LLM 中的信息论](/theory/01-information-theory/06-information-theory-in-llms.md)。 | 方法 | 是否整数码长 | 逼近熵的程度 | 典型场景 | |------|------------|------------|---------| | Huffman | 是 | 最多浪费 1 bit/符号 | 静态词表、简单快速(gzip 内部) | | 算术 / range / ANS | 否 | 可任意逼近熵率 | 需要精确概率模型时(zstd、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*