LZW 算法

LZW 算法(Lempel-Ziv-Welch)是一种字典式无损数据压缩算法,由特里·韦尔奇(Terry Welch)于 1984 年发表,是对亚伯拉罕·伦佩尔(Abraham Lempel)与雅各布·齐夫(Jacob Ziv)1978 年提出的 LZ78 算法的工程化改进。它以实现简单、单遍处理、无需预先统计而著称,曾长期是通用压缩的主力。

概述

与霍夫曼编码依赖字符频率不同,LZW 直接利用数据中的重复子串:把见过的字符串登记进字典,再次遇到时只输出字典编号。压缩与解压两端都按同样规则动态构建字典,因此压缩文件里不需要附带字典本身,这是 LZW 最优雅之处。它随 Unix compress 工具普及,又被 GIF 与 TIFF 图像格式采用而家喻户晓。

核心原理

• 初始化:字典预先装入全部单字符(如 256 个字节值),编号从 256 起分配给新串。
• 压缩:维护当前串 w,不断读入下一个字符 c;若 w+c 在字典中则令 w 变为 w+c 继续,否则输出 w 的编码,把 w+c 存入字典,并令 w 从 c 重新开始。
• 解压:按相同规则重建字典,依据编码序列还原文本;唯一的特殊情形是遇到刚刚才加入、尚未完整登记的编码,可由上一个串推出。
• 字典满时可以冻结、清空重建或按需扩大编码位宽,常见实现采用 9 到 12 位变长编码。

应用场景

LZW 最著名的应用是 GIF 图像格式与 TIFF 的可选压缩模式,以及早期的 Unix compress、调制解调器压缩协议 V.42bis 和 PDF 中的部分流压缩。历史上尤尼西斯(Unisys)公司持有的 LZW 专利曾在上世纪九十年代引发广泛争议,直接催生了完全开放的 PNG 格式;相关专利已于 2003 年至 2004 年间在各国陆续到期。如今通用压缩多被基于 LZ77 加熵编码的 DEFLATE、zstd 等取代,但 LZW 仍是理解字典压缩的最佳入门算法。

常见问题

问:LZW 与 LZ77、LZ78 有何区别？答:LZ77 用滑动窗口内的(距离,长度)指针引用历史数据,LZ78 与 LZW 则显式建字典;LZW 去掉了 LZ78 输出中的附带字符,并预装单字符字典,工程上更简洁。

问:为什么解压端不需要传字典？答:因为字典的每一项都是由已经输出的内容按确定规则生成的,解压端读到编码时能同步执行同样的登记过程。

问:LZW 现在还常用吗？答:在新系统中已不多见,但 GIF 与大量存量 TIFF、PDF 文件仍在使用,读写这些格式仍需实现 LZW。