可逆圧縮
Nビットのデータは2種類ある。前述のNと合わせ、圧縮処理後にNビットとなるデータは少なくとも2+1種類存在する。
しかしNビットのデータが2種類しかないので、鳩の巣原理により少なくとも2種類のデータが圧縮後同じデータになり、解凍が不可能(どちらに戻すべきか判別できない)である。
したがって最初の仮定は誤りであり、「圧縮処理後にデータサイズが小さくなる入力データが存在しない」(可逆圧縮アルゴリズムではない)か「圧縮処理後にデータサイズが大きくなる入力データが存在する」となる。
このようにすべてのデータを圧縮できるアルゴリズムは数学上存在しえないが、インターネット・バブル期にはAdam's Platform(1998年)、NearZero(2001年)などそのようなアルゴリズムを発明したと主張するベンチャーが複数存在した。実際の処理では圧縮を行わず、入力データを別のフォルダにコピーし、「圧縮」された偽ファイルに置き換えただけであり、「解凍」のときは別のフォルダにコピーした入力データを元に戻しただけである。
可逆圧縮アルゴリズムのベンチマークにはカルガリーコーパス(英語版)が広く使われている。サイズ、速度、メモリ使用量がトレードオフの関係にあり、たとえばデータ圧縮比が高いアルゴリズムはメモリ使用量が多い場合が多い。