> lz77 | sliding | window <
// LZ77 – スライディングウィンドウと辞書参照による圧縮
辞書型コーディング
オフセットと長さを使って繰り返しパターンを参照します。
スライディングウィンドウ
最長一致を探すための移動ウィンドウを維持します。
基盤アルゴリズム
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 バイト程度で、最適なサイズはデータの繰り返しパターンに依存します。
// 計算例
| # | Offset | Length | Next | Output |
|---|---|---|---|---|
| 1 | 0 | 0 | a | a |
| 2 | 0 | 0 | b | b |
| 3 | 0 | 0 | r | r |
| 4 | 3 | 1 | c | a + c |
| 5 | 2 | 1 | d | a + d |
| 6 | 7 | 4 | — | abra |
// コード例
Input abracadabra (positions 0..10)
Token (offset, length, next)
offset = distance back into the window, length = bytes copied
Decode copy `length` bytes starting `offset` back, then append `next`
(the copy may overlap its own output, e.g. (1,5,x) repeats a byte)
Window the sliding search buffer; deflate/gzip use 32 KiB
>> その他の質問
Q: (オフセット, 長さ, 文字)の3つ組とは？
A: オフセットは既出のウィンドウ内でどれだけ遡るか、長さはコピーするバイト数、文字は次の新しい1バイトです。復号器はこれで出力を順に再構築します。
Q: なぜコピーが重なってもよいのですか？
A: オフセットが長さより小さいと、書いたばかりのバイトを読むことになります。これで繰り返しが表現できます。(1, 5, x)は直前の文字を5回出力します。
Q: LZ77はどこで使われていますか？
A: DEFLATE（gzip、zlib、PNG、ZIP）の中核で、LZ4、Snappy、Zstandard、Brotliなどの派生もあります。ウィンドウの大きさと探索方法が圧縮率と速度を決めます。