圧縮デモ
1文字も失わずにファイルを小さくするにはどうすればよいのでしょうか。答えは、ファイルが同じことを繰り返していると気づくことです。テキストを貼り付けるか例を選んで、3つの古典的な方法の働きを見てみましょう。LZ77 は前に出てきたテキストを指し示し、LZW は読み進めながら文字列の辞書を学び、ランレングス符号化は同じ文字の連続を数えます。どの方法の結果ももう一度展開して何も失われていないことを示し、グラフでは ZIP やエントロピーの限界と比べます。 テキストを入力または貼り付けるか例を選んで、方法を選んでください。LZ77 は繰り返しを前のテキストへの参照に置き換えます。強調表示された部分をクリックすると、何をコピーしているかがわかります。LZW は読み進めながら文字列の辞書を作り、その番号を送ります。RLE は同じ文字の連続(ラン)を縮めます。グラフではすべての方法を ZIP やエントロピーの限界と比べ、アプリは結果をもう一度展開して、何も失われていないことを確かめます。
使い方
- テキストを入力または貼り付けるか、例を選びます。段落、サビのある歌、1行のピクセル、データの表、ランダムな文字、DNA があります。
- LZ77、LZW、RLE のいずれかを選びます。LZ77 では、どこまでさかのぼれるかを設定し、強調表示された参照をクリックすると、コピー元の前のテキストがわかります。
- タイルとグラフでサイズを ZIP やエントロピーの限界と比べます。テキストの下のチェックで、展開すると元のテキストに戻ることを確かめられます。
鍵は繰り返し
可逆圧縮がうまくいくのは、現実のデータが同じことを繰り返しているからです。LZ77 は直前に読んだテキストのウィンドウを保持し、次の文字がすでにそのウィンドウに現れていれば、文字そのものの代わりに「これだけ戻って、これだけの文字をコピーせよ」という短い参照を書きます。参照はコピーがどれだけ長くても決まった数のビットしかかからないので、長く頻繁な繰り返しほど多くを節約できます。LZW は同じ効果を別のやり方で得ます。出会った新しい文字列をすべて辞書に登録し、それ以降はその文字列の番号を送るのです。
縮まないデータがある理由
あるファイルを小さくする方法は、必ず別のファイルを大きくしてしまいます。短いファイルは長いファイルより数が少ないので、すべてを短くすることはできないからです。圧縮は、テキストや表、単純な画像のようにパターンのあるデータでは成功し、パターンのないデータでは失敗します。ランダムな文字、暗号化されたデータ、すでに圧縮されたファイルには指し示せる前の部分がなく、出力は入力と同じ大きさか、それより大きくなります。これが最もはっきり現れるのがランレングス符号化で、ランのないテキストではサイズが2倍になります。
よくある質問
可逆圧縮と非可逆圧縮の違いは何ですか?
可逆圧縮は元のデータを1ビットも違わず正確に復元します。テキスト、プログラム、データにはこれが必要で、このデモが扱うのは可逆圧縮だけです。JPEG の写真、MP3 の音楽、動画などの非可逆圧縮は、人がほとんど気づかない細部を捨ててファイルをずっと小さくしますが、元のデータは取り戻せません。
ZIP はどのようにファイルを圧縮するのですか?
ZIP と gzip は deflate を使います。deflate はまず 32 KB のウィンドウで LZ77 を実行し、次にリテラルと参照をハフマン符号で書き出します。よく現れる値には短い符号を、まれな値には長い符号を割り当てるのです。この2段階目があるので、すべてのトークンに決まった数のビットを使うここでの素朴な LZ77 よりも、ZIP のほうがたいてい小さくなります。
LZ77 はエントロピーを下回れますか?
ここで示すエントロピーは、文脈を考えずに文字を1つずつ数えたものです。LZ77 と LZW は文脈を利用します。参照は前のテキストのひと続きをまるごとコピーするので、繰り返しの多いテキストではこの数値を大きく下回ることがあります。ただし、あらゆる文脈を考慮に入れた情報源の真のエントロピーを下回ることは決してできません。
実際の ZIP ファイルとサイズが違うのはなぜですか?
このデモは符号化されたデータのビットだけを数えています。実際の ZIP ファイルにはヘッダー、ファイル名、チェックサム、ハフマン表が加わるので、とても小さなファイルはかえって大きくなります。
テキストはどこかに送信されますか?
いいえ。ZIP との比較も含めてすべての方法がお使いのブラウザー内で実行され、テキストはこのブラウザーのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ