文件压缩的工作原理：Huffman Coding、LZ77 和 DEFLATE 详解
每个开发者都用过压缩文件。解压一个软件包、返回 gzip 编码的响应，或者导出 PNG——压缩无时无刻不在幕后运作。但大多数教程都绕开了一个核心问题：这究竟为什么有效？ 为什么一个 500 KB 的文本文件可以压缩到 180 KB 而不丢失任何一个字节，但对 ZIP 文件再次压缩却几乎无效？
答案藏在信息论和几个优雅的算法之中。本文将带你走进真实的机制：从香农熵到 Huffman 树，再到支撑 ZIP、gzip 和 PNG 的 DEFLATE 格式。
为什么文件可以被压缩
文件之所以可以压缩，是因为它们包含冗余——模式、重复内容以及可预测的序列，其携带的信息量比原始字节数所暗示的要少得多。
举个简单的例子：字符串 AAAAAAAAAA（十个 A）在 ASCII 中占 10 个字节。但其信息含量微乎其微——你可以用"十个 A"来完整描述它。压缩算法做的正是这件事：用更短的描述替换冗长、重复的数据。
真实文件中充满了这类冗余：
- 中文文本会反复使用常见词语和字符组合。"的"、"是"、"在"的出现频率远高于罕见字符。
- 源代码具有高度重复的结构：
function、return、const、缩进、空行。 - 位图图像在水平方向上包含大量相同或几乎相同的像素——尤其是纯色区域。
- 日志文件会将时间戳、主机名和状态码重复数千次。
数据越冗余，就越容易压缩；越接近随机，压缩就越困难。
熵：压缩的硬性上限
Claude Shannon 在 1948 年发表的论文《通信的数学理论》引入了一种精确衡量信息含量的方式：熵，以比特为单位。
香农熵回答了这样一个问题：平均而言，表示这个数据源中的一个符号实际需要多少比特？
对于符号为 s₁, s₂, ..., sₙ、概率为 p₁, p₂, ..., pₙ 的信源，公式如下：
H = -Σ pᵢ × log₂(pᵢ)
实际含义如下：假设一个文件只含两种字符——A（出现概率 90%）和 B（出现概率 10%）。
H = -(0.9 × log₂(0.9)) - (0.1 × log₂(0.1))
H = -(0.9 × -0.152) - (0.1 × -3.322)
H ≈ 0.137 + 0.332
H ≈ 0.469 比特/符号
朴素编码每个符号使用 1 比特（A 用 0，B 用 1）。但熵告诉我们，理论最小值仅为每符号 0.469 比特——不到一半。优秀的压缩算法可以逼近这个极限。
再看一个真正随机的文件，每个字节值（0–255）以相等的概率（1/256）出现：
H = -(256 × (1/256) × log₂(1/256))
H = log₂(256) = 8 比特/字节
每字节 8 比特——最大熵。没有冗余可以利用。这就是为什么无法进一步压缩 ZIP 文件：它已经接近最大熵，每个比特都在传递信息，没有任何模式可以消除。
游程编码：最简单的形式
在介绍更复杂的算法之前，游程编码（RLE）清楚地展示了核心思路。
RLE 用一个计数值和符号来替换一串重复符号：
原始： AAABBBBBCCDDDDDD
RLE： 3A 5B 2C 6D
原始：16 个字符。编码后：8 个字符。减少了 50%。
RLE 用于传真传输（CCITT Group 3/4）、BMP 文件，以及更复杂格式内部的子步骤。其缺点显而易见：对没有长重复序列的数据效果很差。字符串 ABABABAB 没有重复游程，因此 RLE 会在每处添加计数值 1，反而使其变大。
正是这个缺点推动了更复杂方法的出现。
Huffman Coding：为常见符号分配更短的编码
标准 ASCII 中，每个字符无论出现频率如何，都使用 8 比特。Huffman Coding 打破了这一假设：频繁出现的符号获得更短的编码，罕见的符号获得更长的编码，从而降低平均编码长度，缩小文件体积。
构建 Huffman 树
以字符串 AABBBCCCC（9 个字符）为例，统计频率：
第一步： 将每个符号放入以其频率为权重的叶子节点。
[A:2] [B:3] [C:4]
第二步： 反复将权重最小的两个节点合并为一个父节点，其权重为两者之和，直到只剩一棵树。
合并 [A:2] 和 [B:3] → 父节点 [AB:5]：
[AB:5]
/ \
[A:2] [B:3]
[C:4]
合并 [C:4] 和 [AB:5] → 根节点 [ABC:9]：
[ABC:9]
/ \
[C:4] [AB:5]
/ \
[A:2] [B:3]
第三步： 通过遍历树来分配编码：左边 = 0，右边 = 1。
计算节省的比特数
使用 Huffman 编码对 AABBBCCCC 进行编码的总成本：
A × 2 次 × 2 比特 = 4 比特
B × 3 次 × 2 比特 = 6 比特
C × 4 次 × 1 比特 = 4 比特
合计 = 14 比特
使用固定 8 比特 ASCII：
9 个字符 × 8 比特 = 72 比特
14 比特对比 72 比特——在这个简单示例中减少了 81%。实际应用中节省比例较小，但原理相同。对于中文文本，仅用 Huffman 通常可以将每字符从 8 比特压缩到较低水平（考虑到 Unicode 的多字节特性）。
关键洞见：Huffman 编码是前缀无关的。没有任何编码是另一编码的前缀，因此解码器无需分隔符就能无歧义地还原原始数据流。树的结构本身存储在压缩文件的头部，以便解码器重建它。
LZ77 和 LZ78：利用重复序列
Huffman Coding 作用于单个符号的频率，却忽略了一大类冗余：重复序列。源代码中的 function 每次出现都占 8 个字节。如果能用指向第一次出现位置的指针来替换后续出现，就能节省大量空间。
Abraham Lempel 和 Jacob Ziv 在 1977 年和 1978 年的论文中正是描述了这一点，由此诞生了 LZ77 和 LZ78。
LZ77：滑动窗口压缩
LZ77 维护一个滑动窗口——最近处理过的数据的缓冲区。编码器在处理新数据时，会向后搜索窗口，寻找与接下来内容的最长匹配。如果找到匹配，就输出反向引用 (偏移量, 长度) 而不是字面字节。
以编码字符串为例：
abcabc
处理 abc：没有历史数据，输出字面量 a、b、c。
处理第二个 abc：编码器向后找到 3 个位置之前的 abc，长度为 3。输出反向引用 (偏移量=3, 长度=3) 而不是三个字面字节。
解码器看到 (3, 3) 后，在输出缓冲区中回退 3 个位置并复制 3 个字节——完美还原 abc。
在实际实现中，匹配搜索受窗口大小限制（gzip 使用 32 KB 窗口）。更大的窗口能找到更多匹配，但需要更多内存和搜索时间。
反向引用 (偏移量, 长度) 通常只需 2–3 个字节。因此，用一个 2 字节的引用替换 10 字节的重复序列，可节省 8 个字节。匹配越长，压缩比越好。
LZ78 和 LZW
LZ78 构建一个显式的已遇模式字典，而不使用滑动窗口。LZW（Lempel-Ziv-Welch）是其衍生版本，因作为 GIF 压缩和 Unix compress 工具的算法而广为人知。LZW 将模式编码为单一字典索引，在编码和解码过程中动态扩展字典。
DEFLATE：LZ77 加 Huffman Coding
DEFLATE（定义于 RFC 1951）将 LZ77 和 Huffman Coding 串联使用：
- LZ77 阶段： 将重复序列替换为
(偏移量, 长度)反向引用，输出字面量和反向引用组成的数据流。 - Huffman 阶段： 对该数据流应用 Huffman Coding。频繁出现的字面量获得短编码；罕见的反向引用值获得更长的编码。
两种技术攻克不同类型的冗余。LZ77 消除长距离重复，Huffman Coding 再消除剩余数据中基于频率的冗余。两者结合所达到的压缩比，是任何一种单独算法无法实现的。
DEFLATE 数据以块为单位组织，每块可使用三种模式之一：
- 无压缩——用于压缩反而会使输出变大的数据（已是随机数据）
- 固定 Huffman 编码——使用预先约定的编码表，省去存储自定义树的开销
- 动态 Huffman 编码——针对当前块优化的自定义树，存储于块头部
动态模式用于大多数可压缩数据。编码器分析该块，构建最优 Huffman 树，将其存储在块的开头，然后用这棵树对数据进行编码。
DEFLATE 在真实文件格式中的应用
ZIP
ZIP 文件中的每个条目都独立存储，拥有自己的 DEFLATE 压缩数据流。这种逐条目压缩意味着你可以从 ZIP 中提取单个文件，而无需解压整个归档。ZIP 格式还支持"存储"模式（不压缩），用于已经压缩过的文件。
gzip
gzip 将单个 DEFLATE 数据流包裹在一个头部（魔数、操作系统、修改时间）和 CRC32 校验和中。它是 HTTP Content-Encoding: gzip 和 .tar.gz 归档的标准压缩格式。.gz 扩展名始终代表单个 DEFLATE 数据流。
PNG
PNG 通过 zlib 使用 DEFLATE 压缩像素数据。在压缩之前，PNG 会应用一个过滤步骤：将每行像素转换为与预测值的差值（增量编码）。这大大增加了 LZ77 可以利用的重复序列，显著提升压缩效果。对于典型的截图和图表，PNG 能压缩到原始像素数据大小的 20–50%。导出 PNG 的图像压缩工具都依赖这条处理链。
zlib
zlib 是 DEFLATE 的包装格式——它添加了两字节头部和 Adler-32 校验和。PDF 数据流在压缩嵌入内容时使用 zlib/DEFLATE（PDF 压缩通过重新压缩或移除这些数据流来减小文件大小）。HTTP、WebSockets 以及许多网络协议也使用 zlib。
JPEG：一种不同的方法
此处值得停下来说明，因为 JPEG 使用了截然不同的压缩策略——一种有意丢失数据的方式。
JPEG 对 8×8 像素块应用离散余弦变换（DCT），将像素值转换为频率分量（类似傅里叶变换）。高频分量——精细细节——随后被激进地量化（舍入为更粗糙的值或完全丢弃）。剩余系数用 Huffman Coding 编码，但有损量化步骤才是使 JPEG 比 PNG 小得多的关键。
代价是：JPEG 无法完美还原原始像素，而 PNG 可以。这就是有损与无损的本质区别，我们的有损与无损文件转换文章对此有深入探讨。
对于一张照片，质量为 80 的 JPEG 可能只使用无损 PNG 字节数的 10%。而对于有纯色和锐利边缘的截图，PNG 通常更胜一筹，因为 DCT 伪影清晰可见，而 DEFLATE 对平坦区域的压缩效果极佳。
为什么无法进一步压缩 ZIP 文件
这是一个常见的困惑点。如果压缩依靠寻找模式，那么对已压缩文件再次压缩为何收效甚微？
因为 DEFLATE 已经把工作做好了。一个压缩良好的 DEFLATE 数据流在统计上看起来是随机的——这是设计使然。反向引用和 Huffman 编码消除了所有可预测的模式。剩余的内容已接近数据的熵极限。
对其再次压缩，第二个压缩器既找不到重复游程（LZ77 找不到长匹配），也看不到频率偏差（Huffman 看到的几乎是均匀的符号分布）。熵已经在每字节 7.9+ 比特。没有任何东西可以再利用。
这也是为什么不应该压缩已压缩的媒体文件。把 JPEG 放入 ZIP，你只会付出 ZIP 的额外开销而没有任何体积收益。MP3、MP4、HEIC 同理——这些格式已经接近其熵上限。
算法对比
综合整理
对于一个经 gzip 压缩的文件，从原始数据到压缩字节的处理链如下：
- 输入： 原始字节流（如文本文件）
- LZ77： 使用 32 KB 滑动窗口搜索反向引用，输出字面量和
(偏移量, 长度)对组成的数据流 - Huffman Coding： 构建两棵树——一棵用于字面量/长度，一棵用于偏移量——并编码 LZ77 的输出
- DEFLATE 块： 将 Huffman 树和编码数据打包成一个或多个块
- gzip 包装： 在前面加上 gzip 头部，在后面附上 CRC32 和原始文件大小
- 输出：
.gz文件，对可压缩输入通常小 30–70%
解压过程严格逆向进行：解析 gzip 头部，从块头部读取并重建 Huffman 树，将 Huffman 数据流解码回 LZ77 标记，应用反向引用重建原始字节流。解压始终比压缩快，因为繁重的工作（搜索最优匹配、构建最优树）只需做一次。
关键要点
- 文件之所以可以压缩，是因为包含冗余——重复模式和频率偏斜的符号分布。
- 香农熵设定了绝对下限：真正随机的数据无法压缩，因为每个比特都已在传递信息。
- RLE 粗暴地处理重复，Huffman Coding 优雅地处理频率偏差，LZ77 处理长距离序列重复。
- DEFLATE 将 LZ77 和 Huffman 串联，这正是它超越任何单一算法的原因。它是 ZIP、gzip、PNG 以及 zlib 压缩 PDF 数据流的核心引擎。
- JPEG 采用了截然不同的方法：有损 DCT 量化后跟无损 Huffman，以牺牲像素精度换取显著的体积压缩。
- 压缩已压缩的文件毫无意义，因为良好的压缩会产生接近最大熵的输出。
理解这些算法，在选择格式、诊断意外的大文件或调试压缩管道时都会派上用场。下次使用 PDF 压缩、解压 ZIP 文件或导出 PNG 进行图像压缩时，你将清楚地知道软件在对你的比特做什么。