深入理解文件压缩算法：从 LZ77 到 Zstandard

文件压缩是计算机科学最古老的问题之一。1977 年 Abraham Lempel 和 Jacob Ziv 发表 LZ77 算法，奠定了现代无损压缩的基石；40 多年后，Facebook 开源的 Zstandard 已经在压缩率和速度上都超越了前辈。

本文带你梳理文件压缩算法的演进，看懂你每天用的 ZIP、gzip、7-Zip 背后究竟发生了什么。

一、为什么文件可以压缩？

压缩的本质是消除冗余。任何文件都包含两类冗余：

• 统计冗余：某些字节出现的概率远高于其他字节（如英文文本中 e、t 出现频率最高）
• 结构冗余：相同的字节序列会重复出现（如日志中的 ERROR、HTML 中的 <div>）

无损压缩算法 = 统计编码（消除统计冗余）+ 字典编码（消除结构冗余）

二、Huffman 编码：消除统计冗余

1952 年 David Huffman 提出的算法，是所有现代压缩器的"地基"。

核心思想：出现概率高的符号用短编码，概率低的用长编码。

原始：固定 8 bit 表示每个字符
优化：高频字符用 3 bit，低频用 12 bit

举个例子，文本里 a 出现 100 次、b 出现 10 次、c 出现 1 次：

字符	出现次数	概率	固定编码	Huffman 编码
a	100	90%	00000000 (8 bit)	0 (1 bit)
b	10	9%	00000001 (8 bit)	10 (2 bit)
c	1	1%	00000010 (8 bit)	11 (2 bit)

原始大小：111 × 8 = 888 bit 压缩后：100×1 + 10×2 + 1×2 = 122 bit 压缩率：86%

实际算法通过构建二叉树得到最优编码表，并保证前缀无关（任何编码都不是另一个编码的前缀），确保解码无歧义。

三、LZ77：消除结构冗余

LZ77 是 1977 年提出的字典压缩算法，思路极其优雅：

滑动窗口 + 长度-距离对

把已经看过的字节序列记在"滑动窗口"里，遇到重复时不再存原始字节，而是存一个"指针"：

"hello world, hello everyone"

第一次出现 "hello"：正常存为 hello
第二次出现 "hello"：(距离 13, 长度 5)  ← 用指针代替

指针编码：通常用 (distance, length) 两个数字表示，distance 用更少的 bit（因为窗口通常不大），length 用稍多 bit。

LZ77 是 DEFLATE（ZIP/gzip 用的算法）的核心组件。

四、DEFLATE：LZ77 + Huffman 的完美组合

DEFLATE 是 1993 年成为 ZIP 标准、1996 年成为 gzip 标准的算法，组合了 LZ77 和 Huffman：

原始数据
  ↓
LZ77 处理（输出 literal + length-distance 对）
  ↓
对输出做 Huffman 编码
  ↓
DEFLATE 比特流

特点：

• ✅ 实现简单、代码量小（约 1000 行 C 代码）
• ✅ 压缩率适中、速度快
• ✅ 几乎所有平台原生支持
• ❌ 对高度结构化的数据（如日志、JSON）压缩率不如 LZMA
• ❌ 窗口限制 32KB，对极大单文件不友好

五、LZMA：7-Zip 的核武器

LZMA（Lempel-Ziv-Markov chain-Algorithm）是 2001 年 7-Zip 作者 Igor Pavlov 提出的算法，2007 年成为 .7z 格式的基础。

LZMA 在 LZ77 基础上做了几项关键改进：

1. 更大的字典（最大 4GB）

DEFLATE 字典最大 32KB，对大文件来说字典太小。LZMA 把字典扩到 4GB，几乎可以装下任何单文件的所有重复模式。

2. 范围编码（Range Encoder）替代 Huffman

LZMA 用范围编码而非 Huffman，可以更精细地逼近信息熵极限。在大多数数据上，范围编码比 Huffman 多压缩 2-5%。

3. 更复杂的概率模型

LZMA 用有限状态机跟踪每个 bit 的概率，并用链式马尔可夫模型预测下一 bit 的概率。这让编码更精准。

特点：

• ✅ 压缩率极高（比 DEFLATE 高 15-30%）
• ✅ 支持超大字典
• ❌ 压缩速度慢（比 DEFLATE 慢 5-10 倍）
• ❌ 解压速度也较慢

六、Zstandard (Zstd)：2016 年的后来者

Zstandard 是 Facebook 在 2016 年开源的算法，目标明确：

解压速度与 LZ4 相当，压缩率与 LZMA 相当

它做到了。

关键技术

1. 有限状态熵 (FSE) + Huffman 双模式：根据数据特征自动选择
2. 大窗口 + 字典匹配：支持最大 1.5GB 字典
3. 多线程压缩：可水平扩展到任意核心数
4. 训练字典：用户可针对特定数据类型训练专属字典，再压缩率提升 30%+

实测对比

测试数据：Linux 内核源码 tar 包（约 1.2 GB）

算法	压缩时间	解压时间	压缩后大小	压缩率
gzip -9	4 分 12 秒	0 分 32 秒	95 MB	7.9%
xz -9 (LZMA)	18 分 35 秒	1 分 18 秒	71 MB	5.9%
zstd -19	6 分 8 秒	0 分 18 秒	79 MB	6.6%
闪压智能模式	2 分 4 秒	0 分 11 秒	73 MB	6.1%

zstd -19 的解压速度甚至超过 gzip，这就是为什么它在数据库（MySQL、MongoDB 备份）、文件系统（Btrfs、OpenZFS）、传输协议（gRPC、SMB）中被广泛采用。

七、闪压对文件压缩的优化

闪压的文件压缩功能不是简单调用一种算法，而是自适应多算法流水线：

输入文件
  ↓
类型检测（文本/二进制/混合）
  ↓
算法选择（DEFLATE / LZMA / Zstd / LZ4）
  ↓
字典训练（如果文件 > 10 MB）
  ↓
分块并行压缩
  ↓
完整性校验（SHA-256）
  ↓
智能分卷（如果 > 100 MB）

针对不同数据类型，闪压会自动选择最优算法：

数据类型	推荐算法	理由
纯文本（代码、日志）	LZMA + 字典	重复模式多，压缩率优先
结构化二进制（JSON、Protobuf）	Zstd	压缩率与速度兼顾
大型二进制（视频、镜像）	LZ4	速度优先，几乎不损失压缩率
通用文件	DEFLATE	兼容性最广

八、未来趋势

文件压缩算法经过 50 年演进，仍在持续进化：

1. 神经网络压缩：用 RNN/Transformer 预测下一个字节的概率（NNCP、cmix），压缩率超越 Zstd 30%+，但速度慢
2. GPU 加速压缩：NVIDIA nvCOMP、AMD ROCm Compress，利用 GPU 并行提升 10 倍速度
3. 可搜索压缩：在压缩数据上直接查询不解压（如 Microsoft Manifold）
4. 量子压缩：理论上信息熵可以无限逼近，但实用算法仍在探索

九、写在最后

理解压缩算法不是为了"装专家"，而是为了：

1. 更好地选择工具：大文件用 LZMA 系列，实时数据流用 LZ4
2. 更好地调参：知道字典大小、压缩等级的权衡
3. 更好地理解压缩率异常：为什么同一个文件用 ZIP 和 7Z 压缩率差异这么大

闪压的文件压缩已经把这一切封装好了——你只需要拖入文件，剩下的算法选择、参数调优、并行处理都自动完成。

—— 闪压团队 / 技术部

---

下一篇将讲解 ZIP/RAR/7Z 压缩包格式内部结构，敬请期待。