可逆圧縮は、圧縮したデータから元のデータを完全に復元できる圧縮です。見た目がほぼ同じという意味ではなく、定めた復元手順で元のデータが一致することを求めます。
繰り返しをまとめる模型
AAAAABBBCCという文字列を、「Aが5回、Bが3回、Cが2回」と表す方法を考えます。記号と回数の区切り方をあらかじめ決めれば、元の並びを復元できます。これはランレングス符号化の発想です。
ただしABCのように繰り返しが少ない列をA1B1C1と書けば、かえって長くなるかもしれません。数字や区切りの保存にも容量が必要です。実際のバイト数は文字の符号化やファイル形式も含めて比べます。
1
AAAAABBBCC
2
A×5・B×3・C×2という表現
3
復号すると元の列と一致
すべての入力を必ず短くできない理由
固定長nビットの異なる列は2ⁿ通りあります。それらをすべてnビット未満の異なる列へ割り当てることはできません。短い列の総数が足りず、同じ圧縮結果を持つ元データが生じれば、一意に復元できなくなるからです。
実際の圧縮は、よく現れるパターンを利用して、想定するデータで平均的に効率を上げます。元から圧縮されているファイルをもう一度圧縮しても、大きく減るとは限りません。
非可逆圧縮・暗号化との違い
非可逆圧縮は、一部の情報を捨てることを許して容量を抑えます。暗号化の主目的は内容を読める相手を制限することで、容量を減らすことではありません。どちらも表現を変えますが目的と復元条件が違います。
よくある疑問
ZIPなら必ず小さくなりますか？
いいえ。データの性質や付加情報によって、ほとんど変わらない場合や増える場合もあります。復元が一致することと圧縮率は別の性質です。
参考資料
定義と論点を確認するための資料です。本文の身近な場面と数値は、理解のために作成した例です。