Search

可逆圧縮

データ圧縮方法の一つ。ロスレス圧縮

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

アルゴリズムとしては連長圧縮、ハフマン符号、LZWなどが有名。

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

アルゴリズム

「Category:可逆圧縮アルゴリズム」も参照

すべてのデータを効果的に圧縮できる可逆圧縮アルゴリズムは存在しない（可逆圧縮の限界の節を参照）。そのため、データの種類によって多くのアルゴリズムが存在する。下記に主要な可逆圧縮方式を列挙する。

データ全般

音声

ラスターイメージ

可逆圧縮の限界

可逆圧縮アルゴリズムはすべての入力データに対して圧縮後のデータサイズが圧縮前より小さいことを保証できない。すなわち、どのような可逆圧縮アルゴリズムでも圧縮処理後にデータサイズが小さくならない入力データが存在し、また圧縮処理後にデータサイズが小さくなる入力データが存在する場合、圧縮処理後にデータサイズが大きくなる入力データも必ず存在する。前者の証明は下記の通り[3]。

  1. すべての入力データを小さくできるアルゴリズムの場合、アルゴリズムを繰り返して適用することでデータサイズを1ビットにできる。
  2. しかし、1ビットでは記録できる情報が2種類しかなく、解凍が明らかに不可能である。
  3. したがって、前提である「すべての入力データを小さくできるアルゴリズムが存在する」が成立しない。

後者の証明は鳩の巣原理を用いたものであり、下記の通りとなっている[3][4]。

  1. 「圧縮処理後にデータサイズが小さくなる入力データが存在し、圧縮処理後にデータサイズが大きくなる入力データが存在しない」と仮定する。
  2. 圧縮処理後にデータサイズが小さくなる入力データのうち、最も小さい入力データをFとし、そのデータサイズをMとする。Fの圧縮処理後のデータサイズをNとする（MとNの単位はビット）。
  3. 圧縮処理後にデータサイズが小さくなるため、N < Mである。さらに圧縮処理後にデータサイズが大きくなる入力データが存在しないため、Nビットのデータは圧縮処理後もNビットとなる。
  4. Nビットのデータは2N種類ある。前述のNと合わせ、圧縮処理後にNビットとなるデータは少なくとも2N+1種類存在する。
  5. しかしNビットのデータが2N種類しかないので、鳩の巣原理により少なくとも2種類のデータが圧縮後同じデータになり、解凍が不可能（どちらに戻すべきか判別できない）である。
  6. したがって最初の仮定は誤りであり、「圧縮処理後にデータサイズが小さくなる入力データが存在しない」（可逆圧縮アルゴリズムではない）か「圧縮処理後にデータサイズが大きくなる入力データが存在する」となる。

このようにすべてのデータを圧縮できるアルゴリズムは数学上存在しえないが、インターネット・バブル期にはAdam's Platform（1998年）、NearZero（2001年）などそのようなアルゴリズムを発明したと主張するベンチャーが複数存在した[3]。実際の処理では圧縮を行わず、入力データを別のフォルダにコピーし、「圧縮」された偽ファイルに置き換えただけであり、「解凍」のときは別のフォルダにコピーした入力データを元に戻しただけである[3]。

可逆圧縮アルゴリズムのベンチマークにはカルガリーコーパス（英語版）が広く使われている[5][6]。サイズ、速度、メモリ使用量がトレードオフの関係にあり、たとえばデータ圧縮比が高いアルゴリズムはメモリ使用量が多い場合が多い[6]。

出典

関連項目

「https:https://www.search.com.vn/wiki/index.php?lang=ja&q=可逆圧縮&oldid=99594834」から取得
🔥 Top keywords: メインページ宮崎麗果特別:検索豊後水道松本忠久土居志央梨若葉竜也能登半島地震 (2024年)田中雄士長谷部誠井上道義The GazettE若林志穂服部百音黒木啓司REITA虎に翼平井理央出口夏希サーブ (盲導犬)三鷹事件セウォル号沈没事故白眞勲三淵嘉子高橋克也 (オウム真理教)ME:Iルーシー・ブラックマン事件佐藤ありさ杉咲花蜜谷浩弥水野真紀亀井亜紀子 (政治家)熊本地震 (2016年)水原一平井川意高中川安奈 (アナウンサー)内藤剛志いなば食品YOSHIKI