1 历史与背景
1.1 压缩界的“神雕侠侣”
Jacob Ziv与Abraham Lempel是以色列理工学院的两位教授。他们在1970年代相继提出LZ77和LZ78算法，奠定了现代无损压缩的理论基础。这两位科学家的合作被称为压缩界的“绝代双骄”，因为他们的工作直接催生了后续几乎所有主流通用压缩算法。
1.2 从1977到未来：一场压缩革命
1977年，Ziv与Lempel发表论文《A Universal Algorithm for Sequential Data Compression》，提出了LZ77。次年，他们又推出LZ78。这两篇论文开启了字典编码的新纪元。此后，LZSS（1982）、LZW（1984）等变体相继问世，使LZ家族枝繁叶茂。时至今日，从ZIP压缩包到GIF动图，从网络传输到存储系统，LZ系列算法依然是底层基础设施不可或缺的一部分。
2 核心思想
2.1 字典编码：查字典的快乐
字典编码的核心是“用索引代替重复”。压缩器维护一个动态构建的“字典”，每当遇到已出现过的字符串，就输出该字符串在字典中的位置和长度，而不是原始字符序列。解压时，根据相同的字典重建原始数据。这样，重复内容越多的数据，压缩效果越好。
2.2 两种字典流派：滑动窗口 vs 无限生长
LZ77采用滑动窗口字典：只记录最近一段历史（如32KB），窗口随数据流向前移动。LZ78则构建一个无限增长的字典，将新遇到的字符串作为新条目加入字典，并赋予递增的索引。前者适合局部重复性强的数据（如文本），后者更能应对全局重复模式。
3 主要算法
3.1 LZ77
3.1.1 基本原理
LZ77将输入数据视为一个字符流。它使用一个“滑动窗口”作为历史缓冲区，窗口内的字符都是已经编码过的。编码器在窗口中寻找与当前待编码字符串匹配的最长子串，然后输出一个三元组。
3.1.2 三元组与滑动窗口
三元组的形式为 (偏移量, 匹配长度, 下一个字符)。偏移量表示匹配子串距离当前位置的字符数，匹配长度是子串的长度，第三个元素是匹配结束后第一个未匹配的原始字符。解压时，仅需根据偏移和长度从已解码数据中复制字符，再添加第三个字符即可。
3.1.3 局限与改进
LZ77的主要局限是滑动窗口大小固定：窗口太小则远距离重复无法捕捉；窗口太大则查找变慢。此外，三元组中必须包含下一个字符，即使没有匹配也要消耗一个字符的存储。
3.1.3.1 回溯查找的性能瓶颈
在滑动窗口中查找最长匹配需要对窗口内容进行逐字符比较，时间复杂度为O(窗口大小 × 匹配长度)。早期实现使用朴素搜索，性能较差。后来的改进如哈希链、二叉树等数据结构显著提升了查找速度。
3.2 LZ78
3.2.1 基本思想
LZ78不再使用滑动窗口，而是构建一个不断增长的字典。字典初始为空（或仅包含所有单字符）。编码时，读取最长的已在字典中的前缀，输出其字典索引，然后将该前缀加上下一个字符作为一个新条目加入字典。
3.2.2 字典生长策略
字典条目按顺序编号（通常从0或1开始）。每个新条目由“已有条目索引 + 新字符”构成。解码器同步构建相同的字典，因此只需根据索引就能恢复原始数据。字典会持续增长，理论上可以压缩任意长度的重复模式。
3.3 LZSS
3.3.1 对LZ77的优化
LZSS（Lempel-Ziv-Storer-Szymanski）在1982年提出，核心改进是引入“标志位”来区分匹配和原始字符。当匹配长度小于某个阈值（例如2或3）时，直接输出原始字符更划算，否则才输出匹配对。
3.3.2 标志位与贪婪匹配
输出格式变为 (标志位, 偏移量, 长度) 或 (标志位, 字符)。解码器根据标志位决定如何解析后续比特。LZSS还常使用贪婪匹配策略：总是选择当前窗口中最长的匹配，不考虑上下文影响。这一优化使LZSS成为许多高效压缩工具（如ZIP中的deflate算法）的基础。
3.4 LZW
3.4.1 从LZ78到LZW的进化
LZW（Lempel-Ziv-Welch）由Terry Welch在1984年改进LZ78而来。它将输出从“索引+字符”改为仅输出字典索引（去掉了第三个字符），并且字典初始化时包含所有单字符。编码时，一旦匹配成功就输出当前前缀的索引，然后将前缀加下一个字符加入字典。解码过程对称。
3.4.2 出场便封神：GIF的依赖
LZW因其简洁高效，被选为GIF图像格式的压缩算法（1987年），随后也用于TIFF和PDF。GIF的流行让LZW家喻户晓，哪怕后来遭遇Unisys公司的专利争议，也未能撼动其历史地位。至今，LZW仍是许多嵌入式场景的首选。
3.5 其他变体
3.5.1 LZMA
LZMA（Lempel-Ziv-Markov chain algorithm）是7-Zip项目中使用的算法，结合了LZ77的大字典（可达4GB）和自适应二进制算术编码。它通过多级匹配、范围编码和状态机大幅提升压缩率，但速度较慢。
3.5.2 LZ4
LZ4是主打极致速度的LZ77变体，牺牲压缩率换取极快的压缩和解压速度（可达GB/s级别）。它使用简单的哈希链查找匹配，输出格式为“令牌+字面量+匹配对”，广泛用于数据库日志、实时通信和文件系统压缩。
4 应用领域
4.1 文件压缩（ZIP、gzip）
ZIP格式采用deflate算法（基于LZ77和哈夫曼编码），gzip也使用deflate。几乎所有操作系统都原生支持ZIP/gzip压缩，从软件分发到备份存档，LZ家族无处不在。
4.2 图像格式（GIF、PNG）
GIF使用LZW，PNG使用deflate。PNG中的deflate对图像数据（经过差分滤波）进行压缩，效果优秀。这两种格式的互联网普及，使得LZ系列算法成为浏览器和图像处理软件的标配。
4.3 网络协议（HTTP压缩）
HTTP协议支持Content-Encoding: gzip或deflate，服务器和浏览器可以协商使用LZ类算法压缩网页内容，显著减少传输字节数。这项技术在HTTP/1.1中成为标准，至今仍是Web性能优化的重要手段。
5 性能与局限
5.1 压缩率 vs 速度的相爱相杀
LZ77/LZ78家族天然存在压缩率与速度的权衡。窗口越大、字典越复杂，压缩率越高，但计算开销也越大。例如，LZMA可达到接近算术编码的压缩率，但速度远慢于LZ4。实际应用中，用户根据场景选择适合的变体：存储备份用高压缩率，实时通信用高速度。
5.2 对数据类型的敏感度
5.2.1 高重复数据：如鱼得水
文本、代码、结构化日志等含有大量重复模式的数据，LZ算法能获得极佳的压缩比（可达5:1甚至更高）。比如英文小说中的常见单词和短语会在滑动窗口中反复出现。
5.2.2 随机数据：巧妇难为无米之炊
对于加密数据、已压缩数据、杂乱噪声等，重复模式极少，LZ算法不仅无法压缩，甚至可能因为字典开销导致体积略微膨胀。这类数据的压缩率接近1:1或更差。
6 文化影响
6.1 算法界的“祖传代码”
LZ系列算法从1977年诞生至今，几乎所有主流操作系统、编程语言标准库、文件格式规范中都有其实现。它们被一遍遍地重构、优化、移植，成为真正的“祖传代码”——每一代程序员都在继续使用和改进。
6.1.1 为什么几乎所有系统都在用？
原因有三：一是算法成熟且无专利障碍（早期专利已过期）；二是实现简单、资源占用低；三是针对不同场景的变体丰富，从嵌入式MCU到超级计算机都能找到合适版本。这使得LZ成为压缩领域事实上的“通用货币”。
6.2 梗：LZ你压缩了吗？
在网络社区中，程序员常调侃“LZ你压缩了吗？”来戏谑那些没做数据压缩就传输大文件的场合。也有表情包将Ziv和Lempel的形象与“压缩/解压”关联起来。这个梗既指具体的算法，也泛指一切数据压缩行为，反映了LZ在开发者文化里的深入人心。