データ圧縮の可視化
ランレングス・ハフマン符号・LZ77・LZW が文字列を縮めていく様子を 1 手ずつ見せます。ハフマン木や辞書ができていく様子と、方式ごとの圧縮率やエントロピーとの関係を確かめられます。
例
LZW の説明でよく使われる例です。辞書に登録した語句が、後半で繰り返し使われます。
出てきた文字列を辞書に登録しながら、辞書の番号で表します。GIF や昔の Unix の compress で使われました。
16 / 16辞書にある一番長い語句「OT」の番号 13 を 5 ビットで出力（最後）
- T
- O
- B
- E
- O
- R
- N
- O
- T
- T
- O
- B
- E
- O
- R
- T
- O
- B
- E
- O
- R
- N
- O
- T
- 符号にした
- 今回出力する語句
- 辞書に足す次の文字
出力
番号のビット数は、そのとき辞書にある語句の数を区別できるだけの長さです。辞書が大きくなるにつれて増えます。
| # | 語句 | 番号 | ビット |
|---|---|---|---|
| 1 | T | 5 | 3 |
| 2 | O | 3 | 3 |
| 3 | B | 0 | 3 |
| 4 | E | 1 | 4 |
| 5 | O | 3 | 4 |
| 6 | R | 4 | 4 |
| 7 | N | 2 | 4 |
| 8 | O | 3 | 4 |
| 9 | T | 5 | 4 |
| 10 | TO | 6 | 4 |
| 11 | BE | 8 | 4 |
| 12 | OR | 10 | 5 |
| 13 | TOB | 15 | 5 |
| 14 | EO | 9 | 5 |
| 15 | RN | 11 | 5 |
| 16 | OT | 13 | 5 |
ここまでで 16 個・66 ビット
辞書
最初の辞書は、入力に出てくる文字を文字コードの順に並べたものです（本来の LZW は 256 通りのバイトから始めます）。
| 番号 | 語句 |
|---|---|
| 0 | B |
| 1 | E |
| 2 | N |
| 3 | O |
| 4 | R |
| 5 | T |
| 6 | TO |
| 7 | OB |
| 8 | BE |
| 9 | EO |
| 10 | OR |
| 11 | RN |
| 12 | NO |
| 13 | OT出力した |
| 14 | TT |
| 15 | TOB |
| 16 | BEO |
| 17 | ORT |
| 18 | TOBE |
| 19 | EOR |
| 20 | RNO |
方式の比べ方
大きさは、元の文字列を UTF-8 で表したときとの比です。ハフマン符号と LZW は、復号に必要な符号表・最初の辞書を送る分の目安（項目の数 8 ビット、ハフマン符号は文字ごとに文字と符号の長さ 8 ビット、LZW は文字の並び）も足しています。
| 方式 | 本体 | 符号表・辞書 | 合計 | 元との比 | 復号 | |
|---|---|---|---|---|---|---|
| 元の文字列 | 192 | — | 192 | 100% | — | |
| ランレングス | 368 | — | 368 | 191.7% | ✓ 元どおり | |
| ハフマン符号 | 59 | 104 | 163 | 84.9% | ✓ 元どおり | |
| LZ77 | 162 | — | 162 | 84.4% | ✓ 元どおり | |
| LZW | 66 | 56 | 122 | 63.5% | ✓ 元どおり |
単位はビット。24 文字のエントロピーは 1 文字 2.424 ビットで、文字を 1 つずつ符号にする方式（ハフマン符号など）では本体を 59 ビットより小さくできません。LZ77 や LZW は繰り返し出てくる文字列をまとめて表すので、この下限より小さくなることがあります。
使い方
- 例を選ぶか、圧縮する文字列（200 文字まで）を入力します。日本語や絵文字も使えます。
- 「ランレングス」「ハフマン符号」「LZ77」「LZW」で方式を切り替えます。「再生」や「◀」「▶」で、1 つずつ符号にしていく様子を確かめられます。
- LZ77 では、振り返る範囲（窓）と、1 回に一致させる最大の長さを変えられます。
- 下の表で、4 つの方式の大きさと、元どおりに戻せることを確かめられます。
- キーボードでは ← → で 1 コマ、Home / End で最初 / 最後に移ります（入力欄にカーソルがないとき）。
偏りを使う圧縮
ふつうの文字コードは、どの文字にも同じ長さ（英数字なら 8 ビット、日本語の UTF-8 なら 24 ビット）を使います。ハフマン符号は、よく出る文字ほど短い符号を割り当てて全体を短くします。重みの一番小さい 2 つの木をまとめることを繰り返して作った木は、どの符号も別の符号の頭の部分にならない（接頭符号）ので、区切りなしで並べても一意に戻せます。文字を 1 つずつ符号にする方式では、平均の長さをエントロピー（出現の偏りから決まる情報量）より短くできないことが知られており、ハフマン符号はその中で最も短い符号になります。
ランレングス圧縮は、同じ文字が続く「ラン」を回数と文字の組にします。しくみは単純ですが、同じ文字が続かないデータでは組の分だけかえって大きくなります。
繰り返しを使う圧縮
LZ77 は、少し前に出てきた文字列と同じところを「何文字前から何文字」で表します。振り返る範囲を窓と呼び、窓が大きいほど遠くの繰り返しを見つけられますが、位置を表すビット数が増えます。一致はこれから読む部分に重なってもよく、「aaaaaa」のような繰り返しも 1 つの出力で表せます。ZIP や gzip、PNG で使われる Deflate は、LZ77 の出力をさらにハフマン符号で縮めています。
LZW は、読んだ文字列を辞書に登録しながら、辞書の番号で表します。辞書は送らなくても、復号する側が同じ手順で作り直せます（このアプリでは最初の辞書だけは送る分を数えています）。長い文章ほど辞書が育ち、長い語句を 1 つの番号で表せるようになります。
このアプリのビット数は、しくみを比べるための単純な数え方です。実際の形式は、符号表の送り方や数の表し方を工夫して、さらに小さくしています。