Ｆａｓｃｉｎａｔｉｏｎ Ｎ−Ｄ−Ｆｉｌｅ　可逆圧縮

可逆圧縮（かぎゃくあっしゅく）とは、圧縮前のデータと、圧縮・展開の処理を経たデータが完全に等しくなるデータ圧縮方法の事。ロスレス圧縮とも呼ばれる。

アルゴリズムとしてはランレングス、ハフマン符号、LZW等が有名。

コンピュータ上でよく扱われるLZH、ZIP、CABや、画像圧縮形式のPNG、音声圧縮形式のFLAC、TTAなどが可逆圧縮である。

可逆圧縮の限界

理論的には、可逆な形ですべてのデータ列を圧縮するような方法は存在しない。 すなわち、どんな可逆圧縮プログラムに対しても、それがあるデータ列を確かに圧縮するならば、ある別のデータ列が存在して、その列に対してはプログラムで処理する前より後のほうが長くなってしまう。 なぜなら、ある長さのデータ列の総数はそれよりも短いデータ列の総数よりも必ず多いからである。 それどころか 1 ビットでも縮められるデータ列はたかだか全体の半分であり、10 ビット縮められるものは全体のおよそ 1000 分の 1 にすぎない。 ただし、長くなるデータ列でも極端に長くなるようなことはない。 例えば、適当な (1 ビットの) フラグを付加して、あるアルゴリズムで圧縮できたデータ列とできなかったデータ列を区別するように出来るからである。

可逆圧縮プログラムがほとんどのデータ列をほとんど圧縮できないということは、我々が実際に接する圧縮アルゴリズムの成績の印象とは大きく異なっている。 これは日常われわれが圧縮を求めるようなデータ列の分布が非常に偏ったものであるからである。 すなわち可逆圧縮アルゴリズムが良いものとなるかどうかは、その日常的なデータ列の偏りをうまくかつ高速に抽出できるかどうかに依存している。