← コンピューティング

LZ77 圧縮デモ

スライディングウィンドウが左から右へ走査する様子を見てみよう。各ステップで探索ウィンドウ内の最長一致を見つけ、(オフセット, 長さ, リテラル) のトークンを出力する。

インタラクティブシミュレーションを読み込んでいます...

窓を大きくしても、得より損のほうが大きい

探索窓を広げれば圧縮率が上がるのは自明に思えます。履歴が増えれば一致が見つかる機会も増えるからです。ところが落とし穴があります。どのポインタもその窓の中のどこでも指せる必要があるため、窓を広げると、出力するすべての参照の距離フィールドが長くなるのです。数バイトさかのぼるだけで済んだ何千もの参照まで含めて、です。窓を 2 倍にすれば、長い一致が得られたかどうかに関係なく、そのすべてに 1 ビットが加わります。ZIP、PNG、gzip の中核にある DEFLATE が 32 KB に落ち着き、数十年そこに留まった理由はこのトレードオフです。普通の文章に実際に現れる繰り返しを捉えるには十分遠く、オフセットが安く済むには十分近いのです。

繰り返さず、コピーする

アルゴリズムは、すでに読み取った文字列に出会うと、同じ内容をもう一度そのまま記録しません。代わりに、「オフセット文字戻り、そこから長さの分だけコピーする」と短く記します。ここで各トークンは(offset, length, literal)、つまり後方参照と新しい一文字の組です。同じ語やパターンを多く含むテキストほど大幅に小さくなりますが、もともとランダムなデータはほとんど圧縮できません。

1 つのトークンが長い連なりになるとき

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

全プロセスの詳細解説

  1. "abracadabra" の六つのトークン（検索ウィンドウ 16 文字） 5 ステップ

    パネルは1つのトークン後に5.18×と表示している。6つすべてのトークンが処理された後に何と表示されるかを求めよ。入力は「abracadabra」、探索ウィンドウは16文字、先読みバッファは8である。

    1. トークンは3つの固定幅フィールドで構成されるため、そのコストはデータではなく2つの設定によって決定される。オフセットはウィンドウ内の任意の位置を指定する必要があり、一致長はバッファサイズまでの任意の値を、リテラルは生の1バイトを表す。

      ⌈log⁡2(W+1)⌉+⌈log⁡2(B+1)⌉+8=⌈log⁡217⌉+⌈log⁡29⌉+8=5+4+8=17 bits\lceil\log_2(W{+}1)\rceil+\lceil\log_2(B{+}1)\rceil+8=\lceil\log_2 17\rceil+\lceil\log_2 9\rceil+8=5+4+8=17\ \mathrm{bits}

    2. エンコーダは左から右へスキャンし、ウィンドウが提供する最長一致を採用する。最初の3文字の手前には何も存在しないため、'a'、'b'、'r' はそれぞれ1回出力するだけでトークン丸ごと1つを費やす。位置0から「abra」をコピーする最後のトークンだけが、そのコストに見合う効果を発揮する。

      (0,0,a) (0,0,b) (0,0,r) (3,1,c) (5,1,d) (7,4,∅)(0,0,\mathtt{a})\ (0,0,\mathtt{b})\ (0,0,\mathtt{r})\ (3,1,\mathtt{c})\ (5,1,\mathtt{d})\ (7,4,\varnothing)

    3. パネル上の比率は累積数値であり、入力全体をこれまでに生成された出力で割ったものである。1つのトークン処理後では、11文字を17 bitsと比較しているため、初期値がこれほど高くなる。

      11×81×17=8817=5.18×\frac{11\times8}{1\times17}=\frac{88}{17}=5.18\times

    4. それぞれ17 bitsのトークン6つで102 bitsとなり、88 bitsの入力に対するコストとなる。符号化後のデータは、符号化対象の元のデータよりも大きくなっている。

      11×86×17=88102=0.86×\frac{11\times8}{6\times17}=\frac{88}{102}=0.86\times

    5. 損益分岐点は1回の割り算で求められる。1つのトークンは17 bitsを費やし、それぞれ8 bits相当の何文字かを表現するため、この手法が得をするのは、トークン1つあたり平均17/8文字を超えて進む場合のみである。そしてこれら6つのトークンのうち、それを満たすのは最後の1つだけである。

      NT>178=2.125,NT=116=1.83\frac{N}{T}>\frac{17}{8}=2.125,\qquad \frac{N}{T}=\frac{11}{6}=1.83

    解答

    パネルには最初のトークン後に 5.18×、6番目のトークン後に 0.86× と表示される。同じ文字列、同じ符号化でありながら、1.0 を挟んで反対側に位置している。覚えておくべき数値は 1トークンあたり2.125文字 であり、これは単にトークン幅を8で割ったもので、LZ77が与えられた入力に有効かどうかを判定する基準そのものである。また、一見コストがかからないように見える設定ノブの代償も示している。探索ウィンドウを64に広げると、すべてのオフセットフィールドに2 bitsが追加されるが、この文字列ではより長い一致はまったく見つからず、解析結果は同じ6つのトークンのままであるため、比率は 0.77× に低下する。到達範囲を2倍にするごとに、使用されるかどうかにかかわらず、すべてのトークンでさらに1 bitのコストが発生する。

    NT>⌈log⁡2(W+1)⌉+⌈log⁡2(B+1)⌉+88\frac{N}{T}>\frac{\lceil\log_2(W{+}1)\rceil+\lceil\log_2(B{+}1)\rceil+8}{8}

学習の道すじ

手作業によるデータ圧縮

参考文献 (1)

· 公表された資料と照合しています。訂正のご指摘を歓迎します。