技术
字典压缩算法 40 年演进史:从 LZ77 到 Zstandard 的技术脉络
📅 2026-07-21 · ✍️ 闪压技术团队 · ⏱ 6 分钟阅读
引言:为什么我们还在用 1977 年的算法
1977 年,Abraham Lempel 和 Jacob Ziv 发表了两篇论文,提出了 LZ77 和 LZ78 算法。40 多年过去了,今天你电脑里的 ZIP、PNG、PDF、HTTP 响应、数据库备份——几乎所有无损压缩场景,底层仍然是 LZ77 及其变体。
这不是因为没有新算法,Snappy、LZ4、Zstandard、Brotli 都是近 10 年的新成果。但 LZ77 的"滑动窗口 + 字典匹配"思想,至今仍是压缩算法的事实标准。
本文从 LZ77 讲起,梳理字典压缩 40 年的演进脉络,重点讲清楚:
- 每个算法的核心思想
- 它解决了什么问题 / 引入了什么权衡
- 现代系统怎么选
LZ77:一切的开端
核心思想
把数据看作一个流,维护一个固定大小的滑动窗口(通常是 32KB)。当读到新数据时,回头看滑动窗口里有没有匹配,有的话输出"(距离,长度)"而不是原文。
一个具体例子
原文:
the quick brown fox jumps over the lazy dog the quick brown fox
第二段 "the quick brown fox" 在前面出现过,所以可以编码成"回退 43 字节,拷贝 19 字节"。这样:
- 原始:19 字节 × 8 = 152 bit
- LZ77:距离(假设 2 字节) + 长度(假设 1 字节)= 24 bit
- 压缩比:6.3 倍
关键洞察
LZ77 之所以成功,是因为它捕捉了真实数据中最常见的冗余模式:重复出现。文本里的常见词、代码里的重复结构、二进制里的固定头部——这些都是滑动窗口能高效匹配的。
局限
- 滑动窗口不能太大(否则匹配搜索太慢)
- 对"局部重复"友好,对"长距离重复"无能为力
- 不压缩随机数据(几乎全是噪声,匹配不上)
LZ78:从窗口到字典
改进点
LZ77 的滑动窗口是无状态的——每次匹配只看不远的过去。LZ78 改为维护一个全局字典:
- 每次读入数据,看字典里有没有匹配
- 有就扩展匹配,没就把"前缀+新字符"作为新条目加入字典
与 LZ77 的对比
| 维度 | LZ77 | LZ78 |
|---|---|---|
| 字典范围 | 最近 N KB(滑动) | 整个历史(无界) |
| 匹配粒度 | 任意长度连续串 | 必须从字典条目开始 |
| 内存占用 | O(窗口大小) | O(字典条目数) |
| 适合场景 | 局部重复多 | 长距离重复多 |
重要性
LZ78 启发了整个"LZW 家族"——LZW 是 LZ78 的一个变体,在 1984 年被引入 GIF 格式。你看的每一个 GIF 图片,背后都是 LZ78 在工作。直到 2023 年,Twitter 还因为 GIF 的 LZW 专利过期发布过一篇技术博客。
Deflate:ZIP 的心脏
为什么是 Deflate
LZ77 输出的是"(距离,长度)"对,这本身还需要再压缩。Deflate 把 LZ77 和霍夫曼编码结合:
- LZ77 把数据转成"字面量"和"指针"两种符号
- 霍夫曼编码给高频符号短编码,低频符号长编码
- 输出比特流
关键贡献
- 算术编码 vs 霍夫曼:Deflate 选择霍夫曼是为了速度和专利安全(算术编码当时有专利)
- 预定义码表:RFC 1951 给出了常用码表,压缩器不需要从头算
- 可分块:Deflate 流可以分块,每块独立压缩,适合流式场景
影响
Deflate 是 ZIP、gzip、zlib、PNG、PDF、HTTP Content-Encoding 的默认算法。截至 2026 年,全球互联网超过 60% 的压缩流量仍然是 Deflate。
LZ4 / Snappy:速度优先
时代背景
2010 年前后,Google、Facebook 这类公司面临一个问题:CPU 越来越便宜,磁盘 I/O 和网络带宽仍然是瓶颈——但压缩速度太慢,反而成了新瓶颈。
LZ4 (2011) 和 Snappy (2011, Google) 应运而生,核心思想是牺牲压缩率换速度。
设计哲学
- LZ4:压缩 ~500 MB/s/核,解压 ~2 GB/s/核
- Snappy:压缩 ~250 MB/s/核,解压 ~500 MB/s/核
- 对比 Deflate gzip:压缩 ~25 MB/s/核,解压 ~200 MB/s/核
LZ4 比 gzip 快 20 倍,但压缩率只差 20-30%。
适用场景
| 场景 | 选 LZ4 / Snappy |
|---|---|
| 数据库存储引擎 | RocksDB / LevelDB 用 Snappy |
| 消息队列 | Kafka 推荐 LZ4 |
| 内存缓存 | Redis 4.0+ 支持 LZ4 压缩 |
| 实时日志 | Flume / Logstash 默认 Snappy |
Zstandard:压缩率与速度的甜点
2016 年,Yann Collet 在 Facebook 发布 Zstandard
它的目标是:压缩率接近或超过 Deflate,速度接近 LZ4。
核心创新
- 有限状态熵编码(FSE):比霍夫曼更精细的概率建模,接近算术编码的压缩率但速度更快
- 字典训练(Dictionary Training):可以离线从样本数据训练出专用字典,显著提升小文件压缩率
- 多级别(level 1-22):从"极致速度"到"极致压缩率"可调
性能数据(Zstd level 3 vs gzip level 6)
| 维度 | gzip -6 | zstd -3 |
|---|---|---|
| 压缩速度 | 25 MB/s | 330 MB/s |
| 解压速度 | 200 MB/s | 940 MB/s |
| 压缩率 | 2.7x | 2.8x |
| 字典加成 | ❌ | ✅ (小文件可到 5x) |
现状
- Linux kernel 4.14+ 内置 zstd
- Facebook 全公司存储引擎换 zstd
- HTTP 协议新增
Content-Encoding: zstd(2024 RFC 8478) - 闪压 v2.0 默认压缩格式
Brotli:为 HTTP 而生
Google 2015 年发布 Brotli
目标场景是HTTP 静态资源压缩(HTML/CSS/JS/字体),与 zstd 不同的是,它专门优化了文本压缩。
关键差异
- 预定义字典内置了英文字母、HTML 标签、CSS 属性、JS 关键字等高频 token
- 压缩率比 gzip 高 20-30%
- 速度比 gzip 慢一些,但解压速度很快
适用场景
- 几乎所有 CDN 默认开 Brotli(Cloudflare、Akamai、Fastly)
- 浏览器全部支持(Chrome 50+, Firefox 44+, Safari 11+)
算法选择决策树
需要压缩什么?
│
├── 通用文件(批量、不确定类型)
│ ├── 磁盘/存储 → Zstandard(平衡最好)
│ └── 网络传输 → Brotli(如果客户端支持)或 Zstandard
│
├── 大文件 / 冷数据(很少解压)
│ └── Zstandard level 19-22(极致压缩率)
│
├── 实时数据流 / 消息队列
│ └── LZ4(速度优先)
│
├── HTTP 静态资源
│ └── Brotli(浏览器原生支持最好)
│
└── 小文件(几十 KB)
└── Zstandard + 训练字典(可提升到 5x 压缩率)
闪压的算法选择
闪压 v2.0 默认采用 Zstandard level 3,理由是:
- 压缩率/速度比最优:330 MB/s 压缩速度,用户无感知
- 解压极快:940 MB/s,老电脑也能秒开
- 生态成熟:Linux kernel、Windows、macOS 全平台原生支持
- 未来可扩展:level 1-22 可调,字典训练在 v2.1 路线图
我们对比过 5 种主流算法(Zstd / Brotli / LZ4 / gzip / bzip2),最终 Zstd 综合胜出。详细对比表见 深入理解文件压缩算法:从 LZ77 到 Zstandard。
写在最后
字典压缩 40 年的演进,本质是三方的权衡:
- 压缩率(越小越好)
- 速度(越快越好)
- 内存占用(越小越好)
没有任何算法能在三个维度同时最优。LZ77 提供了起点,Deflate 让压缩普及,LZ4 解决了速度瓶颈,Zstandard 把三者平衡到了新高度。
下一个突破点会在哪?可能是 AI 预测式压缩——用模型预测下一个字节的概率,再编码。这种方案在文本上已经接近理论极限(LLM 压缩文本可达 10x+),但通用性和速度还是瓶颈。拭目以待。
如果你对压缩算法底层感兴趣,推荐读 字典压缩算法 40 年演进史:从 LZ77 到 Zstandard 的技术脉络——这是有损压缩领域的另一场算法军备竞赛。