可逆圧縮

Poll without page-refresh

Article on other languages:

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

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

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

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

可逆圧縮の限界

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

文字などのデータ列の記号を単位として考え、それがある確率分布に従って独立に現れるという仮定を置けば、圧縮の上限はその分布のエントロピーによって与えられる。しかし、例えば英語の文章を対象としたときには、文字 q が現れれば多くの場合その次は u であり、逆に s の次に r が現れることはほとんどない。よって、文字の分布から独立に選ばれるとの仮定は圧縮を限界づけるには不十分である。複数の文字を単位とするなどより細かい分布を考えていけば分布のエントロピーは小さくなるものの、逆に圧縮・展開のプログラムは大きなものとなっていく。アルゴリズム情報理論によれば、一般にデータ列が与えられたとき展開のプログラムの大きさも含めてそれが究極的にどれだけ圧縮できるかを求めるという問題は計算不能な事柄である。

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

可逆圧縮

可逆圧縮の限界

関連項目