LZW (1984)（エルゼットダブリュー）
Terry Welch が 1984 年に LZ78 を改良して発表した辞書ベース可逆圧縮アルゴリズム。明示辞書を更にシンプル化・高速化、UNIX compress (1984)・GIF (1987)・TIFF・PDF など 1980-1990 年代の主要圧縮フォーマットで広く採用された。
概要
LZW (Lempel-Ziv-Welch) は、Terry Welch が Sperry Univac (後の Unisys) に在籍していた 1984 年に LZ78 を改良して発表した辞書ベース可逆圧縮アルゴリズムで、明示辞書を更にシンプル化・高速化することで、UNIX compress (1984)・GIF (1987)・TIFF (1992 オプション)・PDF など 1980-1990 年代の主要圧縮フォーマットで広く採用されました。LZ78 のペア符号化 (辞書インデックス, 次の文字) を辞書インデックスのみに簡略化し、ASCII 256 文字を初期辞書として高速処理を実現。Sperry Univac は 1985 年に LZW 特許を取得 (US 4,558,302) し、1994 年に GIF を利用するソフトウェアから特許使用料を徴収する方針を発表 (CompuServe との合意) し、Web 開発者コミュニティから大反発を受けた歴史的「GIF 訴訟事件」の元凶として知られています。特許は 2004 年に失効し、現在は誰でも自由利用可能となっています。
主な特徴・仕組み
- 発表: 1984 年 Terry Welch、IEEE Computer
- 論文: "A Technique for High-Performance Data Compression"
- 改良点: LZ78 のペア符号化を辞書インデックスのみに簡略化
- 初期辞書: ASCII 256 文字 (0-255)、辞書インデックス 256 以降に新規パターン追加
- 辞書サイズ: 典型 12bit (4,096 エントリ)・最大 16bit (65,536)
- エンコーディング: 入力ストリームを順次処理、辞書最長一致の探索
- 辞書更新: 一致長 +1 文字 (現在 + 次) を新規エントリとして追加
- 辞書リセット: 満杯時に消去 (UNIX compress) または継続使用 (GIF)
- 特許: US 4,558,302 (Sperry Univac/Unisys、1985 取得・2004 失効)
- GIF 訴訟事件 (1994): Unisys が GIF 利用料を徴収方針、Web コミュニティ反発
スペック比較表
| アルゴリズム | 年 | 辞書方式 | 速度 | 用途 |
|---|---|---|---|---|
| LZ77 | 1977 | スライディング | 中 | ZIP/gzip/PNG |
| LZ78 | 1978 | 明示辞書 | 中 | 学術 |
| LZW | 1984 | 簡略化辞書 | 高速 | GIF/compress/TIFF |
| LZSS | 1982 | LZ77 改良 | 中 | RAR/LHA |
| LZMA | 1998 | LZ77+ Range Coding | 低速 | 7-Zip |
具体例・対応技術
- UNIX compress (1984): BSD UNIX 標準、.Z ファイル、LZW 商用利用第一号
- GIF (1987): CompuServe 開発、Web アニメーション標準
- TIFF (LZW オプション): TIFF 6.0 (1992) でオプション追加
- PDF (Level 1, 1993): Adobe LZW 採用、後に Flate (Deflate) 追加
- PostScript Level 2 (1992): 印刷業界、LZW 標準
自作PCでの選び方・注意点
LZW は GIF・古い TIFF/PDF・レトロ UNIX システムの解凍で現代も利用されますが、新規開発では使用が限定的。Web 開発で GIF アニメーション (2026 年現在も Reactions・ミーム用途で広く使用) は内部 LZW 圧縮、Pillow (Python)・Sharp (Node.js)・ImageMagick で完全サポート。Unisys 特許失効 (2004) 以降は自由利用可能、特許懸念は不要。新規圧縮用途では Zstandard (LZ77 系) が圧倒的に優位、LZW は歴史的役割を終えていますが、レトロ計算機エミュレータ・古いゲームの ROM 圧縮で意識される場面があります。BSD UNIX・初期 Linux の .Z ファイル解凍で uncompress または gzip -d (gzip は LZW 対応) を使う場面が稀にあります。
関連用語との違い
- LZ78: 親アルゴリズム、LZW はその改良
- Deflate: LZ77 + Huffman、PNG/ZIP/gzip で LZW を置換
- LZSS: LZ77 系改良、RAR/LHA で利用
よくある質問（FAQ）
Q1: GIF 訴訟事件とは? A: 1994 年 Unisys 社が CompuServe (GIF 仕様策定者) と合意、GIF を利用するソフトウェアから特許使用料を徴収する方針を発表。Web 開発者コミュニティが大反発、PNG 開発・普及の要因。
Q2: 現代でも LZW を使う必要は? A: 新規開発では不要、Zstd/Brotli/Deflate が優位。GIF・古い TIFF/PDF・レトロ UNIX で解凍時のみ意識。
Q3: LZW 特許は本当に失効した? A: 2003-2004 年に米国・欧州・日本で順次失効、現在は完全に自由利用可能。ただし Welch の発明への敬意として LZW の名称は維持。
まとめ
- LZW = 1984 年 Welch 改良、LZ78 のシンプル高速化版
- 明示辞書 + ASCII 初期辞書で実装容易・高速
- GIF/UNIX compress/TIFF/PDF で 1980-1990 年代主役
- Unisys 特許 (1985-2004) と訴訟事件で衰退、現在自由利用可