可逆圧縮(かぎゃくあっしゅく)とは、圧縮前のデータと、圧縮・展開の処理を経たデータが完全に等しくなるデータ圧縮方法のこと[1]。ロスレス圧縮[1](ロスレスあっしゅく)、無歪み圧縮(むゆがみあっしゅく)[2]とも呼ばれる。
アルゴリズムとしては連長圧縮、ハフマン符号、LZWなどが有名。
コンピュータ上でよく扱われるLZH、ZIP、CABや、画像圧縮形式のPNG、GIFなどが可逆圧縮である[1]。
アルゴリズム「Category:可逆圧縮アルゴリズム」も参照
すべてのデータを効果的に圧縮できる可逆圧縮アルゴリズムは存在しない(可逆圧縮の限界の節を参照)。そのため、データの種類によって多くのアルゴリズムが存在する。下記に主要な可逆圧縮方式を列挙する。
データ全般
算術符号 - エントロピー符号の一種
ハフマン符号 - エントロピー符号の一種
LZ77、LZ78 - 辞書式圧縮
可逆圧縮アルゴリズムはすべての入力データに対して圧縮後のデータサイズが圧縮前より小さいことを保証できない。すなわち、どのような可逆圧縮アルゴリズムでも圧縮処理後にデータサイズが小さくならない入力データが存在し、また圧縮処理後にデータサイズが小さくなる入力データが存在する場合、圧縮処理後にデータサイズが大きくなる入力データも必ず存在する。前者の証明は下記の通り[3]。
すべての入力データを小さくできるアルゴリズムの場合、アルゴリズムを繰り返して適用することでデータサイズを1ビットにできる。
しかし、1ビットでは記録できる情報が2種類しかなく、解凍が明らかに不可能である。
したがって、前提である「すべての入力データを小さくできるアルゴリズムが存在する」が成立しない。
後者の証明は鳩の巣原理を用いたものであり、下記の通りとなっている[3][4]。
「圧縮処理後にデータサイズが小さくなる入力データが存在し、圧縮処理後にデータサイズが大きくなる入力データが存在しない」と仮定する。
圧縮処理後にデータサイズが小さくなる入力データのうち、最も小さい入力データをFとし、そのデータサイズをMとする。Fの圧縮処理後のデータサイズをNとする(MとNの単位はビット)。