LZ77 スライディングウィンドウ圧縮

LZ77 は、繰り返される入力を、限定された履歴ウィンドウ内への参照で置き換える非可逆圧縮方式のファミリーです。元の 1977 年の設計ではスライディング辞書を使用していました。実用的な形式では、独自のトークン構文、マッチ検索器、エントロピー符号を選択します。

リテラル、履歴、マッチ #

入力位置で、エンコーダーは以前に出力したバイト列から一致するプレフィックスを検索します。有用なマッチがない場合はリテラルを出力し、そうでなければ少なくとも距離と長さを含むバックリファレンスを出力します。形式によっては各マッチの後にリテラルを追加し、別の形式では独立したリテラルとマッチのストリームを出力します。デコーダーは、現在の出力位置から distance バイト前の位置から length バイトをコピーします。

コピー元とコピー先は重なることがあります。履歴が a で終わっている場合、距離 1、長さ 5 のマッチは aaaaa を生成します。コピーされた各バイトが次のバイトのコピー元になるためです。デコーダーは前方のバイト順でコピーするか、同等の連鎖セマンティクスを持つループを使用する必要があります。memcpy もスナップショット方式の memmove も、すべての有効な重複マッチを実装するものではありません。

マッチ検索と解析 #

大きなウィンドウはより遠くの反復を見つけますが、より多くのメモリを消費し、距離を表すビット数も増やします。ハッシュチェーン、二分木、サフィックス構造、候補数を制限した検索は、圧縮率と CPU 時間をトレードオフします。

貪欲パーサーは、現在位置で最長のマッチを選択します。遅延パーサーはまず候補を記録し、次の位置により良いマッチがあるか確認して、合計コストが改善する場合は代わりにリテラルを出力します。動的計画法はより大きな解析空間を検索できますが、CPU とメモリのコストが増加します。トークンストリームは自己完結しているため、これらのエンコーダーの選択はいずれもデコーダーの正しさに影響しません。

境界と防御的デコード #

各形式は、最小マッチ長、最大長、ウィンドウサイズ、距離エンコーディングを独自に定義します。たとえば DEFLATE は最大 32 KiB の距離と最大 258 バイトの長さを許可します。デコーダーは、利用可能な履歴を超える距離、無効な長さまたは距離コード、出力位置の計算中の整数オーバーフロー、呼び出し元の制限を超える出力を拒否する必要があります。小さな入力が非常に大きな出力ストリームに展開する可能性があるため、リソース制限は総出力と処理量の両方を対象にすべきです。

DEFLATE と関連形式 #

DEFLATE はリテラル/長さシンボルと距離シンボルをハフマン木でエントロピー符号化し、LZ77 ウィンドウを参照バイトに使用します。LZ4 は同じコピー操作を中心にしたコンパクトなトークン形式を使用し、Zstandard はウィンドウ付き LZ マッチ段階と異なるエントロピー符号を組み合わせます。一方、LZ78 と LZW は句の明示的な辞書を維持します。これらの辞書更新規則を LZ77 の履歴参照の代わりに使用してはなりません。

参照 #

J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data Compression,” IEEE Transactions on Information Theory, 1977.
RFC 1951: DEFLATE
RFC 7932: Brotli Compressed Data Format, for another windowed LZ design.