LZWとは何か？基本原理・実装のポイント・歴史・特許問題・現代の圧縮アルゴリズムとの比較
エバープレイ編集部LZWとは — 基本概要
LZW（Lempel–Ziv–Welch）は、可逆（ロスレス）データ圧縮アルゴリズムの一つで、1984年に Terry A. Welch が発表した方式です。LZ78（1978年の Lempel と Ziv による方式）を改良したもので、データの繰り返しパターンを辞書（ディクショナリ）として動的に構築し、その辞書のインデックス（コード）を出力することで圧縮を行います。実装が比較的単純で高速に動作するため、GIF 画像や TIFF、UNIX の compress コマンドなど、さまざまな場面で採用されてきました。
動作の仕組み（概念）
LZW の核心は「既知の文字列に新しい文字を追加したものを辞書に追加していく」点にあります。処理は逐次的（ストリーミング）に行われます。基本的な流れは次の通りです。
- 辞書を初期化する（入力アルファベットの全ての単一文字を登録する）。
- 入力ストリームを先頭から読み、現在のシーケンス（w）に次のシンボル（k）を付加できるか辞書で調べる。
- もし w+k が辞書に存在すれば w を拡張して次へ進む（w = w+k）。
- 存在しなければ、辞書に w+k を追加し、辞書内の w のコードを出力、w を k に置き換えて続ける。
- 入力終了時に残った w のコードを出力する。
この過程により、よく現れる長いパターンは辞書に登録され、それらの出現は短いコードで表現されるため圧縮が達成されます。
エンコードの例（簡易）
例としてアルファベットだけを考え、初期辞書が {A, B, C, ...} とします。入力が "ABABABA" の場合、処理によって次のように辞書と出力が更新されます（概念的）。
- 読み取り開始: w = "A"
- 次の k = "B" → "AB" が辞書にないので、「A」のコードを出力し、"AB" を辞書へ追加。w = "B"
- 次の k = "A" → "BA" が無ければ「B」のコード出力、"BA" 登録、w = "A"
- 次 k = "B" → "AB" は既に辞書にある → w = "AB"
- 次 k = "A" → "ABA" が無ければ「AB」のコード出力、"ABA" 登録、w = "A"
- 残りを処理し、最後に残った w のコードを出力。
このように、新しい長いパターンが出現するたびに辞書が成長し、同じパターンが以降は短いコードで表現できるようになります。
実装上の重要点
- 辞書の管理：辞書はハッシュ表や trie（接頭辞木）で実装されることが多く、検索と挿入は高速化が必要です。
- 可変長コード：出力されるコード幅は辞書の成長に応じてビット数を増やす方式が一般的（例：9ビット→10ビット→…）。GIF などでは特殊な「クリアコード（辞書をリセット）」や「終端コード（EOD）」を利用します。
- 辞書の上限とリセット：辞書が上限（例えばコード幅の最大値）に達したとき、辞書をリセットして初期状態に戻す方式と、上限に達したらそれ以上追加しない方式があります。GIF ではクリアコードを送ってリセットする仕様が使われます。
- ビット詰め（packing）：可変長コードをバイト境界に詰めるためのビット操作が必要で、実装を誤ると互換性が損なわれます。
性能と特徴（長所・短所）
- 長所
- 逐次的に処理でき、ストリーミング処理が可能。
- 実装が比較的単純で高速。リアルタイム用途にも向く。
- 圧縮／復元が完全可逆で、繰り返しパターンには高効率。
- 短所
- 統計符号化（ハフマンや算術符号化）と組み合わせていない基本形では、出力コードの頻度分布を最適化できず、最先端の圧縮方式（例：DEFLATE：LZ77＋ハフマン）より圧縮率が劣る場合がある。
- 初期段階や短いデータ、ランダムデータでは圧縮効果が小さいか逆に膨らむことがある。
- 辞書管理（メモリ）やビット操作の実装ミスによる互換性問題。
歴史と利用例
LZW は 1984 年の論文で提案されて以降、広く使われてきました。代表的な用途は次の通りです。
- GIF（Graphics Interchange Format）：LZW を採用した初期の画像フォーマット。可逆圧縮でアニメーション GIF などに使われる。
- TIFF（Tagged Image File Format）：LZW 圧縮をサポートするバージョンがあり、画像保存で利用されることがある。
- UNIX compress：historical なユーティリティで LZW を実装していた。
ただし、1990年代に LZW をめぐる特許問題が起き、GIF の普及に影響を与えたため、代替として PNG（可逆圧縮の画像フォーマットで、DEFLATE を採用）が登場し、広く受け入れられることになりました。
特許問題（概略）
LZW に関連する特許は一部の企業が保有し、1990年代にそのライセンス問題が公になったことで、GIF の利用と配布に制約や不安が生じました。この問題を受けて、特にウェブ画像の分野では特許フリーかつ性能の高い PNG が代替として普及しました。なお、関連特許は各国で有効期限があり、最終的には満了しているため、現在は LZW を用いること自体に新たな特許料は通常発生しません（各国の特許法・時効を参照してください）。
LZW と現代の圧縮アルゴリズムとの比較
今日の一般的な用途では、LZ77 系（例：DEFLATE）が多く使われます。DEFLATE は LZ77 にハフマン符号を組み合わせ、統計的に出力をさらに圧縮するため、同じデータに対してより高い圧縮率を示すことが多いです。一方で LZW の実装は軽量で低レイテンシーなため、小規模な組み込み用途や歴史的フォーマットの互換性のために今でも重要です。
実装上の注意点・最適化
- 辞書の上限値をどう扱うか（リセットするか、拡張を止めるか）を設計段階で決める。
- 高速化のためにハッシュ関数やオープンアドレッシングを用いた辞書実装、または圧縮中に頻度の低いエントリを削除する策略を検討する。
- 可変長コードのエンコード・デコードの整合性（ビットオーダ、バイト境界の扱い）に注意する。GIF 等の既存仕様に合わせる場合は仕様通りに処理すること。
- 圧縮前にデータ特性を分析し、LZW が有利かどうか（繰り返しパターンが多いか、短いデータかどうか）を判断する。複数アルゴリズムを選択できるようにするのも有効。
まとめ（どんな場面で使うか）
LZW は設計がシンプルで実行が高速、ストリーミング処理に適しているため、組み込み系やレガシーフォーマットの互換性維持には有益です。しかし、最高の圧縮率を求める現代的な用途では、LZ77＋統計符号（DEFLATE など）やより進んだアルゴリズム（Brotli、Zstandard 等）が選ばれることが多いです。歴史的経緯（特許問題など）を踏まえた上で、データ特性と用途に合わせて選択してください。
参考文献
- Lempel–Ziv–Welch (Wikipedia)
- Welch, T. A., "A Technique for High-Performance Data Compression", Computer, 1984 (DOI)
- GIF89a Specification (W3C)
- PNG (Portable Network Graphics) Specification (W3C)
- GIF の特許問題（Wikipedia 解説）
- compress (Unix) — LZW を使ったユーティリティ（Wikipedia）
投稿者プロフィール
