可逆圧縮
データ圧縮方法の一つ。ロスレス圧縮 ウィキペディアから
データ圧縮方法の一つ。ロスレス圧縮 ウィキペディアから
可逆圧縮(かぎゃくあっしゅく)とは、圧縮前のデータと、圧縮・展開の処理を経たデータが完全に等しくなるデータ圧縮方法のこと[1]。ロスレス圧縮[1](ロスレスあっしゅく)、無歪み圧縮(むゆがみあっしゅく)[2]とも呼ばれる。
すべてのデータを効果的に圧縮できる可逆圧縮アルゴリズムは存在しない(可逆圧縮の限界の節を参照)。そのため、データの種類によって多くのアルゴリズムが存在する。下記に主要な可逆圧縮方式を列挙する。
可逆圧縮アルゴリズムはすべての入力データに対して圧縮後のデータサイズが圧縮前より小さいことを保証できない。すなわち、どのような可逆圧縮アルゴリズムでも圧縮処理後にデータサイズが小さくならない入力データが存在し、また圧縮処理後にデータサイズが小さくなる入力データが存在する場合、圧縮処理後にデータサイズが大きくなる入力データも必ず存在する。前者の証明は下記の通り[3]。
後者の証明は鳩の巣原理を用いたものであり、下記の通りとなっている[3][4]。
このようにすべてのデータを圧縮できるアルゴリズムは数学上存在しえないが、インターネット・バブル期にはAdam's Platform(1998年)、NearZero(2001年)などそのようなアルゴリズムを発明したと主張するベンチャーが複数存在した[3]。実際の処理では圧縮を行わず、入力データを別のフォルダにコピーし、「圧縮」された偽ファイルに置き換えただけであり、「解凍」のときは別のフォルダにコピーした入力データを元に戻しただけである[3]。
可逆圧縮アルゴリズムのベンチマークにはカルガリーコーパスが広く使われている[5][6]。サイズ、速度、メモリ使用量がトレードオフの関係にあり、たとえばデータ圧縮比が高いアルゴリズムはメモリ使用量が多い場合が多い[6]。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.