LZ77 圧縮 | 辞書ベースのデータ圧縮

>> 機能

[DICTIONARY]

辞書型コーディング

オフセットと長さを使って繰り返しパターンを参照します。

[SLIDING]

スライディングウィンドウ

最長一致を探すための移動ウィンドウを維持します。

[FOUNDATION]

基盤アルゴリズム

ZIP・GZIP・DEFLATE・PNG など多くの圧縮方式の基礎です。

>> 技術情報

LZ77 の仕組み

LZ77 は最近見たデータからなるスライディングウィンドウを維持します。各位置でウィンドウ内から最長一致部分文字列を検索し、見つかれば (オフセット, 長さ, 次の文字) という参照を出力します。一致がない場合は (0,0,文字) のようなリテラルを出力します。これにより、繰り返し部分が短い参照に置き換えられ、ロスレス圧縮が実現されます。

LZ77 の例

Text: "ABCABCABC"
Window=4, Lookahead=4

Position 0: 'A' - no match
  → (0,0,A)

Position 1: 'B' - no match
  → (0,0,B)

Position 2: 'C' - no match
  → (0,0,C)

Position 3: 'ABC' - matches at offset 3
  → (3,3,A)

Position 7: 'BC' - matches at offset 3
  → (3,2,)

Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)

LZ77 を使う理由

ロスレス圧縮
事前のデータ形式の知識が不要
データのパターンに自動適応
実装が比較的シンプル
現代的な多くの圧縮アルゴリズムの土台

>> よくある質問

LZ77 とは？

LZ77 は Abraham Lempel と Jacob Ziv によって 1977 年に発表された、汎用的なロスレスデータ圧縮アルゴリズムです。未圧縮データ列の中で以前に現れた部分への参照で、繰り返し部分を置き換えることで圧縮を行います。

スライディングウィンドウはどう動きますか？

スライディングウィンドウは、すでに処理されたデータを保持する検索バッファと、これから圧縮するデータを保持するルックアヘッドバッファから構成されます。アルゴリズムは検索バッファから、ルックアヘッドの先頭と最も長く一致する部分を探し、参照またはリテラルを出力します。

LZ77 と現代的な圧縮方式の違いは？

LZ77 は多くの現代的な圧縮方式の基礎です。ZIP や GZIP で使われる DEFLATE は、LZ77 と Huffman 符号化を組み合わせています。LZSS は LZ77 の冗長性を減らし、LZ78 や LZW は異なる方法で辞書を構築しますが、基本的な考え方は共通です。

最適なウィンドウサイズは？

一般的なデータでは、32KB〜64KB のウィンドウサイズがよく使われます。ウィンドウが大きいほど多くの一致が見つかりますが、メモリと時間のコストも増えます。DEFLATE は 32KB を使用します。ルックアヘッドバッファは通常 256〜512 バイト程度で、最適なサイズはデータの繰り返しパターンに依存します。

[Base64.sh]

> lz77 | sliding | window <