第三章 无损压缩原理：字典编码思想、统计编码思想、游程编码（RLE）原理、LZ77算法核心思想
好，咱们进入正题。无损压缩，说白了就是压缩完还能原封不动地解回来。这跟有损压缩不一样——有损压缩像 JPEG，丢点细节你肉眼看不出来，但无损压缩不行，丢一个 bit 都不行。
我个人习惯把无损压缩分成三大流派：统计编码、字典编码、还有游程编码。今天咱们一个一个聊透。
3.1 统计编码思想：用更短的码表示更常见的东西
统计编码的核心思想其实特别朴素——出现频率高的符号，用短码；出现频率低的符号，用长码。你想想看，如果每个字符都用 8 位固定长度去存，那「e」和「z」占的空间一样大，这合理吗？不合理。
我在项目中遇到过一份英文文本，里面「e」出现了上万次，「z」只出现了几十次。如果用等长编码，光「e」就浪费了多少空间？
最经典的统计编码就是哈夫曼编码。它的做法是：
- 统计每个符号的出现频率
- 把频率最低的两个符号合并成一个节点
- 重复这个过程，直到构建出一棵二叉树
- 左子树走 0，右子树走 1，得到每个符号的编码
举个例子，假设有四个符号 A、B、C、D，频率分别是 50%、25%、12.5%、12.5%。哈夫曼编码的结果可能是：
| 符号 | 频率 | 哈夫曼编码 | 等长编码 |
|---|---|---|---|
| A | 50% | 0 | 00 |
| B | 25% | 10 | 01 |
| C | 12.5% | 110 | 10 |
| D | 12.5% | 111 | 11 |
你看，A 只用了 1 位，而等长编码需要 2 位。整体下来，平均码长从 2 位降到了 1.75 位。别小看这 0.25 位，数据量大了以后，节省的空间相当可观。
3.2 字典编码思想：用索引代替重复的内容
统计编码关注的是「哪个符号出现得多」，而字典编码关注的是「哪些内容重复出现了」。它的思路是：把重复出现的字符串存到一个字典里，下次再遇到时，只存一个索引号。
举个例子，原文是「ABABABABAB」，如果建一个字典：
字典：
索引 0: "AB"
索引 1: "ABAB"
压缩结果：0, 1, 0, 1 （或者更聪明的组合）
嗯，这里要注意：字典编码有两种实现方式——静态字典和动态字典。
- 静态字典：提前约定好一本字典，编码和解码都用同一本。比如传真机用的就是静态字典，因为传真的内容模式比较固定。
- 动态字典：边压缩边建字典，解压时也同步重建。LZ77、LZ78 都属于这一类。
我曾经在一个日志压缩项目里试过静态字典，结果发现日志格式一变，压缩率直接崩了。后来换成动态字典，适应性好很多。
3.3 游程编码（RLE）原理：最简单的压缩算法
游程编码，英文叫 Run-Length Encoding，简称 RLE。它的原理简单到令人发指——把连续重复的字符替换成「字符 + 重复次数」。
比如原始数据是：
AAAAABBBCCCCDD
RLE 压缩后变成：
A5B3C4D2
从 14 个字符压缩到 8 个字符，省了将近一半。
但 RLE 有个致命弱点——如果数据本身很少重复，压缩后反而会变大。比如「ABCDEFG」压缩成「A1B1C1D1E1F1G1」，从 7 个字符变成了 14 个字符，直接翻倍。
所以实际应用中，RLE 通常作为预处理步骤，先处理掉连续重复的部分，再用其他算法做进一步压缩。比如传真机就是 RLE + 哈夫曼的组合。
3.4 LZ77 算法核心思想：滑动窗口 + 匹配指针
LZ77 是 Lempel-Ziv 家族里最经典的一个，也是后来 ZIP、gzip、PNG 等格式的基础。它的核心思想就两句话：
- 用滑动窗口维护一个历史缓冲区，里面存着最近处理过的数据
- 在当前数据中找跟历史缓冲区匹配的最长字符串，然后用「(距离, 长度)」这对指针来代替
举个例子，假设滑动窗口大小是 8 个字符，当前要处理的数据是：
历史缓冲区: "abcdeabc"
当前数据: "deabcxyz"
算法会从当前数据里找最长的、能在历史缓冲区里匹配到的字符串。这里「deabc」中的「de」匹配不到，但「abc」在历史缓冲区里出现过，位置是偏移 5（从当前位置往前数 5 个字符），长度是 3。
于是压缩结果就是：
原始: d e a b c x y z
压缩: d e (5,3) x y z
你看，原本 8 个字符，现在变成了 5 个字符加一对指针。如果数据里重复模式很多，压缩率会非常可观。
关键参数：
- 滑动窗口大小：决定了能回溯多远找匹配。窗口越大，找到长匹配的概率越高，但搜索时间也越长。
- 最小匹配长度：太短的匹配不值得用指针代替，因为指针本身也有开销。一般设 2 或 3。
我记得有一次优化一个嵌入式设备的固件压缩，滑动窗口设了 4KB，结果解压速度太慢。后来把窗口缩小到 1KB，压缩率只降了 3%，但解压速度快了一倍。嗯，这就是工程上的取舍。
3.5 三种思想的对比与组合
这三种思想不是互斥的，实际压缩工具往往是它们的组合。比如：
| 压缩工具 | 使用的技术 |
|---|---|
| gzip | LZ77 + 哈夫曼编码 |
| PNG | LZ77 + 哈夫曼编码（Deflate 算法） |
| 传真机 | RLE + 哈夫曼编码 |
| ZIP | Deflate（LZ77 + 哈夫曼） |
为什么会这样组合？因为每种思想都有它的长处和短板：
- RLE 擅长处理连续重复，但对随机数据无效
- 字典编码 擅长处理重复模式，但对高频单字符不敏感
- 统计编码 擅长处理频率差异大的数据，但对重复模式无能为力
所以聪明的做法是：先用字典编码或 RLE 把数据里的冗余去掉，再用统计编码对结果做二次压缩。这就是为什么 Deflate 算法能成为互联网上使用最广泛的压缩算法——它把 LZ77 和哈夫曼编码完美地结合在了一起。
我的建议：如果你自己写压缩工具，不要一上来就搞复杂的算法。先试试 RLE，如果效果不好，再加 LZ77，最后用哈夫曼收尾。每一步都做性能测试，你会发现很多时候简单的组合就够用了。
好，这一章的内容就到这里。下一章咱们会深入 LZ77 的变种 LZSS 和 LZW，看看它们是怎么在 LZ77 的基础上做优化的。到时候我会拿实际代码出来讲，保证你能看懂。