LZ77 (1977)（エルゼッドナナナナ）
Abraham Lempel と Jacob Ziv が 1977 年に発表した辞書ベース可逆圧縮アルゴリズム。スライディングウィンドウ内の過去データから繰り返しパターンを (距離, 長さ) のペアで参照して圧縮、ZIP/gzip/PNG/Deflate の基盤として現代も主流の基礎技術。
概要
LZ77 は、イスラエルの数学者 Abraham Lempel と Jacob Ziv が 1977 年に発表した辞書ベース可逆圧縮アルゴリズムで、スライディングウィンドウ内の過去データから繰り返しパターンを (距離, 長さ) のペアで参照して圧縮する画期的な手法です。「Lempel-Ziv 1977」(LZ77) または「LZ1」とも呼ばれ、現代の ZIP/gzip/PNG/Deflate の基盤として、また Snappy・lz4・Zstandard・Brotli といった最新圧縮アルゴリズムの基礎技術として位置付けられています。基本アイデアはシンプルで、過去 N バイト (典型 32KB) のスライディングウィンドウを保持し、新規データに対し最長一致を検索して (offset, length, next char) の三つ組で符号化。1989 年に Phil Katz が PKZIP で実装した Deflate アルゴリズム (LZ77 + Huffman 符号化) によって商用利用が爆発的に普及し、現代のあらゆる圧縮技術の源流となりました。
主な特徴・仕組み
- 発表: 1977 年 Abraham Lempel・Jacob Ziv、IEEE Transactions on Information Theory
- 論文: "A Universal Algorithm for Sequential Data Compression"
- 辞書方式: スライディングウィンドウ (過去データの一定範囲)
- 典型ウィンドウサイズ: 32KB (Deflate)・最大 256KB-1MB (Zstd)
- 符号化単位: (offset, length, next char) の三つ組
- マッチ最低長: 3 バイト (典型)、3 バイト未満はリテラル出力
- 検索方法: ハッシュテーブル・木 (Suffix Tree)・最長一致検索
- 圧縮率: 平均 50-70% (テキスト)、画像はあまり圧縮しない
- 復号: 高速、(offset, length) で過去データから直接コピー
- 計算量: 圧縮 O(N×M)、復号 O(N)
スペック比較表
| アルゴリズム | 年 | 辞書方式 | 圧縮率 | 速度 |
|---|---|---|---|---|
| LZ77 | 1977 | スライディング | 50-70% | 中 |
| LZ78 | 1978 | 明示辞書構築 | 50-65% | 中 |
| LZW (LZ78 派生) | 1984 | 明示辞書 | 50-70% | 中 |
| Deflate (LZ77+Huffman) | 1989 | スライディング 32KB | 60-75% | 中 |
| Zstandard | 2016 | スライディング 1MB+ | 70-85% | 高速 |
具体例・対応技術
- Deflate (1989): LZ77 + Huffman、PKZIP・gzip・PNG のベース
- Snappy (Google, 2011): 速度重視 LZ77 系、Bigtable・LevelDB で利用
- lz4 (2011): 超高速 LZ77 系、ZFS・lvm-cache で利用
- Zstandard (2016): Facebook 開発、LZ77 + ANS、現代最強級
- Brotli (Google, 2013): LZ77 + Huffman + 第二段辞書、Web 標準
自作PCでの選び方・注意点
LZ77 は現代のあらゆる圧縮ツール (ZIP/gzip/Zstd/Brotli/Snappy/lz4) の内部で動作し、Web 開発・データ圧縮・ファイルバックアップで CPU 性能が直接影響します。Intel/AMD の最新 CPU (Alder Lake 以降・Zen 4 以降) は SIMD 命令 (AVX-512・AVX2) で LZ77 マッチ検索を高速化、圧縮速度が世代ごとに 20-30% 向上しています。NVMe SSD + Zstandard で AI モデルファイル (10-100GB) を圧縮保存する用途で実用的な選択肢、Llama 3 70B の Q4 量子化済モデル (約 40GB) を Zstd で 25-30GB 程度に圧縮可能。Web サーバの応答圧縮 (Brotli/gzip) は CPU 負荷と帯域削減のトレードオフ、Nginx の brotli モジュール導入で 15-25% の帯域削減効果が見込めます。
関連用語との違い
- LZ78: 同じ Lempel-Ziv 系列の後継、明示的辞書構築が違い
- Huffman: 別系統の符号化、LZ77 と組合せ (Deflate) で最強
- LZW: LZ78 の改良版、特許問題で衰退
よくある質問（FAQ）
Q1: LZ77 と LZ78 どちらが優れる? A: 実装・性能とも一長一短だが、LZ77 系 (Deflate・Zstd) が現代主流。LZ78 系 (LZW) は GIF/compress で残るが衰退傾向。
Q2: マッチ検索の高速化手法は? A: ハッシュテーブル (高速・低圧縮)・Suffix Tree (低速・高圧縮)・Suffix Array (中庸) の選択肢。Zstd は適応的にこれらを選択して最適化。
Q3: なぜ 1977 年のアルゴリズムが現代も主流? A: シンプルさ・実装容易性・特許なし・最適化余地大の特性。SIMD 命令や ANS との組合せ (Zstd) で現代も性能を伸ばし続けている。
まとめ
- LZ77 = 1977 年 Lempel-Ziv 発表、スライディング辞書圧縮
- (offset, length, next char) の三つ組で繰り返しパターン参照
- Deflate (ZIP/gzip/PNG)・Snappy・lz4・Zstd・Brotli の基盤
- 50 年近く現役、SIMD/ANS との組合せで進化継続