LZ78 (1978)（エルゼッドナナハチ）
Abraham Lempel と Jacob Ziv が 1978 年に LZ77 の翌年に発表した辞書ベース可逆圧縮アルゴリズム。LZ77 のスライディングウィンドウに対し、明示的に辞書を構築・拡張する方式で、後続の LZW (1984) などに影響を与えた。
概要
LZ78 は、Abraham Lempel と Jacob Ziv が 1978 年に LZ77 の翌年に発表した辞書ベース可逆圧縮アルゴリズムで、LZ77 のスライディングウィンドウ方式に対し、明示的に辞書を構築・拡張する方式を採用した点が大きな違いです。LZ77 と並ぶ Lempel-Ziv 系列の代表で、(辞書インデックス, 次の文字) のペアで符号化を行い、辞書は入力データを処理しながら動的に拡張していきます。明示辞書のため検索が高速ですが、辞書サイズ管理が複雑になる欠点があります。1984 年に Terry Welch が改良した LZW (Lempel-Ziv-Welch) によって UNIX compress (1984)・GIF (1987)・TIFF (1992 オプション)・PDF など実用フォーマットで普及しましたが、Unisys 社が保有していた LZW 特許 (1985-2004) の問題で 2000 年代に衰退、GIF も PNG (LZ77 系 Deflate) に置き換えが進みました。
主な特徴・仕組み
- 発表: 1978 年 Lempel・Ziv、IEEE Transactions on Information Theory
- 論文: "Compression of Individual Sequences via Variable-Rate Coding"
- 辞書方式: 明示的辞書を入力データから動的構築
- 符号化単位: (辞書インデックス, 次の文字) のペア
- 辞書初期化: 空または ASCII 全文字 (256 エントリ)
- 辞書拡張: 新規パターンを辞書に追加、インデックスで参照
- 辞書サイズ: 典型 4,096 エントリ (12bit)・最大 65,536 (16bit)
- 辞書リセット: 満杯時に消去または最古エントリ削除 (LZW は特殊処理)
- 特許: Unisys 社が LZW 特許保有 (1985-2004)、GIF 利用料問題で訴訟多発
- 後継: LZW (1984)・LZC (UNIX compress 実装)・LZRW
スペック比較表
| アルゴリズム | 年 | 辞書方式 | 用途 | 特許 |
|---|---|---|---|---|
| LZ77 | 1977 | スライディング | ZIP/gzip/PNG | なし |
| LZ78 | 1978 | 明示辞書 | 学術的 | なし |
| LZW | 1984 | 明示辞書改良 | GIF/compress/TIFF | あり (2004 失効) |
| LZC | 1984 | LZW + UNIX | UNIX compress | LZW 同様 |
| LZAP | 1988 | LZ78 派生 | 学術 | なし |
具体例・対応技術
- UNIX compress (1984): LZW (LZ78 派生) ベース、.Z ファイル拡張子
- GIF (1987): LZW 利用、画像圧縮の元祖、現代もアニメで利用
- TIFF (LZW オプション): 画像形式のオプション圧縮方式
- PDF (LZW): 1993 年仕様策定時に LZW 採用、後に Flate (Deflate) 追加
- PostScript Level 2: LZW 対応、印刷業界で利用
自作PCでの選び方・注意点
LZ78 系 (特に LZW) は GIF・古い TIFF・古い PDF の解凍で現代も利用されますが、新規開発では LZ77 系 (Deflate・Zstd・Brotli) が主流です。GIF アニメーションは 2026 年現在も Web で広く使われ、内部的に LZW 圧縮が動作中。Unisys 特許失効 (2004) 後は誰でも LZW を自由利用可能になり、Pillow (Python)・ImageMagick・GIMP など主要画像ライブラリでサポート継続。レトロソフト保守・古い PDF 復元・GIF アニメ生成で LZ78/LZW の知識が必要となるケースがあり、自作 PC のメディア処理用途で意識すべき技術。新規圧縮用途では Zstandard (LZ77 系) が圧倒的に優位、LZ78 系は歴史的役割を終えた状態。
関連用語との違い
- LZ77: 同系列前年、スライディングウィンドウ方式
- LZW: 1984 年 Welch 改良、Unisys 特許の元凶
- LZSS: LZ77 の改良版、リテラルフラグ追加
よくある質問（FAQ）
Q1: LZ77 と LZ78 の選択基準は? A: 一般用途・特許フリー必須なら LZ77 系。明示辞書での実装容易性なら LZ78 系。現代は LZ77 系 (Zstd/Brotli) が主流。
Q2: LZW 特許問題とは? A: Unisys 社が 1985 年に取得した LZW 特許で、GIF を利用するソフトウェア開発者から特許使用料を徴収しようとした事件。2004 年特許失効で問題解消、PNG 普及の要因。
Q3: 現代でも使う場面は? A: GIF・古い TIFF/PDF の解凍、レトロソフト互換性目的のみ。新規圧縮は LZ77 系 (Zstd/Brotli) を選択すべき。
まとめ
- LZ78 = 1978 年 Lempel-Ziv 発表、明示辞書ベース圧縮
- LZ77 のスライディングに対し、辞書を入力から動的構築
- LZW (1984) で実用化、GIF/compress/TIFF/PDF で活躍
- Unisys 特許 (1985-2004) で衰退、新規は LZ77 系主流