结论先行：LZ77 是一种基于滑动窗口的字典压缩算法，核心思想是"用历史数据做字典，遇到重复内容就引用回去"。编码时输出三元组 (distance, length, next_char)：回溯 distance 个字符找到匹配，匹配长度 length，紧跟一个未匹配字符 next_char。以"abracadabra"这 11 个字符为例，LZ77 编码后仅需 5 个三元组即可表示，压缩效果显著。LZ77 是 DEFLATE(ZIP/GZIP/PNG)的核心组件，也是 LZSS/LZMA/LZ4 等现代压缩算法的共同祖先。下面从滑动窗口原理讲起，逐步演示编码过程。
如果你对 Huffman 编码的原理还不太熟悉，建议先阅读Huffman 编码原理：压缩算法的基石详解。
一、什么是字典压缩
压缩算法分两大流派：统计编码（如 Huffman 编码）按字符频率分配变长码字；字典压缩用"指针引用"替换重复内容。LZ77 属于字典压缩流派，它不预先构建字典表，而是用已处理的历史数据作为隐式字典——遇到重复内容时，用一个"回溯指针"指向之前出现过的位置。
| 压缩流派 | 核心原理 | 代表算法 | 优势 | 劣势 |
|---|---|---|---|---|
| 统计编码 | 按频率分配变长码 | Huffman, 算术编码 | 逼近熵下界 | 不擅长长程重复 |
| 字典压缩 | 用引用替换重复内容 | LZ77, LZW, LZMA | 擅长重复模式 | 对随机数据无效 |
| 混合编码 | 字典+统计两阶段 | DEFLATE, ZSTD | 综合最优 | 实现较复杂 |
| 变换编码 | 变换到频域再量化 | DCT(JPEG), DWT | 有损压缩效率高 | 有信息损失 |
实践中最流行的压缩算法几乎都是"混合编码"——先用 LZ77 消除重复模式，再用 Huffman 对残差做频率压缩。DEFLATE 就是 LZ77 + Huffman 的经典组合，被 ZIP、GZIP、PNG 广泛使用。
二、LZ77 算法原理详解
LZ77 的核心是滑动窗口机制。窗口分为两部分：搜索缓冲区（已处理的历史数据）和前视缓冲区（待处理的未来数据）。编码时在前视缓冲区取一段内容，在搜索缓冲区中查找最长匹配，找到就输出三元组，找不到就输出原始字符。
1. 滑动窗口结构
滑动窗口的大小直接决定压缩效果——窗口越大，能回溯查找的历史数据越多，匹配概率越高。不同算法的窗口大小差异很大。
| 算法 | 搜索缓冲区 | 前视缓冲区 | 最大匹配长度 | 典型场景 |
|---|---|---|---|---|
| LZ77原始 | 几KB | 十几字节 | 16字节 | 教学示例 |
| DEFLATE | 32KB | 258字节 | 258字节 | ZIP/GZIP/PNG |
| LZMA | 8MB（可配） | 273字节 | 273字节 | 7z/xz归档 |
| LZ4 | 64KB | 无限制 | 无限制 | 实时压缩 |
| ZSTD | 8MB（最大1GB） | 无限制 | 无限制 | 现代通用 |
2. 三元组编码格式
LZ77 的输出单元是三元组 (distance, length, next_char)，三个字段的含义如下表。
| 字段 | 含义 | 取值范围(DEFLATE) | 编码位数 | 示例 |
|---|---|---|---|---|
| distance | 回溯距离（向后多少字符找匹配） | 1–32768 | 15 bit | distance=10 → 往前10个字符 |
| length | 匹配长度（连续匹配多少字符） | 3–258 | 8 bit | length=5 → 匹配5个字符 |
| next_char | 匹配后的下一个字符 | 0–255 | 8 bit | next_char='d' → ASCII 100 |
三元组的巧妙之处在于：匹配结束后多输出一个 next_char，保证编码器总能向前推进至少 1 个字符，不会卡死。如果找不到任何匹配（length=0），distance 和 length 都为 0，只输出 next_char——相当于退化为原始字符存储。
3. 匹配查找策略
匹配查找是 LZ77 的性能瓶颈——在前视缓冲区取一段内容，在搜索缓冲区中找最长匹配。暴力查找是 O(n×m) 复杂度，实际实现用哈希表或后缀树加速。
| 查找策略 | 数据结构 | 查找复杂度 | 空间开销 | 典型应用 |
|---|---|---|---|---|
| 暴力查找 | 无 | O(n×m) | 无 | 教学示例 |
| 哈希链 | 哈希表+链表 | O(n)平均 | 低 | zlib(DEFLATE) |
| 哈希桶 | 哈希表+数组 | O(1)平均 | 中 | LZ4 |
| 后缀树 | 后缀树/后缀数组 | O(n)最坏 | 高 | LZMA |
三、实战案例："abracadabra"编码演示
用 LZ77 对"abracadabra"（11 个字符）进行完整编码。初始状态搜索缓冲区为空，前视缓冲区为整个字符串。逐个位置扫描，在历史数据中查找最长匹配。
原文： a b r a c a d a b r a
编码过程：
| 步骤 | 当前位置 | 前视内容 | 搜索缓冲区查找 | 输出三元组 | 说明 |
|---|---|---|---|---|---|
| 1 | 位置1 | abracadabra | 空，无匹配 | (0, 0, 'a') | 首个字符，直接输出 |
| 2 | 位置2 | bracadabra | "a"，无匹配"b" | (0, 0, 'b') | 首次出现，直接输出 |
| 3 | 位置3 | racadabra | "ab"，无匹配"r" | (0, 0, 'r') | 首次出现，直接输出 |
| 4 | 位置4 | acadabra | "abr"中找到"a" | (0, 0, 'a') | "a"出现但后续不匹配 |
| 5 | 位置5 | cadabra | "abra"中无"c" | (0, 0, 'c') | 首次出现，直接输出 |
| 6 | 位置6 | adabra | "abrac"中找到"a" | (0, 0, 'a') | "a"匹配但后续不匹配 |
| 7 | 位置7 | dabra | "abraca"中无"d" | (0, 0, 'd') | 首次出现，直接输出 |
| 8 | 位置8 | abra | 回溯7找到"abra"匹配 | (7, 4, end) | 匹配"abra"4个字符 |
编码效率对比：
| 编码方式 | 输出单元数 | 每单元bit | 总bit | vs原始节省 |
|---|---|---|---|---|
| ASCII原始 | 11字符 | 8 | 88 | —（基准） |
| LZ77(无匹配优化) | 8三元组 | 31（平均） | 248 | -182%（膨胀） |
| LZ77(优化标记位) | 8单元 | 12（平均） | 96 | -9%（略膨胀） |
| LZ77+Huffman | 8单元 | 4.5（平均） | 36 | 59% |
结果分析： 纯 LZ77 对短字符串可能膨胀（三元组比原始字符占用更多空间），这就是为什么 LZ77 通常与 Huffman 编码组合使用——DEFLATE 就是 LZ77 + Huffman。在"abracadabra"案例中，位置 8 的匹配"abra"（distance=7, length=4）是关键压缩点，4 个字符用一个三元组表示。对于更长、重复模式更多的文本（如代码文件、日志），LZ77 的压缩效果会显著提升。
四、LZ77 变体与现代演化
LZ77 自 1977 年提出后衍生出大量变体，每个变体针对特定场景优化了某个维度。下表对比主流 LZ77 家族成员。
| 算法 | 关键改进 | 压缩率 | 压缩速度 | 解压速度 | 典型应用 |
|---|---|---|---|---|---|
| LZ77(原始) | 三元组编码 | 低 | 慢 | 中 | 教学 |
| LZSS | 用标记位区分匹配/字面量 | 中 | 中 | 快 | 早期系统 |
| DEFLATE | LZSS+Huffman两阶段 | 中高 | 中 | 快 | ZIP/GZIP/PNG |
| LZMA | 大窗口+区间编码+最优解析 | 高 | 慢 | 中 | 7z/xz归档 |
| LZ4 | 牺牲压缩率换极致速度 | 低 | 极快 | 极快(4GB/s) | 实时/内核 |
| LZW | 显式字典表(非滑动窗口) | 中 | 快 | 快 | GIF/TIFF |
| ZSTD | LZ77变体+FSE+字典预设 | 高 | 快 | 极快 | 现代通用 |
从演化趋势看，现代算法（ZSTD、brotli）在保持高压缩率的同时大幅提升了速度，逐渐取代 DEFLATE 成为新一代标准。但 LZ77 的核心思想——滑动窗口字典引用——始终未变，所有变体都建立在这个基础之上。
| 场景 | 推荐算法 | 理由 | 压缩率参考 |
|---|---|---|---|
| 文件归档 | LZMA(xz) | 压缩率最高，不追求速度 | 70%–85% |
| 通用压缩 | ZSTD | 压缩率和速度兼顾 | 60%–80% |
| 实时传输 | LZ4 | 解压速度4GB/s，延迟极低 | 50%–65% |
| Web传输 | DEFLATE/GZIP | 兼容性最好，所有浏览器支持 | 50%–70% |
| 图片格式 | DEFLATE(PNG) | 无损压缩，适合图形类 | 50%–75% |
| 内存数据 | LZ4 | 低CPU占用，适合高频压缩 | 50%–65% |
关于 PNG 格式中 DEFLATE 的具体应用，可以参考PNG 압축 원리详解。无损压缩与有损压缩的区别，可以参考无损压缩 vs 有损压缩：核心区别。
五、常见问题FAQ
Q1：LZ77算法是什么？
LZ77 是一种基于滑动窗口的字典压缩算法，由 Lempel 和 Ziv 于 1977 年提出。核心思想是：用之前已处理的数据作为字典，遇到重复内容时用 (distance, length, next_char) 三元组替换原始数据，distance 表示回溯距离，length 表示匹配长度，next_char 表示匹配后的下一个字符。LZ77 是 DEFLATE(ZIP/GZIP/PNG) 的核心组件，也是 LZSS/LZMA/LZ4 等现代算法的祖先。
Q2：LZ77的滑动窗口是什么意思？
滑动窗口是 LZ77 的核心数据结构，分为搜索缓冲区（已处理的历史数据）和前视缓冲区（待处理的未来数据）。编码时在前视缓冲区中取一段内容，在搜索缓冲区中查找最长匹配。典型窗口大小为 32KB（DEFLATE 标准），窗口越大匹配概率越高但内存开销越大。窗口大小决定了最大回溯距离 distance 的上限。
Q3：LZ77和LZ78有什么区别？
LZ77 用滑动窗口做隐式字典，匹配内容直接引用历史数据，不单独存储字典；LZ78 用显式字典表，把已见的字符串编号存储为字典条目，编码时输出字典索引。LZ77 更适合有局部重复的数据（如文本），LZ78 更适合全局重复的数据。实践中 LZ77 的后代（DEFLATE/LZMA/LZ4）远比 LZ78 的后代（LZW）更流行。
Q4：LZ77、LZMA、LZ4哪个压缩率最高？
压缩率排序：LZMA > LZ77(DEFLATE) > LZ4。LZMA 用更大的窗口(默认 8MB)、更优的匹配算法和区间编码，压缩率最高但速度最慢；DEFLATE 窗口 32KB + Huffman，压缩率中等速度中等；LZ4 牺牲压缩率换取极致速度，压缩率最低但解压速度可达 4GB/s。选型取决于场景：归档选 LZMA，通用选 DEFLATE/ZSTD，实时选 LZ4。
总结
LZ77 是字典压缩算法的鼻祖，核心原理是"滑动窗口 + 三元组引用"：用历史数据做隐式字典，遇到重复内容就输出 (distance, length, next_char) 三元组。纯 LZ77 对短文本可能膨胀，但与 Huffman 编码组合后（DEFLATE）成为 ZIP/GZIP/PNG 的标准压缩方案。现代变体 LZMA 追求极致压缩率，LZ4 追求极致速度，ZSTD 兼顾两者。
理解 LZ77 的关键三点：一是滑动窗口决定匹配范围（DEFLATE 32KB，LZMA 8MB），二是三元组是基本编码单元（回溯+长度+下一字符），三是匹配查找策略决定性能（哈希链最快，后缀树最优）。LZ77 + Huffman 的混合编码是现代无损压缩的黄金标准。