1948年，贝尔实验室的克劳德·香农发表了一篇题为《通信的数学理论》的论文。这篇论文定义了一个叫做"熵"的概念：对于任何信息源，存在一个不可逾越的压缩极限。无论你用什么方法，都无法把数据压缩到这个极限以下而不丢失信息。
这个结论听起来像是给压缩技术判了死刑——但恰恰相反，它为接下来的五十年技术演进划定了战场。
三元组的诞生
1977年，海法市的两位以色列研究人员Abraham Lempel和Jacob Ziv在IEEE Transactions on Information Theory上发表了一篇论文。他们提出了一个叫做LZ77的算法。
LZ77的核心思想出奇简单：如果你要压缩的数据里出现了重复的内容，就不要再存储一遍，而是记下"我在前面某处见过这个"。
具体来说，LZ77把数据分成两部分：一个"搜索缓冲区"和一个"向前看缓冲区"。当处理到某个位置时，算法在搜索缓冲区里寻找与当前位置最长的匹配。如果找到了，就输出一个三元组：(距离, 长度, 下一个字符)。距离告诉解码器"往回看多少"，长度告诉它"复制多少"，下一个字符则是在匹配结束后的那个字符。
比如要压缩字符串"abracadabra"，当处理到第二个"abra"时，算法会发现在前面10个字符的位置有一个完全相同的序列。于是它输出(10, 4, ?)，意思是"从当前位置往回数10个字符，复制4个字符"。解码时，解码器照做就行，根本不需要知道原始数据是什么样子。
这个设计的天才之处在于：解码器不需要任何预先准备。它只需要从数据开头顺序读取，边读边解。这个特性在今天看来理所当然，但在当时是一个重大突破——它意味着压缩数据可以自解释。
但LZ77也有一个致命缺陷：它的输出不一定比输入更短。如果你要编码的是"abc"，三元组可能是(0, 0, ‘a’)、(0, 0, ‘b’)、(0, 0, ‘c’)，每个三元组都比原始字符占更多空间。后来LZSS（Lempel-Ziv-Storer-Szymanski）对此做了改进：只有当匹配能节省空间时才使用三元组，否则直接输出原始字符。
霍夫曼的补刀
LZ77解决了一个问题：如何消除重复数据的冗余。但它留下了另一个问题：如何高效编码那些三元组？
1952年，MIT的大卫·霍夫曼还是罗伯特·法诺的学生。法诺给学生出了一个选择：要么写期末论文，要么参加期末考试。霍夫曼选择了论文，题目是"寻找最高效的二进制编码方法"。
据说霍夫曼苦思冥想了几个月都毫无进展，直到放弃的那一刻，答案突然出现在脑海里。他的方法是这样的：把所有符号按出现频率排序，然后不断合并频率最低的两个符号，形成一棵二叉树。出现频率高的符号离树根近，编码短；出现频率低的符号离树根远，编码长。
这比香农和法诺之前提出的自顶向下方法更优。霍夫曼证明了这种方法产生的编码是最优的前缀编码——没有其他前缀编码能用更少的比特表示同样的数据。
但霍夫曼编码有一个根本限制：每个符号必须用整数个比特表示。如果一个符号的出现概率是90%，理论上它应该用 -log₂(0.9) ≈ 0.152 个比特来编码。但霍夫曼编码最少只能给它1个比特。这看起来不是大问题，但在高压缩比场景下，这些"浪费"的分数比特会累积成可观的开销。
DEFLATE：一个时代的开始
1993年，一个叫Phil Katz的程序员发布了PKZIP 2.0。这个版本引入了一个叫做DEFLATE的算法，它把LZ77和霍夫曼编码组合在一起。
DEFLATE的工作流程是：首先用LZ77（实际上是LZSS变体）把数据转换成一系列literal和(距离, 长度)对，然后用霍夫曼编码对这些输出进行压缩。它为literal/长度和距离分别维护霍夫曼树，允许动态生成最优的编码表。
这个组合非常成功。DEFLATE在压缩比和速度之间取得了良好的平衡，而且没有专利障碍——这与当时流行的LZW算法（被Unisys持有专利）形成了鲜明对比。LZW的专利纠纷导致了GIF格式的没落和PNG格式的诞生，也让Unix社区从compress转向了gzip。
2016年，Facebook工程师团队在官方博客中总结了DEFLATE的地位：“作为当前数据压缩的标准，DEFLATE是Zip、gzip和zlib的核心算法。二十年来，它在速度和空间之间提供了令人印象深刻的平衡，因此几乎用于每台现代电子设备。”
但DEFLATE的设计受到1990年代硬件的限制。它的滑动窗口最大只有32KB——在那个内存以MB计算的年代，这是一个合理的选择。今天，即使移动设备也有数GB内存，32KB的窗口显然不够用。
熵编码的进化
要理解DEFLATE之后的进展，需要先理解熵编码的演进。
霍夫曼编码的整数比特限制，催生了一种更强大的编码方法：算术编码。1979年，IBM的研究人员开发了这种方法。它不把每个符号映射到一个固定的比特序列，而是把整个消息编码成0到1之间的一个实数。
比如要编码"AABABC"，假设A出现3次、B出现2次、C出现1次。算术编码会根据这些概率，不断把当前区间细分。最终整个消息被编码成一个很窄的区间，输出该区间内任意一个数的二进制表示即可。
理论上，算术编码可以任意接近香农极限。但它有两个实际问题：第一，实现复杂，需要高精度算术；第二，曾经被专利覆盖（虽然现在已过期）。
2013年，Jarek Duda发表了关于非对称数字系统（ANS）的论文。这种方法达到了算术编码的压缩效率，但计算复杂度接近霍夫曼编码。Yann Collet基于ANS实现了有限状态熵（FSE）编码器，成为Zstandard算法的核心组件。
FSE的关键创新是使用预计算的查找表。编码和解码过程只需要简单的查表和移位操作，不需要算术编码中的除法。这使得它既快又准确。
LZ4：速度至上
2009年，一个叫Yann Collet的法国人开始做一件奇怪的事。他是公司的项目经理，日常工作是管理Excel表格和协调团队。但在业余时间，他开始为HP-48图形计算器编写压缩算法。
Collet注意到，当时大多数压缩算法研究者都在追求更高的压缩比，速度只是次要考虑。他想：如果反过来呢？如果把速度作为首要目标，同时尽量不牺牲太多压缩比？
这个思路产生了LZ4。LZ4的核心设计哲学可以用一句话概括：宁可少压缩一点，也要快。
LZ4对LZ77做了几个关键简化：
首先，它限制了匹配搜索的范围。DEFLATE会在整个滑动窗口里寻找最长匹配，LZ4则使用更激进但有界的搜索策略。这牺牲了一些压缩比，但大大加快了压缩速度。
其次，它优化了输出格式。LZ4的输出格式被设计成对现代CPU友好：顺序访问、分支预测友好、易于向量化。Collet后来在采访中解释：“我只是意识到这个东西可以以每秒1GB的速度解压。这太疯狂了。我完全没想到。”
2011年，就在Collet准备开源LZ4的前两周，Google开源了Snappy——一个设计理念几乎相同的压缩算法。Snappy立刻获得了大量关注，因为Google内部已经在BigTable等系统中广泛使用它。
但LZ4有一个Snappy没有的优势：Collet花了几个月时间深入理解为什么LZ4这么快，然后让它更快。六个月后，LZ4在所有性能指标上都超越了Snappy。
今天，LZ4被广泛应用于需要极快压缩/解压的场景：Hadoop、Linux内核、PlayStation游戏、大型强子对撞机的数据处理系统。Unity游戏引擎把它作为默认压缩选项，无数开发者在不知情的情况下使用着它。
Zstandard：寻求平衡
2016年，Facebook发布了Zstandard（zstd）。这个算法代表了Collet十年压缩研究的集大成：既要有好的压缩比，又要有快的速度。
Zstandard的设计有几个关键创新：
更大的滑动窗口。DEFLATE受限于32KB窗口，zstd则可以使用数MB甚至数GB的窗口。在内存充足的现代系统上，这意味着能找到更远处的重复模式。
有限状态熵编码。zstd使用FSE替代霍夫曼编码，可以更接近香农极限。对于高概率符号，FSE可以用分数比特编码，避免了霍夫曼编码的浪费。
Repcode建模。这是一种专门处理结构化数据的技术。很多数据（比如日志、JSON、代码）包含大量"几乎相同"的序列：只在少数位置有差异。Repcode建模通过跟踪最近几次匹配的距离，可以更高效地编码这些"重复但略有不同"的模式。
为现代CPU设计。zstd的格式设计考虑了分支预测、缓存友好性和指令级并行。Collet称之为"无分支设计"——尽量避免条件分支，因为分支预测失败会导致流水线清空，代价高昂。
官方基准测试显示了zstd的优势：在相同压缩比下，压缩速度比DEFLATE快3-5倍；在相同压缩速度下，压缩比高10-15%；解压速度几乎是DEFLATE的两倍。更重要的是，zstd提供了22个压缩级别，允许精细的时间/空间权衡，而解压速度在所有级别上都保持稳定。
Brotli：为Web而生
2013年，Google开始开发Brotli压缩算法。与zstd的通用设计不同，Brotli专门针对Web内容优化。
Brotli最独特的特性是内置了一个约120KB的静态字典，包含13,504个单词和短语。这个字典覆盖了HTML、CSS、JavaScript中常见的内容：type="text/javascript"、<div class="、function()等。
当LZ77找不到匹配时，Brotli会尝试在静态字典中查找。字典中的词可以通过一个短引用来表示，通常比原始文本节省很多空间。字典还支持120种变换：大小写转换、添加前缀后缀、截断等。这使得字典的有效覆盖范围扩大到约160万个变体。
Cloudflare的工程师在博客中展示了这个特性的威力：对于一个1KB左右的JSON记录，使用字典的压缩比从2.8倍提升到6.9倍。
Brotli还使用了二阶上下文建模。传统的霍夫曼编码为每个符号计算一个全局概率，但上下文建模会根据前面的符号调整当前符号的概率估计。比如在HTML中，<后面的字符概率分布与普通文本不同。这种更精确的概率估计带来更好的压缩效果，代价是更慢的压缩速度。
实际测试中，Brotli对JavaScript文件的压缩比gzip好14%，对HTML好21%，对CSS好17%。但压缩速度较慢，尤其是高质量级别。因此，Brotli的推荐使用场景是"压缩一次、解压多次"——静态资源预压缩，而不是动态内容实时压缩。
字典压缩：小数据的救星
传统压缩算法有一个共同的弱点：它们需要"历史数据"来学习模式。对于很小的数据（比如几百字节的JSON消息），没有足够的历史来建立统计模型，压缩效果很差。
这个问题催生了字典压缩。Zstandard提供了训练模式：用户提供一组样本数据，算法从中提取最常见的模式，生成一个字典。之后压缩同类数据时，可以加载这个字典作为"预设的历史"。
Facebook的基准测试显示：对于GitHub用户数据（每条记录约1KB），使用字典后压缩比从2.8倍提升到6.9倍。更关键的是，压缩和解压速度同时提高了——因为预设字典让算法更快找到匹配。
2024年，HTTP工作组发布了Compression Dictionary Transport规范，允许浏览器和服务器共享压缩字典。这意味着Web资源可以使用预定义字典进行更高效的压缩。Chrome的实现显示，这项技术可以显著减少重复访问时的传输量。
选择的艺术
面对众多压缩算法，如何选择？答案取决于具体场景的约束。
速度优先场景：实时通信、内存数据库、高频日志写入。选择LZ4或Snappy。它们的压缩比可能只有2倍左右，但压缩和解压速度可以超过500MB/s，解压甚至能超过1GB/s。对于I/O密集型应用，这个速度意味着压缩几乎不会成为瓶颈。
存储优先场景：冷数据归档、备份、发布包。选择zstd高压缩级别或xz/LZMA。压缩可能很慢，但解压速度仍然可以接受，而存储空间节省显著。
Web传输场景：HTTP响应、静态资源。对于动态内容，使用zstd级别1-3或Brotli级别4-5，平衡压缩比和CPU开销。对于静态资源，可以预先使用Brotli级别10-11或zstd级别18-22压缩。
小数据场景：消息队列、数据库记录、RPC调用。考虑使用字典压缩。为每种数据类型训练专门的字典，压缩比可以从2倍提升到5-8倍。
内存受限场景：嵌入式系统、移动设备。注意算法的内存消耗。zstd的字典大小可配置，LZ4解压只需要输入输出缓冲区。避免使用xz等需要大内存的算法。
从技术演进的角度看，压缩算法的发展遵循一个清晰的模式：先有理论基础（香农熵），然后有基础实现（LZ77、霍夫曼），接着是工程优化（DEFLATE），最后是针对特定场景的专门化（LZ4追求速度、Brotli针对Web、zstd寻求平衡）。
香农在1948年证明的极限仍然存在。我们只是在不断接近这个极限的过程中，找到了更多兼顾速度、内存、复杂度的方案。压缩算法的历史，本质上是人类在有限计算资源下，不断逼近理论最优的工程实践史。
参考资料
- Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal.
- Ziv, J., & Lempel, A. (1977). A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory.
- Huffman, D. A. (1952). A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE.
- Deutsch, P. (1996). DEFLATE Compressed Data Format Specification. RFC 1951.
- Collet, Y. (2011-2016). LZ4 - Extremely Fast Compression Algorithm. GitHub Repository.
- Collet, Y., & Facebook Team. (2016). Smaller and Faster Data Compression with Zstandard. Facebook Engineering Blog.
- Alakuijala, J., & Szabadka, Z. (2016). Brotli Compressed Data Format. RFC 7932.
- Duda, J. (2013). Asymmetric Numeral Systems: Entropy Coding Combining Speed of Huffman with Accuracy of Arithmetic Coding. arXiv:1311.2540.
- History of Lossless Data Compression Algorithms. IEEE ETHW.
- ClickHouse Documentation. Compression in ClickHouse.
- Cloudflare Blog. Brotli Compression Using a Reduced Dictionary.
- CoRecursive Podcast. From Project Management to Data Compression Innovator - Interview with Yann Collet.
- Phoronix. Zstd Compression For Btrfs & Squashfs Set For Linux 4.14.
- Silesia Compression Corpus. Standard benchmark dataset for compression algorithm evaluation.
- Mozilla Developer Network. Compression Dictionary Transport.