可逆圧縮
可逆圧縮(かぎゃくあっしゅく)とは、圧縮前のデータと、圧縮・展開の処理を経たデータが完全に等しくなるデータ圧縮方法のこと。ロスレス圧縮とも呼ばれる。
アルゴリズムとしてはランレングス、ハフマン符号、LZWなどが有名。
コンピュータ上でよく扱われるLZH、ZIP、CABや、画像圧縮形式のPNG、GIF、動画圧縮形式のHuffyuv、音声圧縮形式のWindows Media Audio Lossless、Apple Lossless、ATRAC Advanced Lossless(AAL)、FLAC、TAK、TTA、Dolby TrueHD、DTS-HDマスターオーディオ、Meridian Lossless Packing、Monkey's Audio、Shorten、mp3HD、WavPack などが可逆圧縮である。
可逆圧縮の限界
可逆圧縮アルゴリズムは、データの冗長性を排除するために、データ列の偏りや法則性を見つけ出すように設計されており、大きな偏りや明確な法則性を持つデータであれば大幅にデータサイズを圧縮する事ができる。従って、ホワイトノイズ等の、明確な構造を持たない極めて乱雑な情報のみを含むデータを圧縮することを考えると、全く圧縮する事が出来ない事が分かる。しかし、人間に取って意味を持つデータは、必ず何らかの構造を含んでおり、大きな偏りや明確な法則性を持つため、人間が日常的に用いるデータに関しては可逆圧縮アルゴリズムが上手く機能する。
乱雑度が高く、冗長性の低いデータを圧縮しようとすると、圧縮後にデータサイズが大きくなってしまう事も考えられる。しかしこの場合は圧縮に向かないデータ列のみ無圧縮で記録する事によって、圧縮後にデータサイズが大きくなる事を回避する事ができる。
可逆圧縮アルゴリズムの実用性に関する評価基準は、データの冗長性を的確かつ高速に抽出できるかどうかである。ある可逆圧縮アルゴリズムがデータを大きく圧縮できたとしても、圧縮完了までに天文学的な時間を要する場合は実用性が無いと言える。
アルゴリズム情報理論によれば、冗長性の形態には無限の可能性が考えられ、また圧縮・展開するプログラムそのものの情報量が大きくなることも想定できるため、世界に存在する全てのデータを限界まで小さく圧縮できる可逆圧縮プログラムは実現不可能である。
関連項目
- 非可逆圧縮
- エントロピー符号
Apple Lossless (ALAC)
ATRAC Advanced Lossless (AAL)- Windows Media Audio Lossless
- TAK
- TTA
Monkey's Audio (APE)- FLAC
- WavPack
- PNG
Shorten(SHN)- コルモゴロフ複雑性
- 差分符号化
- 最適化 (情報工学)
|