[信息论与编码理论专题-44]：用“编号”代替重复出现的字符串，并非对每个字母单独编码，而是对“单词“进行编码，最长匹配法。
LZW 编码（Lempel-Ziv-Welch）是一种无损数据压缩算法，由 Abraham Lempel、Jacob Ziv 于 1978 年提出，Terry Welch 在 1984 年改进并推广。它无需预先知道数据统计特性，能自适应地构建字典，特别适合压缩具有重复模式的数据（如文本、图像）。
下面从原理、步骤、优缺点、应用四个方面通俗讲解。
一、核心思想：用“编号”代替重复出现的字符串
LZW 的本质是：边压缩边建一本“短语字典”，把常见子串映射为短代码。
- 初始字典：包含所有单字符（如 ASCII 的 0–255）；
- 压缩时：不断寻找当前最长匹配的已有子串，输出其编号，并将“该子串 + 下一个字符”作为新词条加入字典；
- 解压时：同步重建相同字典，反向还原原始数据。
✅关键优势：不需要传输字典！编解码双方按相同规则动态生成，完全同步。
二、编码过程（以字符串 "ABABABA" 为例）
初始设置
- 字符集：A=65, B=66（ASCII）
- 字典初始：
0:A, 1:B, 2:C, ..., 255:ÿ（共 256 项） - 下一个可用编号：
256
步骤分解
表格
| 当前输入 | 最长匹配 | 输出 | 新增字典项 |
|---|---|---|---|
| ABABABA | A → AB（新） | 输出 A (65) | 256: AB |
| BABABA | B → BA（新） | 输出 B (66) | 257: BA |
| ABABA | AB（已在字典 #256）→ ABA（新） | 输出 256 | 258: ABA |
| ABA | A → AB（#256）→ ABA（#258）→ ABAB（新） | 输出 258 | 259: ABAB |
📌 实际输出序列：65, 66, 256, 258
原始 7 字节 → 压缩为 4 个整数（若用 12 位编码，约 6 字节），且随着字典增长，压缩率提升。
三、解码过程（同步重建字典）
输入：65, 66, 256, 258
初始字典同编码端（0–255）
| 输入码 | 对应字符串 | 输出 | 新增字典 |
|---|---|---|---|
| 65 | "A" | A | — |
| 66 | "B" | B | 256: A + B[0] = "AB" |
| 256 | "AB" | AB | 257: B + A[0] = "BA" |
| 258 | ? | — | 先构造：上一项 "AB" + 自身首字符 'A' → "ABA" |
✅ 解码结果：A B AB ABA→ 拼接为 "ABABABA"
💡神奇之处：解码器在收到 258 时，字典中尚无 258，但可通过“上一项 + 首字符”推导出来！
四、关键技术细节
1.字典大小限制
- 通常用12 位编码→ 最多 4096 个条目（0–4095）；
- 超出后可：
- 清空字典重新开始；
- 或使用动态位数（如 GIF 格式固定 12 位）。
2.无需传输字典
- 编解码器从相同初始状态出发，按相同规则更新，天然同步。
3.适合重复模式数据
- 文本（"the the the"）、简单图像（大面积单色）、日志文件等效果极佳；
- 对随机数据（如加密文件）可能反而膨胀。
五、优缺点对比
表格
| 优点 | 缺点 |
|---|---|
| ✅自适应：无需预知统计特性 | ❌字典需内存：大字典占 RAM |
| ✅编解码速度快（查表为主） | ❌初期压缩率低（字典未建立） |
| ✅实现简单 | ❌不适合高熵数据（如已压缩文件） |
| ✅广泛标准化 | ❌专利曾受限（1984–2004，现已过期） |
六、经典应用场景
表格
| 格式/协议 | 说明 |
|---|---|
| GIF 图像 | 使用 LZW 压缩调色板索引序列 |
| TIFF 图像 | 可选 LZW 压缩（无损） |
| Unix compress 命令 | 早期 Unix 标准压缩工具 |
| 可选 LZW 作为流过滤器 | |
| V.42bis 调制解调器协议 | 数据压缩标准 |
⚠️ 注意：ZIP、PNG 等现代格式不再使用 LZW（因专利历史和效率），改用DEFLATE（LZ77 + 哈夫曼）。
七、与 LZ77/LZ78 的关系
- LZ77：用“滑动窗口 + 指针”表示重复（如 "ABAB" → (2,2) 表示回退2字节复制2字节）；
- LZ78：显式构建字典，存储 (index, char) 对；
- LZW：LZ78 的优化版，只输出 index，char 隐含在下一个条目中，更高效。
✅ 总结一句话：
LZW 是一位“自学习的速记员”——它一边听你说话，一边给常用词组编短号，越说越快，越压越小。
因其简洁、高效、无需先验知识，LZW 成为 20 世纪最成功的压缩算法之一，至今仍在 GIF 等场景焕发活力。