可逆圧縮: データ圧縮方法の一つ。ロスレス圧縮
可逆圧縮（かぎゃくあっしゅく）とは、圧縮前のデータと、圧縮・展開の処理を経たデータが完全に等しくなるデータ圧縮方法のこと。ロスレス圧縮（ロスレスあっしゅく）、無歪み圧縮（むゆがみあっしゅく）とも呼ばれる。
アルゴリズム
すべてのデータを効果的に圧縮できる可逆圧縮アルゴリズムは存在しない（可逆圧縮の限界の節を参照）。そのため、データの種類によって多くのアルゴリズムが存在する。下記に主要な可逆圧縮方式を列挙する。
データ全般
- 算術符号 - エントロピー符号の一種
- ハフマン符号 - エントロピー符号の一種
- LZ77、LZ78 - 辞書式圧縮の一種
- Lempel-Ziv-Markov chain-Algorithm (LZMA) - 7z、xzで使用される
- Lempel–Ziv–Storer–Szymanski (LZSS) - WinRARでハフマン符号とともに使用される
- Lempel–Ziv–Welch (LZW) - GIF、UNIX Compressで使用される
- ブロックソート - 圧縮の前処理で使用される可逆変換
- Prediction by Partial Matching (PPM) - プレーンテキストの圧縮で使用される
- 連長圧縮
音声
- ATRAC Advanced Lossless (AAL)
- Apple Lossless (ALAC)
- FLAC
- Monkey's Audio (APE)
- MPEG-4 ALS
- MPEG-4 SLS
- Shorten (SHN)
- TTA
- WavPack
- Windows Media Audio Lossless
ラスターイメージ
- AV1 Image File Format (AVIF)
- JPEG XL - ロスレスモードあり
- JPEG XR - ロスレスモードあり
- Lossless JPEG
- Portable Network Graphics (PNG)
- QOI
- Tagged Image File Format (TIFF)
- WebP
可逆圧縮の限界
可逆圧縮アルゴリズムはすべての入力データに対して圧縮後のデータサイズが圧縮前より小さいことを保証できない。すなわち、どのような可逆圧縮アルゴリズムでも圧縮処理後にデータサイズが小さくならない入力データが存在し、また圧縮処理後にデータサイズが小さくなる入力データが存在する場合、圧縮処理後にデータサイズが大きくなる入力データも必ず存在する。前者の証明は下記の通り。
- すべての入力データを小さくできるアルゴリズムの場合、アルゴリズムを繰り返して適用することでデータサイズを1ビットにできる。
- しかし、1ビットでは記録できる情報が2種類しかなく、解凍が明らかに不可能である。
- したがって、前提である「すべての入力データを小さくできるアルゴリズムが存在する」が成立しない。
後者の証明は鳩の巣原理を用いたものであり、下記の通りとなっている。
- 「圧縮処理後にデータサイズが小さくなる入力データが存在し、圧縮処理後にデータサイズが大きくなる入力データが存在しない」と仮定する。
- 圧縮処理後にデータサイズが小さくなる入力データのうち、最も小さい入力データをFとし、そのデータサイズをMとする。Fの圧縮処理後のデータサイズをNとする（MとNの単位はビット）。
- 圧縮処理後にデータサイズが小さくなるため、N < Mである。さらに圧縮処理後にデータサイズが大きくなる入力データが存在しないため、Nビットのデータは圧縮処理後もNビットとなる。
- Nビットのデータは2N種類ある。前述のNと合わせ、圧縮処理後にNビットとなるデータは少なくとも2N+1種類存在する。
- しかしNビットのデータが2N種類しかないので、鳩の巣原理により少なくとも2種類のデータが圧縮後同じデータになり、解凍が不可能（どちらに戻すべきか判別できない）である。
- したがって最初の仮定は誤りであり、「圧縮処理後にデータサイズが小さくなる入力データが存在しない」（可逆圧縮アルゴリズムではない）か「圧縮処理後にデータサイズが大きくなる入力データが存在する」となる。
このようにすべてのデータを圧縮できるアルゴリズムは数学上存在しえないが、インターネット・バブル期にはAdam's Platform（1998年）、NearZero（2001年）などそのようなアルゴリズムを発明したと主張するベンチャーが複数存在した。実際の処理では圧縮を行わず、入力データを別のフォルダにコピーし、「圧縮」された偽ファイルに置き換えただけであり、「解凍」のときは別のフォルダにコピーした入力データを元に戻しただけである。
可逆圧縮アルゴリズムのベンチマークにはカルガリーコーパスが広く使われている。サイズ、速度、メモリ使用量がトレードオフの関係にあり、たとえばデータ圧縮比が高いアルゴリズムはメモリ使用量が多い場合が多い。
出典
関連項目
This article uses material from the Wikipedia 日本語 article 可逆圧縮, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). コンテンツは、特に記載されていない限り、CC BY-SA 4.0のもとで利用可能です。 Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki 日本語 (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.