LZ77の基本原理と歴史：DEFLATEを軸にした派生技術と実装ノウハウ

2025年11月22日 最終更新日時 : 2025年11月22日 エバープレイ編集部

LZ77とは — 基本アイデアと歴史的背景

LZ77（Lempel–Ziv 1977）は、1977年にアブラハム・レンペル（Abraham Lempel）とヤアコブ・ジブ（Jacob Ziv）が発表した、代表的な辞書式（dictionary-based）可逆圧縮アルゴリズムのひとつです。原論文「A universal algorithm for sequential data compression」によって示されたこの手法は、出現したデータの過去部分（過去のウィンドウ）を“辞書”として利用し、現在の位置で最長一致する過去の文字列を参照（距離と長さで表現）することで冗長性を取り除きます。

LZ77の基本原理（スライディングウィンドウ）

LZ77の特徴は「スライディングウィンドウ（滑る窓）」方式です。入力ストリームを先読みバッファ（lookahead buffer）と検索バッファ（search buffer）に分け、検索バッファ内に現れる最長の一致（match）を探します。見つかった場合はその一致を「(距離, 長さ, 次の文字)」のようなトークンで出力し、見つからなければ単一のリテラル文字を出力してウィンドウを進めます。

  • 検索バッファ（Search buffer）: 過去に出現したデータ（辞書）
  • 先読みバッファ（Lookahead buffer）: 現在から先に見えるデータ
  • トークン例: (offset, length, next_symbol) — offset は現在位置からの距離、length は一致長、next_symbol は一致の直後に続く文字

簡単な動作例

入力: "abcabcabcx"

最初は検索バッファが小さいためリテラルを出力しますが、"abc" が2回目以降に出現したとき、過去の位置を参照して (3,3,'a') のように表現できます（例は説明のため簡略化）。この参照により同じ部分を繰り返し保存する必要がなくなり、圧縮が実現します。

出力トークンのフォーマット

LZ77のオリジナル表現は (offset, length, next_symbol) の三つ組ですが、実装や派生によって様々な表現が使われます。

  • LZ77（三要素）: (distance, length, 次の文字)。検索バッファに一致がなくとも next_symbol を伴う。
  • LZSS: 一致がない場合は単一バイト（リテラル）を出力し、一致がある場合は (offset,length) の二要素で出力する。フラグビットでどちらかを示す。
  • DEFLATE: LZ77類似のマッチ（最小長3、最大長258、距離は最大32768など）を用い、マッチ長／距離と単一シンボルを別の符号化（ハフマン符号）でさらに圧縮する。

LZ77単体と統計的符号化の組合せ

重要な点は、LZ77自体は「辞書参照」による冗長性除去（繰り返しの排除）を行うだけで、参照トークンの出現頻度に基づく最適符号化（例えばハフマン符号や算術符号）を行うわけではないことです。実運用ではLZ77でマッチを検出した後に、そのトークンをハフマンやレンジコーダ（算術符号）でさらに圧縮することが一般的です（例: DEFLATE は LZ77 + ハフマン）。

アルゴリズムの疑似コード（概念説明）

pos = 0
while pos < len(input):
  find longest match of input[pos:] in input[max(0,pos-W):pos]
  if match.length >= MIN_MATCH:
    emit (offset=pos - match_pos, length=match.length, next_char=input[pos+match.length])
    pos += match.length + 1
  else:
    emit literal input[pos]
    pos += 1

ここで W は検索バッファ（ウィンドウ）の最大サイズ、MIN_MATCH は一致と見なす最小長（実装によっては 2 か 3）です。

実装上の工夫と探索手法

最長一致を見つけることが圧縮効率の鍵ですが、単純に文字列比較を全探索すると時間コストが高くなります。実装では次のような高速化技術が使われます。

  • ハッシュチェイン（Hash chains）: 先読みバッファの先頭の n バイトをハッシュし、同じハッシュを持つ過去位置を辿って最長一致を探す。
  • バイナリツリー（Binary trees）: 過去位置をツリー構造で管理し、効率的に類似位置を探す。
  • ローリングハッシュ（Rabin–Karp）やSuffix Array / Suffix Tree: 理論上は高速に最長一致が求められるが、実装メモリや定数因子の問題がある。
  • 限定検索深度や最長一致打ち切り: 実行時間と圧縮率のトレードオフを調整するために探索回数を制限する。

計算量とメモリ

理想的には最長一致検索を O(n) で終わらせる手法（サフィックス構造など）もありますが、実用的な圧縮器ではハッシュベースやツリーにより平均的に高速化します。ウィンドウサイズを大きくすると圧縮率は向上することがありますが、検索空間が増えて処理時間とメモリが増えるため適切なトレードオフが必要です。DEFLATE のように 32KB 程度の固定ウィンドウは実装容易性と性能のバランスが取れた設計例です。

LZ77の派生と関連技術

  • LZ78（1978）: LZ77とは異なり、出現した語（シンボル列）を辞書に明示的に登録していく手法。LZW は LZ78 の実用化（辞書をインデックス化）として有名。
  • LZSS（Storer–Szymanski）: LZ77の改良で、短いマッチは参照よりリテラルの方が有利なため、出力をフラグで切り替えることで効率化。
  • DEFLATE（RFC 1951）: LZ77スタイルのマッチ探索＋ハフマン符号化を組み合わせた実用規格（gzip、zlib、PNG の圧縮部分に用いられる）。
  • LZMA（7zなど）: LZ77をベースにしてより大きな辞書、レンジコーダ（高効率なエントロピ符号化）や高度なマッチ予測を組合せた高圧縮比方式。

利点と欠点

  • 利点
    • 実装が比較的直感的で、ストリーム処理が可能（逐次読み書き）
    • 繰り返しパターンに強く、多くの実用的データ（テキスト、ログ、バイナリ）で有効
    • DEFLATE のように他の技術と組み合わせて高効率になる
  • 欠点
    • ランダムデータや高エントロピーデータには効果が薄い
    • 最長一致探索の計算負荷が問題になりうる（特に大きなウィンドウ）
    • 単体ではエントロピー符号化を行わないため、トークンの符号化が必須でないと圧縮比が限定される

実用的な注意点とチューニング

  • ウィンドウサイズ: 32KB は多くの用途で妥当な選択（DEFLATE の実装実績）。非常に長い繰り返しを狙うならもっと大きくするがメモリや検索コストが増える。
  • 最小マッチ長: 2 や 3 を選ぶ実装が多い。短すぎると参照オーバーヘッドで逆にサイズ増になる。
  • 探索の上限や早期打ち切り: 圧縮時間を抑えるために探索深度や比較回数を制限する。
  • エントロピー符号化の導入: ハフマンやレンジコーダを併用するとトークンのビット最適化が可能。

利用例と応用分野

  • 汎用ファイル圧縮: gzip（DEFLATE）、zip（DEFLATE の派生）、7z（LZMA）など
  • ネットワーク転送: HTTP 圧縮や各種プロトコルでのストリーム圧縮
  • 画像形式: PNG（DEFLATE を使用）
  • ログやテキストの圧縮: 長い重複やパターンが多いデータに有効

まとめ

LZ77は「過去の出力を辞書と見なし、繰り返しを距離と長さで参照する」シンプルで強力な圧縮アイデアを提供しました。単体で使う場合と、ハフマンや算術符号と組み合わせる場合とで目的や用途が異なります。実用的な圧縮器では、探索アルゴリズムの効率化や出力トークンの最適な符号化が重要であり、DEFLATE や LZMA のような派生はそれらを洗練させた例です。実装ではウィンドウサイズ、最小マッチ長、探索のトレードオフを設計目標に応じて調整することが鍵になります。

参考文献

カテゴリー
IT
前の記事
This Heat 完全ガイド：プロフィール・音楽性・代表作・影響—ポストパンクと実験ロックの歴史を紐解くNew!!
2025年11月22日
次の記事
This Heat 入門ガイド：デビュー作からDeceitまでの聴き方とおすすめレコード／購入ポイントNew!!
2025年11月22日