经典算法回顾：LZ77、LZ78、Huffman编码的核心思想

各位同学，咱们今天聊聊压缩算法的老祖宗。说实话，现在各种花里胡哨的压缩库满天飞，但万变不离其宗，底层逻辑还是这三板斧：LZ77、LZ78 和 Huffman 编码。我在做嵌入式系统优化时，发现很多工程师连这些基础都搞混，上来就调 zstd 参数，结果越调越慢。嗯，咱们先把地基打牢。

1. LZ77：滑动窗口里的“找茬”游戏

LZ77 的核心思想，说白了就是用指针代替重复数据。你想想看，一段文本里“压缩”这个词出现了十次，我干嘛要存十遍？存一次，后面九次只记“前面第几个位置，长度多少”就行了。

举个例子，输入 "abcabcabc"：

• 一开始窗口为空，直接输出 'a', 'b', 'c'
• 读到第二个 "abc" 时，发现窗口里有完全匹配的 "abc"
• 于是输出 (3, 3)，意思是“往前3个字符，复制3个字符”

我在项目中遇到过一个问题：窗口设太大，内存吃不消；设太小，压缩率上不去。后来我习惯用 32KB 窗口做通用场景，效果比较均衡。

2. LZ78：字典式压缩的鼻祖

LZ78 和 LZ77 的思路不太一样。它不依赖滑动窗口，而是动态构建一个字典。每遇到一个新短语，就把它加入字典，下次再遇到直接输出字典索引。

举个例子，输入 "ababcab"：

• 遇到 'a'，字典里没有，加入字典索引 1
• 遇到 'b'，加入字典索引 2
• 遇到 "ab"，发现字典里有 "a"+"b" 的组合？没有，于是把 "ab" 加入字典索引 3
• 遇到 'c'，加入字典索引 4
• 遇到 "ab"，输出索引 3

你可能会问：那字典无限增长怎么办？没错，这就是 LZ78 的致命伤。我在做文件压缩工具时，发现字典超过 4K 条目后，查找速度急剧下降。后来我加了字典重置策略——每 8KB 数据清空一次字典，效果还不错。

3. Huffman 编码：给字符“称体重”

Huffman 编码的思路特别直观：高频字符用短码，低频字符用长码。就像摩斯电码里 'e' 用 '.' 表示，而 'q' 用 "--.-" 表示一样。

具体怎么构建？我习惯用一句话概括：把频率最小的两个节点合并，重复直到只剩一棵树。

假设字符频率如下：

字符	A	B	C	D	E
频率	15	7	6	6	5

构建过程：

1. 取最小的 D(6) 和 E(5)，合并为 11
2. 取 C(6) 和 B(7)，合并为 13
3. 取 11 和 13，合并为 24
4. 取 A(15) 和 24，合并为 39

最终编码：A=0, B=10, C=110, D=1110, E=1111。你看，频率最高的 A 只用了 1 位，而 E 用了 4 位。

我记得有一次做日志压缩，发现 Huffman 树构建本身占用了大量 CPU。后来我改用规范 Huffman 编码，只传输码长表，不传输树结构，压缩速度提升了 40%。

4. 三者如何协同工作？

实际工程中，很少单独使用某个算法。我参与过的压缩库，基本都是LZ77 + Huffman 的组合拳：

• 第一层：LZ77 找出重复数据，输出 (距离, 长度) 对和原始字符
• 第二层：Huffman 对上述输出进行熵编码

这就是 DEFLATE 算法的核心，也是 gzip、zlib、PNG 的底层基础。你想想看，LZ77 负责“去重”，Huffman 负责“压缩”，各司其职。

5. 知识体系总览

下面这张图，是我自己梳理的三大算法关系图。你看一眼，就能明白它们在整个压缩体系中的位置：

从这张图你能看到，LZ77 和 LZ78 是字典压缩的两条分支，而 Huffman 是统计压缩的代表。它们组合起来，就构成了现代压缩算法的基石。

6. 总结与思考

学完这三个算法，我建议你思考一个问题：为什么 LZ77 比 LZ78 更流行？

我个人觉得，原因有两点：

• LZ77 的滑动窗口天然适合流式处理，内存可控
• LZ78 的字典会无限增长，在资源受限场景下不友好

但 LZ78 的思想启发了后来的 LZW 和 LZMA，所以它依然值得学习。嗯，今天就先聊到这儿。下一节咱们会深入 LZ77 的工程实现，包括哈希链查找、懒惰匹配这些实战技巧。