LZ77 圧縮デモ

The LZ77 compression algorithm eliminates structural redundancy by substituting repeating data sequences with relative mathematical pointers. Utilizing a sliding operational window, it encodes data as length-distance pairs referencing previously processed buffers. This deterministic referencing dictates the foundation of DEFLATE protocols. The algorithm relies strictly on the statistical probability of repetitive strings, maximizing entropy reduction without fundamentally altering the original mathematical information.

アルゴリズムは既に読んだテキストに出会うと、それをもう一度書き出すのではなく、「offset 文字戻って length 文字コピーせよ」という短い指示を残します。ここでの各トークンは (offset, length, literal)、つまり後方参照と新しい 1 文字の組です。実際には、繰り返しの語やパターンが多いテキストは大きく縮み、すでにランダムなデータはほとんど圧縮されません。

一致はわずか 1 文字だけ後ろを指しながら、そこにまだ存在する以上の文字をコピーできます。offset 1 では、デコーダは書き込んだ端からその 1 バイトをコピーするため、(1, 5, ...) という 1 つのトークンが 1 個の a から aaaaaa を展開します。こうして古典的な連長圧縮 (RLE) が LZ77 から無料で得られるのです——「コピー」はまだ生成中のテキストと重なります。繰り返しのサンプルを試すと、一致領域が現在位置を越えて伸びる様子が見られます。