4、无损压缩算法（下）：LZ77、LZSS、Huffman编码原理，以及Deflate算法在PNG中的应用
上一节我们把游程编码和LZW聊透了。今天继续往下挖——LZ77、LZSS、Huffman编码，以及它们怎么组合成Deflate算法，最终在PNG里落地。
说实话，这部分内容我当年啃了很久。不是因为难，而是因为资料太散。今天我把它们串起来讲，你跟着走一遍，应该就能明白为什么PNG能压得那么小。
LZ77：滑动窗口的鼻祖
LZ77的核心思想很简单：用已经出现过的数据片段，替换当前要编码的数据。说白了就是——你之前写过一遍的东西，我记下来，下次再写就只写个引用。
它维护一个滑动窗口，窗口分两部分：
- 查找缓冲区：已经编码过的数据，供匹配用
- 前瞻缓冲区：待编码的数据
编码时，算法在前瞻缓冲区里找最长匹配，然后输出一个三元组：(距离, 长度, 下一个字符)。
举个例子：
输入字符串 abracadabrad，当处理到第二个"abra"时，查找缓冲区里已经有"abra"了。LZ77会输出 (4, 4, 'd')，意思是：往前4个字符，复制4个字符，然后下一个字符是'd'。
我在一个嵌入式GUI项目里用过LZ77的变体。当时Flash空间只剩8KB，字体数据压完刚好塞下。嗯，那种感觉就像拼图最后一块正好卡进去。
LZSS：LZ77的改良版
LZ77有个问题——如果匹配长度太短，输出三元组的开销反而比直接存原文还大。你想想看，一个(距离, 长度, 下一个字符)至少占3个字节，而原文可能就2个字节。
LZSS的改进很直接：加一个标志位，判断这次是输出三元组还是直接输出原文。
| 特性 | LZ77 | LZSS |
|---|---|---|
| 输出格式 | 固定三元组 | 标志位 + 三元组或原文 |
| 匹配长度阈值 | 无 | 通常 ≥ 3 |
| 压缩率 | 中等 | 更高 |
| 解码复杂度 | 低 | 略高 |
我曾经在一个资源受限的MCU上移植过LZSS解压器。窗口大小设成4KB，匹配阈值设成3，效果最好。设成2反而会膨胀——这个坑我踩过。
避坑指南：LZSS的窗口大小不是越大越好。窗口越大，匹配概率越高，但查找时间也越长。在嵌入式系统里，我建议窗口大小不要超过8KB，否则解压速度会明显变慢。
Huffman编码：给数据分配变长码
Huffman编码的思路很朴素：出现频率高的符号用短码，出现频率低的符号用长码。这样整体数据量就降下来了。
具体做法是：
- 统计每个符号的出现频率
- 构建Huffman树（每次合并两个最小频率的节点）
- 从根到叶子遍历，左0右1，得到每个符号的编码
举个例子，假设有4个符号：A(50%), B(25%), C(15%), D(10%)：
符号 频率 Huffman编码
A 50% 0
B 25% 10
C 15% 110
D 10% 111平均码长 = 0.5×1 + 0.25×2 + 0.15×3 + 0.1×3 = 1.7位/符号。如果用固定2位编码，需要2位/符号。节省了15%。
我记得第一次手动构建Huffman树时，画了整整一页纸。后来写了个小程序自动生成，才发现这东西其实很机械——就是不断找最小的两个节点合并。
小技巧：在嵌入式系统里，Huffman树可以预计算好，存成静态表。这样解码时就不需要重建树了，省内存省时间。
Deflate算法：LZSS + Huffman的黄金组合
Deflate算法是Phil Katz在1990年代设计的，后来成为PNG、gzip、zlib的核心压缩算法。它的结构很清晰：
- 第一步：用LZSS做重复数据消除，输出
(距离, 长度)对或原文 - 第二步：对LZSS的输出做Huffman编码，进一步压缩
Deflate支持两种Huffman模式：
- 动态Huffman：根据数据动态构建Huffman树，需要额外存储树信息
- 静态Huffman：使用预定义的Huffman树，不需要额外存储
动态Huffman压缩率更高，但需要更多计算。静态Huffman适合小数据块。
下面这张图展示了Deflate的完整流程：
Deflate在PNG中的应用
PNG使用Deflate作为其核心压缩算法。具体流程是：
- 过滤：对图像行做差分处理（比如减去上一行的像素值），让数据更可压缩
- Deflate压缩：对过滤后的数据做LZSS + Huffman
- 封装：加上PNG的chunk结构（IHDR、IDAT、IEND等）
PNG的IDAT chunk里存的就是Deflate压缩后的数据流。解码时反过来：先解Deflate，再逆过滤，得到原始像素。
关键参数：PNG使用的Deflate窗口大小固定为32KB。这个值在嵌入式系统里可能偏大，所以有些轻量级PNG解码器会限制窗口大小，或者用流式解压。
我曾经在一个只有64KB RAM的MCU上做过PNG解码。32KB的窗口直接占了一半内存，剩下的还要存像素缓冲区。最后只能分块解码——一次只解一小块图像，解完就输出。虽然慢了点，但能跑起来。
三种算法的对比
| 算法 | 核心思想 | 压缩率 | 速度 | 内存需求 |
|---|---|---|---|---|
| LZ77 | 滑动窗口匹配 | 中 | 快 | 窗口大小 |
| LZSS | LZ77 + 标志位优化 | 中高 | 中 | 窗口大小 |
| Huffman | 变长编码 | 高（配合LZSS） | 中 | 频率表/树 |
| Deflate | LZSS + Huffman | 很高 | 中慢 | 窗口 + 树 |
选型建议：如果你的嵌入式系统内存紧张，可以考虑只用LZSS，跳过Huffman那一步。压缩率会降一些，但内存占用能减半。我有个项目就是这么干的——效果还不错。
好了，无损压缩算法的核心就这些。LZ77和LZSS解决的是重复数据的问题，Huffman解决的是频率分布的问题，Deflate把它们组合起来，就成了PNG的基石。理解这些，你就能在嵌入式系统里做出更明智的压缩选型决策。