05 万能压缩器不存在，三行就能证明

▷ 先猜一下

有人给你一个压缩程序，说它能把任意 1 GB 文件压到 999 MB，解压后一字不差。你的判断是：

A 有可能，看文件内容B 不可能，但要看具体算法才知道C 不可能，而且不用看算法D 要看是不是量子算法

三行证明

答案是 C，而且理由和算法一点关系都没有。

1. 长度恰好为 n 比特的文件，一共有 2ⁿ 个。

2. 长度【小于】n 比特的文件，一共有
   2⁰ + 2¹ + … + 2ⁿ⁻¹ = 2ⁿ − 1 个。

3. 无损压缩必须是【单射】——两个不同的文件不能压成同一串，
   否则解压时不知道该还原成哪个。
   把 2ⁿ 个东西一一对应地塞进 2ⁿ−1 个格子里，
   鸽笼原理说：【至少有一个塞不下】。

完了。

注意这个论证里没有出现「算法」两个字。它对 zip 成立，对 7z 成立，对还没被发明出来的算法成立，对上帝写的压缩器也成立。它是一个关于「计数」的事实，不是关于「技术」的事实。

◆ 所以压缩到底是什么

既然不可能所有文件都变小，那么任何一个压缩器都是在做一笔赌注：

把一部分文件换短，代价是把另一部分换长。

zip 之所以有用，不是因为它「能把文件变小」，是因为它赌对了：它让你会遇到的那些文件变短，让你永远不会遇到的那些（几乎所有随机字节串）变长。

而「你会遇到什么文件」，就是第 1 章那个概率分布。压缩器的水平 = 它对这个分布猜得有多准。这句话第 12 章会变成一个可以直接测量的数字。

把这笔账真的算一遍

下面这台 demo 把某个长度的所有文件枚举一遍，用一个真的（很简单的）压缩器跑，然后数账：

看那个「全体净收支」。在 n = 10 的档位上，1024 个文件里只有 16 个被压短了，其余 1008 个各多花 1 比特，总账净亏 992 比特。

而它在现实里仍然是一台有用的压缩器。因为现实里的文件不是从 1024 个里均匀抽的。你的日志、你的代码、你的截图，全都密集地挤在那 16 个「规整」文件所在的角落里。

▸ 在现实里：那个「兜底」不是小聪明，是标准做法

demo 里那个「压不动就原样存，只多付 1 位标志」，是所有真实压缩格式都有的机制：

DEFLATE（zip / gzip / PNG 用的）有 stored block 类型：不压，原样放，只加几字节头。
PNG 每一行前面有一个 filter 字节，0 表示「这行不做任何变换」。
HTTP 的 Content-Encoding 允许服务器决定这次压不压——很多服务器对已经压过的格式（JPEG、MP4）直接跳过。

所以「gzip 一个 JPEG 会变大」不是 bug，是鸽笼原理在你面前现身。正确的做法不是换个更强的压缩器，是别压。

地板在哪：香农第一定理

知道了「不可能全赢」，下一个问题就是「最多能赢多少」。

答案就是第 2 章那个熵。这个结论叫无失真信源编码定理（香农第一定理），它有两半，两半都重要：

◆ 香农第一定理

设一个信息源每个符号的熵是 H，那么：

下界（谁也过不去）：任何无损编码的平均码长 L ≥ H。

可达（这个下界不是空话）：存在编码方式，使 L 可以任意接近 H。

第一半说「别想了」，第二半说「但能摸到」。一个只有前一半的定理是悲观主义，只有后一半的是营销话术。两半合起来才是工程学。

下界为什么成立：一条不等式

下界的证明只需要一个观察，叫克拉夫特不等式（Kraft inequality）：

∑ 克拉夫特不等式：码长不能想多短就多短

先说一个前提：我们要的是前缀码——没有任何一个码字是另一个码字的前缀。

为什么要这个？因为没有它，你就没法在一串连续的比特里知道每个码字在哪结束。如果 A = 0 而 B = 01，那么收到 01 时你不知道这是「B」还是「A 后面跟着一个还没收完的东西」。

而前缀码可以画成一棵二叉树：每个码字是一片叶子，往左是 0，往右是 1。「没有码字是别人的前缀」正好等价于「没有码字长在另一个码字的路上」。

现在数格子。一棵深度无限的二叉树，把所有叶子的「占地面积」加起来是 1；一个长度为 ℓ 的码字，占掉 2⁻ˡ 的面积。于是：

Σ 2^(−ℓᵢ)  ≤  1                    【克拉夫特不等式】

# 取等号 = 这棵树一片空地都没剩，全部铺满。
# 第 6 章那台霍夫曼编码器算出来的码，这个和恰好等于 1。

有了它，剩下的是一步标准的凸性论证（吉布斯不等式）：在 Σ2⁻ˡ ≤ 1 的约束下，最小化 Σ pᵢ ℓᵢ，最优解是 ℓᵢ = −log₂ pᵢ，最优值正好是 H。

换句话说：理想码长就是自信息。一个概率 1/8 的符号，应该占 3 个比特——不多不少。

可达为什么成立：典型集

下界好懂，可达那一半才是香农真正的贡献，而它的核心思路值得单独讲，因为它在这本书后面还会再出现一次（第 16 章的信道容量用的是同一招）。

◆ 典型集：绝大多数序列根本不会出现

还是那枚 p = 0.9 的硬币，抛 1000 次。

一共有 2¹⁰⁰⁰ 种可能的序列。但你实际会看到什么？正面大约 900 次，反面大约 100 次。偏离这个比例很多的序列（比如正面只有 500 次），概率小到可以忽略。

「正面约 900 次」的序列有多少条？大约 C(1000, 100) ≈ 2⁴⁶⁹ 条。

而 1000 × H(0.9) = 1000 × 0.469 = 469。

一模一样。这不是巧合，这就是渐近均分性（AEP）。

长度 n 的序列一共有   2ⁿ 条
其中「典型」的大约有  2^(n·H) 条        ← 只有这些会真的出现
每条典型序列的概率约  2^(−n·H)          ← 而且它们几乎等可能

# 于是压缩的办法就摆在那里了：
# 给这 2^(nH) 条典型序列编号，一个编号 n·H 比特。
# 非典型的序列？留一个逃生出口，反正几乎不会用到。

这就是可达性证明的全部骨架。它同时解释了为什么压缩必须「批量」才划算——n 越大，非典型序列的概率越小，这个方案越接近完美。

✗ 这个直觉是错的

「压缩就是找出文件里的冗余，把它删掉。」压缩是换一套编号方式：给常见的东西编短号，给罕见的东西编长号。没有任何东西被「删掉」——无损压缩里信息量一比特都不会少。

这个区别在有损压缩那里才变得清楚：JPEG 和 MP3 真的删了东西（人眼人耳注意不到的部分），所以它们能突破熵这个地板。而这本书讲的全是无损压缩，地板就是地板。

顺带一提：有损压缩有它自己的一套理论，叫率失真理论（rate–distortion theory），也是香农 1959 年建立的。它回答的问题是「允许失真到什么程度，最少要几个比特」。这本书不展开，但第 24 章会告诉你从哪继续往下读。

一个推论：随机数据压不动，而且这可以用来检验

如果一段数据是真随机的（每个比特独立均匀），它的熵就是每比特 1 比特，地板等于原文，压缩率必然是 1。

这给了你一个非常实用的诊断工具：

▸ 在现实里：用 gzip 当随机性检测器

把一段数据丢给 gzip -9，如果它压不动，说明这段数据在 gzip 能看见的那些结构上是「随机的」。

这个土办法在实践中很有用：

检查加密输出：密文如果能被压缩，说明加密有问题（正确的密文应当和随机串不可区分）。
检查随机数生成器：输出能压缩 = 有周期或偏置。
检查「这个文件已经压过了吗」：压不动多半压过了。

但要注意它的边界：压不动只说明「gzip 找不到结构」，不说明「没有结构」。一个用 x → x+1 mod 2³² 生成的伪随机序列，如果先做一次异或掩码，gzip 大概率压不动，但它一点都不随机。「某个具体的压缩器压不动」是一个很弱的随机性证据——这一点在第 13 章会被推到极致：真正的「随机」定义要用「最短的程序」，而那个东西是不可计算的。

◇ 结账

C：不可能，而且不用看算法

如果你选了 A 或 B，你的直觉把这件事当成了一个工程问题（「算法够不够好」）。它不是，它是一个计数问题。

而这个区分很有价值：以后遇到任何「我们发明了一种能压缩任意数据的方法」的说法，你不需要去读它的技术细节——你可以直接问它：那你把 2ⁿ 个文件塞进 2ⁿ−1 个格子的哪一步做了手脚？答案通常是三种之一：它其实是有损的，它其实把一部分数据藏在了别处（比如文件名或者字典里），或者它只对某类数据有效（那就没什么好吹的了）。

这一章的一句话

压缩不是「让文件变小」这门手艺，是「赌哪些文件会出现」这笔赌注。赌注的天花板是熵，而不可能有一台压缩器在所有赌局上都赢。

下一章开始真的动手。第一台压缩器：霍夫曼编码。它是一棵按概率长出来的树，1951 年由一个交不出期末论文的研究生在放弃的那天想出来的——而它在某个精确的意义上是最优的，同时又有一个致命的病。两件事我们都会看清楚。