第 12 章

压缩算法——1948年，信息究竟能被压缩到多小？

原文从第一幕开始；章标题依据第十一章预告恢复，未补写导语。

正在加载交互实验…

第一幕：1948年，一个32岁的数学家重新定义了“信息”

第 12 章配图 2 — Tekniska museet；摄影者不详 · 来源 · CC BY 2.0

Claude Shannon

1916—2001 · 美国数学家、电气工程师香农的研究奠定了现代信息论的重要基础。他还研究过密码学、通信系统、开关电路和机器智能。

1948年7月，《贝尔系统技术期刊》（Bell System Technical Journal）刊登了一篇论文：A Mathematical Theory of Communication《通信的数学理论》。第二部分发表于同年10月。这篇论文后来成为信息论最重要的奠基文献之一。^{[数字对象标识符][Wiley Online Library]}

当时的通信工程师为什么需要这样的理论？

那是电话、无线电、电视和电子通信迅速发展的时代。工程师每天都在面对一些非常实际的问题：一条电话线最多能够传输多少信息？如果信道存在噪声，接收端还能不能恢复原始消息？要传输同样的内容，能否使用更少的信号？当时已经存在研究通信速度和带宽的数学理论，例如 Harry Nyquist 与 Ralph Hartley 的工作。但香农希望建立一套更加普遍的理论，把消息的不确定性、信道容量、噪声和编码联系起来。他提出了一个极其大胆的抽象：研究通信时，不一定需要知道消息的具体意义。重要的是发送者可能发出什么消息，以及它们出现的概率。这使通信问题可以通过数学方法进行研究。

一个看起来很反直觉的问题

假设我向你发送一个字母。只有两种可能：A 或 B。如果 A 和 B 出现的概率相同，那么收到字母之前，你确实不知道它是哪一个。但如果：

A 出现的概率为99.9%。
B 出现的概率为0.1%。

那么你在收到消息之前，几乎已经能猜到它会是 A。这两种情况下，虽然字母种类一样，但消息带来的不确定性显然不同。香农把这种平均不确定性用一个数学量来描述：信息熵（Information Entropy）。对于离散随机变量：

H(X)=-\sum_i p_i\log_2p_i

这里的

p_i

是第

i

种符号出现的概率。使用以2为底的对数时，单位是 bit。

为什么越确定，熵越低？

我们来动手观察。

香农的信息熵实验

Binary Entropy

符号 A 出现概率

50%

平均信息熵

1.0000

bit / 符号

二元信源熵在两种结果等概率时达到最大值 1 bit。

查看图表数据

probability	信息熵
0%	0
10%	0.469
20%	0.722
30%	0.881
40%	0.971
50%	1
60%	0.971
70%	0.881
80%	0.722
90%	0.469
100%	0

A 与 B 完全等概率，接收消息前的不确定性最大。

当 A、B 各占50%时：

H=1\text{ bit}

如果 A 的概率达到100%，B 永远不会出现：

H=0

这是一个影响深远的结论。信息熵不只是抽象的概率公式。它还告诉我们：数据源本身的统计特性，决定了无损压缩在理论上能够达到什么程度。但这不意味着任意一段长度固定的数据都可以被压缩。如果所有可能消息都同样可能，那么就不存在一种无损编码，能让每一条消息都变得更短。压缩必须利用某种不均匀性、重复性或结构。而接下来，故事转向麻省理工学院的一间课堂。

第二幕：1951年，一场本来可以参加考试的课程作业

David A. Huffman

1925—1999 · 美国计算机科学家曾在麻省理工学院学习，后来在加州大学圣克鲁兹分校任教。他最著名的贡献，是提出最优前缀编码的构造算法。

1951年，Huffman 是 MIT 的一名研究生。他选修了一门信息论课程，授课教授是 Robert M. Fano。Fano 本人是信息论和通信研究的重要人物，与香农的研究领域密切相关。那门课的期末考核提供了一个选择：参加期末考试。或者完成一篇学期论文。Huffman 选择了论文。题目是研究怎样为一组出现概率不同的符号，设计平均长度最短的二进制编码。听起来，这似乎就是普通的课堂作业。但根据1991年《科学美国人》对 Huffman 的采访，当时 Fano 和 Shannon 都已经研究过相关最优编码问题，尚未找到后来那样简洁的构造方法。^{[Huffman Coding][Mathematical Association of America]}这意味着，Huffman 实际上在尝试一个前沿研究问题。而他起初并不知道这个问题有多困难。

几个月的尝试

Huffman 花费很长时间研究各种编码方案。他尝试建立数学规则，也尝试不同的构造方法。但始终无法证明自己的方案就是最优的。最后，他打算放弃论文，转而准备考试。1991年的报道中，他回忆，自己正准备丢弃研究笔记时，突然意识到应该怎样构造这棵编码树。这个顿悟成为他一生中最难忘的时刻之一。^{[www-sigproc.eng.cam.ac.uk]}这里需要说明，所谓“丢弃笔记时突然想到答案”的细节，是 Huffman 几十年后的个人回忆，并不是我们可以独立验证到分钟的实验记录。但其核心情节有可靠的访谈来源。这位学生真的解决了一道其老师也在研究的问题。1952年9月，他的论文正式发表于 Proceedings of the IRE：A Method for the Construction of Minimum-Redundancy Codes《一种构造最小冗余编码的方法》。^{[ScienceOpen]}阅读 Huffman 1952年四页原始论文但要理解他真正发现了什么，我们还要先重新做一次香农的编码实验。

第三幕：既然 A 经常出现，为什么还要给它分配很长的编码？

假设我们要传输由四种字母组成的消息。每种字母出现的概率不同。

字符	出现概率
A	50%
B	25%
C	12.5%
D	12.5%

如果采用固定长度编码，因为只有四个字符，我们可以用两位二进制数表示每一个字符：

字符	固定长度编码
A	00
B	01
C	10
D	11

每个字符都是2 bit。因此平均码长是：

L=2

那么，可不可以让最常出现的 A 只用1 bit 表示？例如：

字符	可变长度编码
A	0
B	10
C	110
D	111

你可能立刻发现：A 只需要1 bit。B 需要2 bit。C、D 各需要3 bit。于是平均码长：

L=0.5(1)+0.25(2)+0.125(3)+0.125(3)

\boxed{L=1.75\text{ bit/符号}}

比固定长度编码的2 bit更短。而且，这个例子的熵正好也是：

H=1.75\text{ bit/符号}

所以，这套编码在此概率分布下达到了熵下界。一个值得注意的历史细节是，香农1948年论文中就给出了同样的四符号概率分布与编码示例。Huffman 的突破不是第一次想到“高频字符用短码”，而是提供了对任意给定符号概率构造最优二元前缀码的系统算法。^{[knuthlab.org]}

可变长度不会产生歧义吗？

假设：A = 0B = 01那么收到：01它究竟应该被解释成 B，还是先读到 A，再读到一个没有完整解释的 1？问题就在这里。如果一种字符的编码，是另一种字符编码的开头，解码可能出现歧义或需要额外的分隔规则。于是，我们要求：任何一个字符的编码，都不能是另一个字符编码的前缀。这叫作前缀码（Prefix Code），或者即时码（Instantaneous Code）。刚才的编码：0、10、110、111恰好满足这个条件。因为没有任何一个完整码字，是另一个码字的前缀。接收端可以从左向右读取比特流，只要读到一个完整码字，就立刻确定一个字符。这就把问题从简单的概率分配，变成了一棵树的设计。

第四幕：Huffman 的惊人发现——不要从根开始建树

这里就是整章最精彩的算法时刻。假设我们有六个字符：

字符	频次
A	45
B	13
C	12
D	16
E	9
F	5

总共100次出现。我们希望设计一棵二叉编码树。从根向左走，记为0。从根向右走，记为1。每个字符位于叶节点。字符的编码，就是从根到该叶节点的路径。树越浅，编码越短。树越深，编码越长。

关键问题：谁应该放在最深的位置？

假设有两个字符：A 出现45次。F 出现5次。如果 A 的编码长5 bit，而 F 的编码长1 bit，显然不划算。因为频繁出现的 A，每次都要支付高昂的编码成本。而很少出现的 F，反而占据了最短的编码位置。因此，我们倾向于把高频字符放在浅层，把低频字符放在深层。但 Huffman 想得更进一步。在一棵最优编码树中，可以让频率最低的两个字符成为最深层的兄弟叶节点。如果能保证这一点，就可以把两个最小频率合并成一个新节点。然后把问题规模减小一。这就是一个可以反复使用的贪心选择。

每次合并两个最小频率

我们的初始频次：45、13、12、16、9、5第一步：选出最小的5和9。合并成14。第二步：剩下 12、13、14、16、45。选出12和13。合并成25。第三步：剩下 14、16、25、45。选出14和16。合并成30。第四步：剩下 25、30、45。合并25和30，得到55。最后：合并45和55，得到100。一棵完整的编码树诞生了。

动手建造自己的 Huffman 树

Huffman 编码树构造器

每次选择两个权重最低的节点

合并 0/5

当前节点集合

5

9

12

13

16

45

六个字符各自是一个独立节点。找出频次最低的两个。

注意，这里最巧妙的一点是：Huffman 不是从根节点开始猜测字符应该放在哪里。而是从最不重要的两个字符开始，把它们组合成一个子问题。这叫作自底向上构造（Bottom-up Construction）。是不是又想到了我们之前学习过的归并排序？虽然目的完全不同，但它们都通过逐渐合并较小结构，形成更大的结构。而 Huffman 每一步都需要选出当前最小的两个权重。最适合的数据结构是什么？答案是：最小堆（Min Heap）。第七章我们学习堆排序时，已经认识它了。使用最小堆，可以使 Huffman 树的典型构造复杂度达到：

O(k\log k)

其中

k

是不同符号的数量。

第五幕：为什么 Huffman 的贪心选择居然不会错？

你应该记得第九章的贪心算法。我们在那里学过：“每次选择当前最便宜的方案”，并不总能获得全局最优。找零钱就是反例。那么，Huffman 为什么敢每次合并两个最小频率？答案依然是数学证明。

第一条性质：低频字符可以放在更深的位置

对于一棵前缀编码树，假设：字符 A 的频次比字符 B 高。但是 A 的编码更长。如果交换 A 与 B 的位置，会发生什么？原先编码代价：

f_A L_A+f_B L_B

交换之后：

f_A L_B+f_B L_A

两者差值：

(f_A-f_B)(L_B-L_A)

由于：

f_A\geq f_B

以及：

L_A>L_B

交换后成本不会增加。因此，我们总可以把频率较低的字符安排在更深的位置，而不会让总体编码代价变差。

第二条性质：两个最低频率符号可以成为兄弟

在一棵最优的完整二叉前缀编码树中，我们可以找到一对位于最大深度的兄弟叶节点。通过交换符号标签，可以让两个频率最低的字符位于这两个叶节点上，而不增加编码代价。然后，把这两个兄弟叶子合并成一个父节点。新父节点的权重等于两者频次之和。于是问题就变成了一个规模更小、结构完全相同的最优编码问题。这就满足了贪心选择性质与最优子结构。通过归纳，可以证明 Huffman 算法生成的二元前缀码具有最小的加权路径长度。也就是：

\sum_i f_i L_i

达到最小。它的正确性不是来自经验上“高频字符应该更短”，而是来自严格的交换论证与递归缩减。这也是 Huffman 与普通拍脑袋的压缩技巧之间的根本区别。

第六幕：终于完成编码，究竟节省了多少空间？

现在我们把刚才构造出的树转换成编码表。一种可能的结果是：

字符	频次	Huffman 编码	长度
A	45	`0`	1
B	13	`101`	3
C	12	`100`	3
D	16	`111`	3
E	9	`1101`	4
F	5	`1100`	4

这些编码互不为前缀。因此接收方可以连续读取比特流，并唯一确定每个字符。

计算总编码长度

A 出现45次，每次1 bit：

45\times1=45

B、C、D 分别使用3 bit：

13\times3+12\times3+16\times3=123

E、F 使用4 bit：

9\times4+5\times4=56

因此总共：

45+123+56=\boxed{224\text{ bit}}

如果使用六种符号的固定长度编码，需要至少：

\lceil\log_2 6\rceil=3\text{ bit/符号}

100个字符就需要：

100\times3=300\text{ bit}

所以 Huffman 节省：

300-224=76\text{ bit}

相对固定长度符号编码，节省约25.3%。

编码长度对比

仅比较100个符号本身的编码长度，不包括编码表、文件头和其他开销。

查看图表数据

method	编码位数
固定3-bit编码	300
Huffman编码	224

固定编码

300 bit

Huffman 编码

224 bit

这里有一个容易被忽略的工程问题。我们刚刚计算的，是纯数据符号的编码长度。但在真实文件中，解码器还必须知道：

使用了哪些符号。
每种符号对应什么编码，或者如何重建编码树。
原始数据长度或结束位置。
最后一个字节中有多少填充位。

这些信息都会产生额外开销。所以，对于特别短的小文件，Huffman 压缩后的文件甚至可能比原文件更大。这也是压缩算法不可能脱离文件格式和具体数据讨论效果的原因。

第七幕：香农早就告诉我们，为什么压缩会有极限

现在回到1948年。香农研究的不只是怎样让常见符号使用短编码。他真正建立的是一套信息论基础。其中一个重要结论是：对于给定概率分布的离散无记忆信源，任何唯一可译的二进制符号编码，其平均码长不能低于信息熵。对于最优二元前缀编码，通常有：

\boxed{H\leq L<H+1}

其中：

$H$ ：信源熵。
$L$ ：平均码长。

这说明 Huffman 编码非常接近熵极限。但不意味着对所有概率分布都能恰好达到熵。例如，如果某个字符的概率是0.9，另一个字符的概率是0.1：二元 Huffman 仍然需要给两个字符分别分配至少一个比特的码字。平均码长是1 bit。但熵只有约0.469 bit。为什么不能再压缩？因为这里采用的是单符号、整数长度的前缀编码。如果考虑很长的符号序列，使用分组编码、算术编码或其他方法，可以让平均每个符号使用的比特数进一步接近熵。这就引出一个非常重要的概念：Huffman 对给定符号集及其概率分布的单符号前缀码是最优的，但不意味着它对任意长数据的所有无损编码方法都是最优的。

一场熵与码长的比较

二元信源：熵与 Huffman 码长

A 出现概率50%

理论熵下界

1.000

bit/符号

二元单符号 Huffman 码长

1.000

bit/符号

只要 A、B 都有正概率，两个不同的单符号前缀码都至少需要1 bit。概率越不均衡，符号编码的整数长度限制就越明显。

而这就是1948年香农的理论与1952年 Huffman 算法之间最深刻的联系。香农告诉我们：平均信息量由概率结构决定。Huffman 则告诉我们：在前缀编码的约束下，可以用一种非常简洁的算法找到最优编码树。

第八幕：1952年的算法，如何进入今天的 ZIP、JPEG 与网络系统？

当 Huffman 在1952年发表那篇四页论文时，他研究的是最小冗余编码的数学问题。但后来，人们发现这种方法非常适合与其他压缩技术结合。

ZIP 与 DEFLATE

经典 DEFLATE 算法结合了：

LZ77：寻找重复出现的字符串片段，用距离与长度表示重复内容。
Huffman 编码：对 LZ77 输出的符号进行变长熵编码。

因此，在 ZIP、gzip、PNG 等使用 DEFLATE 的场景中，Huffman 都是重要的底层组成部分。但要注意，ZIP 是一种容器格式，支持多种压缩方法，并不意味着每个 ZIP 文件都必然使用 DEFLATE。

JPEG

经典 JPEG 的基线编码流程中，图像首先经过颜色空间变换、离散余弦变换、量化等处理。最后，量化系数经过游程编码与 Huffman 熵编码。因此，JPEG 的主要有损压缩来自量化等步骤，而 Huffman 本身是无损的熵编码部分。这两个概念不能混淆。

视频与音频

现代视频和音频压缩，也广泛使用熵编码思想。不过，它们不一定采用传统 Huffman。例如，H.264 中就存在 CAVLC 和 CABAC 等不同熵编码技术，现代编码器会根据标准和使用场景采用更复杂的方法。这里最重要的历史继承关系是：压缩系统不断发展，但利用统计概率减少平均码长的思想始终没有改变。

第九幕：自己写一个 Huffman 编码器

我们现在把故事转化成 Python。假设输入是：

text = "AAAAABBC"

字符频率：

A：5次
B：2次
C：1次

我们希望构建 Huffman 树，然后生成编码表。使用最小堆，可以很自然地实现。

from collections import Counter
import heapq
from itertools import count


def build_huffman_codes(text):
    if not text:
        return {}

    frequencies = Counter(text)
    serial = count()

    heap = []

    for char, freq in frequencies.items():
        heapq.heappush(
            heap,
            (freq, next(serial), char)
        )

    if len(heap) == 1:
        only_char = next(iter(frequencies))
        return {only_char: "0"}

    while len(heap) > 1:
        freq1, _, left = heapq.heappop(heap)
        freq2, _, right = heapq.heappop(heap)

        parent = (left, right)

        heapq.heappush(
            heap,
            (freq1 + freq2, next(serial), parent)
        )

    root = heap[0][2]
    codes = {}

    def walk(node, prefix):
        if isinstance(node, str):
            codes[node] = prefix
            return

        left, right = node

        walk(left, prefix + "0")
        walk(right, prefix + "1")

    walk(root, "")
    return codes


text = "AAAAABBC"
codes = build_huffman_codes(text)

encoded = "".join(codes[c] for c in text)

print(codes)
print(encoded)

这个实现的思路是：先统计频率。将所有字符放入最小堆。每次取出两个频次最低的节点合并。直到形成一棵完整树。最后沿树遍历，把左边记为0、右边记为1。其中 serial 用于确保堆在频率相同时有明确的比较顺序，避免直接比较混合类型的节点。

一个有意思的细节

同一组字符频率，Huffman 生成的具体编码并不一定唯一。比如某两个字符频率相等，选择谁放左边、谁放右边，都可能得到同样最优的平均码长。因此：Huffman 保证编码长度最优，而不是保证所有实现都生成完全相同的比特序列。真实文件格式通常还需要明确编码表或使用规范化的 Canonical Huffman Code（规范 Huffman 编码），让编码与解码双方能够一致理解数据。

第十幕：一道真正能检验理解的挑战

假设我们有四个字符：

字符	频率
A	40
B	30
C	20
D	10

现在使用 Huffman 算法。第一次合并，一定选择频率最低的两个：C 和 D？不对，我们需要看清楚：D = 10。C = 20。所以第一次合并：

10+20=30

剩下三个节点：

30,\ 30,\ 40

这时又出现一个很有意思的现象。原本的 B 频率30。新形成的 CD 节点权重也为30。接下来合并这两个30，形成60。最后再合并40和60。最终一组可能的编码长度是：

A：1 bit
B：2 bit
C：3 bit
D：3 bit

平均码长：

0.4(1)+0.3(2)+0.2(3)+0.1(3)=1.9

这里我们用一个选择题检验你是否理解了 Huffman 的根本逻辑。

为什么 Huffman 每次选择权重最低的两个节点合并？

因为这样可以保证树中每个节点占用的内存最少因为低频字符可以放在较深的位置，从而使加权编码总长度最小因为所有字符最终都会获得相同长度的编码因为它能保证编码后的字符按字母顺序排列

尾声：一位学生的期末作业，成为整个数字时代的基础工具

1948年，Claude Shannon 在贝尔实验室提出了信息熵与通信理论的数学框架。他证明，通信中的统计不确定性可以用数学量描述，也为无损压缩的理论极限奠定了基础。1951年，David Huffman 还是 MIT 的研究生。他只是在尝试完成一份课程论文，避免参加期末考试。但当他终于想到“每次合并两个最低频率节点”的构造方式时，一个复杂的最优化问题突然获得了非常优雅的算法解。1952年，这个算法正式发表。几十年后，它进入压缩软件、图像编码和大量数字通信系统。如果把第九章的贪心算法与这一章放在一起，你会发现一个非常有趣的规律：Borůvka、Kruskal 和 Prim 通过选择安全的最小权重边，构造最低成本网络。Huffman 通过合并两个最小权重节点，构造最低平均码长的编码树。它们表面上解决完全不同的问题。但都依靠同一种数学精神：通过证明某个局部选择不会破坏全局最优，把一个复杂的优化问题变成一连串简单、可靠的步骤。这就是算法最迷人的地方。

第十二章知识总结

概念	核心思想
Information Entropy	衡量信源的平均不确定性
Prefix Code	任何码字都不是另一个码字的前缀
Huffman Coding	每次合并两个最低权重节点
Min Heap	高效取出最小的两个权重
Greedy Choice	局部选择可以证明保持最优
Weighted Path Length	频率乘以编码长度的总和
Source Coding Theorem	信息熵给出无损编码的理论界限
Canonical Huffman	使用规范规则表达相同码长结构

本章历史原始资料

Shannon（1948）：《A Mathematical Theory of Communication》第一部分 Shannon（1948）：论文第二部分 Huffman（1952）：《A Method for the Construction of Minimum-Redundancy Codes》《Scientific American》（1991）：Huffman 本人讲述课程作业的发明故事美国数学协会：Huffman 编码的发现历史

下一章预告

第十三章：从LZ77到ZIP——为什么重复的文字根本不需要再存一次？

1977年，两位以色列研究者 Jacob Ziv 和 Abraham Lempel 发表了一种全新的通用数据压缩方法。他们提出：如果一段文字已经在前面出现过，为什么还要把它重新保存一遍？能不能只记录：“回头看多少个字符，然后复制多长的一段？”这就是 LZ77 算法的核心。1978年，他们又提出另一种思想，发展出 LZ78。此后，LZW、DEFLATE、ZIP、gzip 等技术逐渐发展。下一章，我们会从 Ziv 与 Lempel 在以色列理工学院的真实研究经历出发，研究字典压缩技术是如何诞生的，以及它为什么成为现代文件压缩的重要基础。最精彩的地方是：Huffman 用更短的编码表示高频符号，而 LZ77 则让整段重复内容都不必再次出现。