データ圧縮の解説
読み込むすべてのウェブページ、すべての ZIP ファイル、すべての PNG 画像は圧縮されています。1ビットも失わずに小さくされ、届いた先で再び展開されるのです。その裏にある方法は驚くほど単純です。繰り返し現れるものを探し、もう一度言う代わりに「前と同じ」と言うのです。この考えがどこまで通用し、どこで止まるのかは、コンピューター科学で最も見事な物語の1つです。
可逆と非可逆
圧縮には2つの種類があります。可逆圧縮は元のデータを正確に復元します。これはテキスト、プログラム、表計算のデータなど、1ビットの誤りも許されないものには欠かせません。写真、音楽、動画に使われる非可逆圧縮は、人がほとんど知覚できない細部を捨ててはるかに小さなサイズにしますが、元のデータは永久に失われます。このページとデモが扱うのは可逆圧縮です。可逆圧縮は、冗長性、つまりデータのうち予測できたはずの部分を見つけて取り除くことで働きます。
ランレングス符号化
最も単純な方法は、同じ記号の連続を回数とその記号に置き換えるものです。白いピクセル12個は 12W になります。ファクス、初期のビットマップ形式、PCX 画像形式がこれを使っていました。スキャンしたページや単純な図には長いランがたくさんあるからです。普通のテキストではまったく役に立たず、むしろ有害です。ランはまれで、1文字ごとに回数を書くとサイズが2倍になってしまいます。それでもランレングス符号化は、最初の変換のあとに残るゼロの連続を処理するために、ほかの方法の内部で今も生きています。
LZ77:前を指し示す
1977年、イスラエル工科大学(テクニオン)の2人の研究者、アブラハム・レンペルとヤコブ・ジフが、この分野を変える方法を発表しました。符号化器は直前に処理したテキストのウィンドウを保持します。次の文字がすでにウィンドウ内に現れていれば、前のコピーがどれだけ前から始まり、どれだけの長さかという2つの数の組を書きます。そうでなければ文字そのものを書きます。復号器には辞書はまったく必要なく、すでに再構成したテキストさえあれば十分です。参照は、自分が生み出すテキストと重なってもかまいません。そのため、同じ文字が100個続くランは、1文字と1つの参照で表せます。
LZW:辞書を学ぶ
レンペルとジフの2つ目の方法 LZ78 は、ウィンドウをさかのぼる代わりに辞書を作ります。テリー・ウェルチが1984年に改良した LZW は、256通りのバイト値すべてから始め、各ステップで、すでに知っている最も長い文字列の番号を送り、その文字列に次の文字を加えたものを新しい項目として登録します。復号器は番号だけから同じ辞書を再構成します。LZW は高速で単純だったため、Unix の compress コマンド、GIF 画像形式、TIFF ファイルに採用されましたが、1990年代にはその特許をめぐって長い論争が起きました。
deflate、ZIP、そしてその先
フィル・カッツが1993年に PKZIP 2 とともに導入した deflate 方式は、LZ77 とハフマン符号を組み合わせたものです。繰り返しを見つけたあと、最もよく現れるリテラル、長さ、距離に最も短いビット符号を割り当てます。deflate は ZIP、gzip、PNG 画像、ウェブページの圧縮に使われており、このデモがブラウザー自身の圧縮機能で測っているのもこの方式です。Zstandard、Brotli、xz などの新しい方式は、より大きなウィンドウ、より賢い一致検索、より精密なエントロピー符号化を使い、一般的なファイルをさらに10〜30%縮めます。
すべてを縮められない理由
どんな方法も、すべてのファイルを小さくすることはできません。n ビットのファイルは 2ⁿ 個ありますが、それより短いファイルは 2ⁿ − 1 個しかありません。ですから、ある方法がそのすべてを縮めたとすると、2つが同じ結果になり、両方を復元することはできなくなります。これが鳩の巣原理です。そのため、どの圧縮プログラムも一部の入力を大きくしてしまいます。たいていは、暗号化されたファイル、すでに圧縮されたファイル、ノイズのような、ランダムに見えるデータです。これはランダム性の検査にもなります。どの圧縮プログラムでも縮められないデータは、ランダムに見えるのです。
エントロピーの限界
クロード・シャノンは1948年、情報源のエントロピーが、どんな可逆符号でも1記号あたりの平均ビット数の最小値であることを示しました。1文字ずつ数えると、英語の文章のエントロピーは1文字あたり約4ビットで、保存に使われる8ビットの半分です。LZ77 のように文脈を利用する方法は、参照がひと続きの部分をまとめて表すので、繰り返しの多いテキストではこの1文字単位の値を下回ります。それまでのすべてから各文字を予測する最高の現代の圧縮プログラムは、英語を1文字あたり2ビット未満にまで縮めます。
試してみよう
圧縮デモを開いて、段落、サビのある歌、1行のピクセル、データの表、ランダムな文字、DNA、あるいは自分のテキストで LZ77、LZW、ランレングス符号化を実行してみましょう。LZ77 の参照をクリックすれば何をコピーしているかがわかり、LZW の辞書が育っていく様子を見ながら、すべての方法を ZIP やエントロピーの限界と比べられます。
よくある質問
圧縮比 3 : 1 とはどういう意味ですか?
元のデータが圧縮版の3倍の大きさだということです。つまり圧縮したファイルは3分の1の容量で済み、3分の2を節約できます。テキストは ZIP でふつう 2 : 1 から 4 : 1 になり、ログファイルのように繰り返しの多いデータでは、それをはるかに超えることもよくあります。
ZIP ファイルをもう一度圧縮しても効果がないのはなぜですか?
1回目ですでに繰り返しが取り除かれ、その出力はほとんどランダムに見えます。2回目は指し示せるものを何も見つけられず、自分のオーバーヘッドを加えるだけなので、ファイルは同じサイズのままか、少し大きくなります。
LZ77 のウィンドウは大きいほうがよいのはなぜですか?
ウィンドウが大きければ、何番かの歌詞のあとに戻ってくるサビのように、もっと前にある繰り返しも見つけられます。その代わり、距離を書くのに必要なビット数が増え、探索にも時間がかかります。そのため deflate は 32 KB までにとどめ、新しい方式ではメガバイト単位が使えます。
圧縮は暗号化と同じですか?
いいえ。圧縮はデータを小さくするもので、誰でも元に戻せます。暗号化は、鍵がなければデータを読めなくするものです。両者はよく組み合わされますが、その場合は先に圧縮しなければなりません。暗号化されたデータはランダムに見え、もう圧縮できないからです。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
圧縮デモを開く