可逆圧縮

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

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

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

コンピュータ上でよく扱われるLZHZIPCABや、画像圧縮形式のPNGGIF動画圧縮形式のHuffyuv音声圧縮形式のWindows Media Audio LosslessApple LosslessATRAC Advanced Lossless(AAL)FLACTAKTTADolby TrueHDDTS-HDマスターオーディオMeridian Lossless PackingMonkey's AudioShortenmp3HDWavPack などが可逆圧縮である。

可逆圧縮の限界

汎用の可逆圧縮アルゴリズムは、データ列の偏りや法則性を見つけ出す工程があり、偏りや法則性が多い程小さく圧縮する事ができる。そのため世のあらゆるデータを圧縮すると仮定するなど、空想上で全く偏りの無いランダムなデータを圧縮すると、全く圧縮する事が出来ない。 逆に考えれば、日常われわれが圧縮を求めるようなデータは数値的に非常に偏った、あるいは規則的なもの、すなわち冗長性を持つ事が分かる。

冗長性の無いデータを無理に圧縮しようとすると、余計に大きくなってしまう事も考えられる。しかしこの場合は圧縮しづらいデータ列のみ無加工で記録する事によって、極端に大きくなる事を回避する事ができる。

またアルゴリズム情報理論によれば、冗長性の形態には無限の可能性が考えられ、また圧縮・展開するプログラムそのものの情報量が大きくなることも想定できるため、どんなデータをも限界まで小さく圧縮できる可逆圧縮プログラムは実現不可能である。

すなわち、可逆圧縮アルゴリズムがよいものとなるかどうかは、その日常的なデータの冗長性をうまくかつ高速に抽出できるかどうかに依存している。

関連項目

テンプレート:データ圧縮