4、无损压缩算法（二）：LZ77与LZSS算法原理，以及如何在字库压缩中落地
上一章我们聊了游程编码和哈夫曼编码。说实话，这两种方法对付规则数据还行，但遇到真正的字库——几千个汉字，每个字16×16点阵，重复模式又散又乱——就有点力不从心了。
这时候就该LZ77家族登场了。我最早接触LZ77是在做一款温控器的字库时，Flash只剩4KB，字库却要装6KB的内容。当时急得团团转，后来用LZSS硬是塞进去了。嗯，今天就把这套方法掰开揉碎讲清楚。
4.1 LZ77：滑动窗口的智慧
LZ77的核心思想其实很简单：用指针代替重复数据。你写文章时，如果前面已经写过「嵌入式GUI」，后面再出现时你会怎么写？大概率会写「见上文」对吧？LZ77干的就是这事。
它维护一个滑动窗口，窗口分两部分：
- 搜索缓冲区：已经编码过的历史数据
- 前瞻缓冲区：待编码的后续数据
编码器在搜索缓冲区里找前瞻缓冲区的最长匹配。找到了，就输出一个(距离, 长度)对；没找到，就原样输出字符。
举个例子：假设搜索缓冲区里有「ABCDEF」，前瞻缓冲区是「CDEFGH」。最长匹配是「CDEF」，长度4，距离2（从当前位置往前数2个字符）。输出就是(2, 4)，而不是4个字符。
解码时更简单：拿着(距离, 长度)，从已解码数据里往前数距离个字符，复制长度个字符就行。说白了就是一次内存拷贝。
4.2 LZSS：LZ77的改良版
LZ77有个明显的问题：如果匹配长度只有1个或2个字符，输出(距离, 长度)反而比直接输出字符更占空间。你想想看，一个(距离, 长度)至少占2字节，而一个字符可能只占1字节。
LZSS的改进就是加了一个最小匹配长度阈值。我习惯设成3。匹配长度小于3时，直接输出原始字符；大于等于3时，才输出(距离, 长度)对。
另外，LZSS还引入了一个标志位来区分当前输出的是原始字符还是(距离, 长度)对。解码器先读标志位，再决定怎么解析后续数据。
| 特性 | LZ77 | LZSS |
|---|---|---|
| 最小匹配长度 | 无限制（1字节也编码） | 通常≥3 |
| 输出类型 | 全部是(距离,长度)对 | 原始字符或(距离,长度)对 |
| 标志位 | 无 | 有（1bit区分类型） |
| 压缩率 | 短匹配时可能膨胀 | 更稳定，不易膨胀 |
| 解码速度 | 快 | 稍慢（需解析标志位） |
我在项目中几乎只用LZSS。LZ77那个短匹配膨胀的问题，在嵌入式字库里特别致命——字库里经常出现只有1-2个像素差异的相邻字符，LZ77会输出大量短匹配对，压缩率反而变差。
4.3 字库压缩的落地实战
好了，理论讲完了。咱们直接看怎么把LZSS用到字库上。我以16×16点阵字库为例，每个汉字32字节。
4.3.1 数据预处理
字库数据有个特点：相邻字符之间往往有相似性。比如「啊」和「阿」，左边都是「口」字旁。但LZSS的滑动窗口有限，如果按字符顺序排列，相似字符可能隔得很远。
我建议做一步重排序：
- 按部首分组：相同部首的字放一起
- 按笔画数排序：笔画相近的字结构更相似
- 必要时做差分编码：后一个字减去前一个字，让重复区域变成0
经验之谈：我曾经把GB2312的6763个汉字按拼音排序后压缩，压缩率只有45%。改成按部首+笔画排序后，压缩率降到了32%。排序方式对压缩率的影响，比你想象的大得多。
4.3.2 窗口大小选择
窗口大小直接影响压缩率和内存占用。我给出几个参考值：
| 窗口大小 | 内存占用 | 压缩率（16×16字库） | 适用场景 |
|---|---|---|---|
| 2KB | 2KB + 256B | 约40% | RAM极少的MCU |
| 4KB | 4KB + 512B | 约35% | 主流MCU |
| 8KB | 8KB + 1KB | 约30% | RAM较充裕 |
| 16KB | 16KB + 2KB | 约28% | 性能较好的MCU |
我个人习惯用4KB窗口。再大收益就不明显了，而且解码时占用的RAM也更多。你想想看，MCU的RAM本来就金贵，为了多省那5%的Flash空间多占4KB RAM，不值当。
4.3.3 解码器实现
解码器必须轻量。我贴一个我在STM32上跑过的核心代码：
// LZSS解码器核心函数
// in: 压缩数据指针, out: 解压数据指针
void lzss_decode(uint8_t *in, uint8_t *out, uint32_t out_len) {
uint32_t out_pos = 0;
uint32_t in_pos = 0;
uint8_t flag = 0;
uint8_t flag_bit = 0;
while (out_pos < out_len) {
// 每8个输出消耗1个标志字节
if (flag_bit == 0) {
flag = in[in_pos++];
flag_bit = 8;
}
flag_bit--;
if (flag & 0x01) { // 标志位为1：原始字符
out[out_pos++] = in[in_pos++];
} else { // 标志位为0：(距离,长度)对
uint8_t dist_lo = in[in_pos++];
uint8_t dist_hi = in[in_pos++];
uint16_t dist = (dist_hi << 8) | dist_lo;
uint8_t len = in[in_pos++];
// 从已解码数据中复制
uint32_t src_pos = out_pos - dist;
for (uint8_t i = 0; i < len; i++) {
out[out_pos++] = out[src_pos++];
}
}
flag >>= 1;
}
}
注意：这段代码假设(距离,长度)对占3字节（2字节距离+1字节长度）。实际项目中你可以根据窗口大小调整。比如4KB窗口，距离用12bit，长度用4bit，拼成2字节，能省不少空间。
4.4 压缩率实测数据
我拿一个实际项目的数据给大家看看。字库是GB2312的6763个汉字，16×16点阵，总共216KB。
| 压缩方法 | 压缩后大小 | 压缩率 | 解码速度（STM32F103 @72MHz） |
|---|---|---|---|
| 不压缩 | 216KB | 100% | 0ms（无需解码） |
| 游程编码 | 162KB | 75% | 约2ms |
| 哈夫曼编码 | 108KB | 50% | 约8ms |
| LZSS（4KB窗口） | 76KB | 35% | 约5ms |
| LZSS + 重排序 | 65KB | 30% | 约5ms |
看到没？LZSS加上重排序，压缩率从35%降到了30%。解码速度只比游程编码慢一点，但压缩率好太多了。
4.5 避坑指南
做LZSS字库压缩，有几个坑我踩过，你们别重蹈覆辙：
- 窗口大小别贪大：我曾经试过32KB窗口，压缩率只比8KB好了2%，但解码时RAM占用多了24KB。MCU直接罢工了。
- 注意对齐：ARM Cortex-M系列对非对齐访问有惩罚。解码时尽量保证
(距离,长度)对是2字节对齐的，否则速度会慢30%以上。 - 标志位别用bit field：C语言的bit field在不同编译器下布局不同。我建议手动用位运算，虽然代码丑点，但可移植性好。
- 测试边界情况：全0的字（空白字符）和全1的字（全黑字符）要单独测试。我遇到过全0字压缩后反而变大的情况，后来加了最小匹配长度才解决。
4.6 知识体系总览
下面这张图把LZ77/LZSS的核心逻辑和字库落地方案串起来了，建议保存下来对照着看。
这张图从左到右展示了完整的压缩流程：原始字库先做预处理，然后选择LZ77或LZSS编码，配置合适的窗口大小，最后用轻量解码器还原。我个人强烈建议走右边那条绿色路线——LZSS加4KB窗口，这是性价比最高的方案。