可逆圧縮 - Wikipedia可逆圧縮アルゴリズムはすべての入力データに対して圧縮後のデータサイズが圧縮前より小さいことを保証できない。すなわち、どのような可逆圧縮アルゴリズムでも圧縮処理後にデータサイズが小さくならない入力データが存在し、また圧縮処理後にデータサイズが小さくなる入力データが存在する場合、圧縮処理後にデータサイズが大きくなる入力データも必ず存在する。前者の証明は下記の通り[3]。 すべての入力データを小さくできるアルゴリズムの場合、アルゴリズムを繰り返して適用することでデータサイズを1ビットにできる。 しかし、1ビットでは記録できる情報が2種類しかなく、解凍が明らかに不可能である。 したがって、前提である「すべての入力データを小さくできるアルゴリズムが存在する」が成立しない。 後者の証明は鳩の巣原理を用いたものであり、下記の通りとなっている[3][4]。 「圧縮処理後にデータサイズが小さくなる入力データ
