Loading article…
可逆圧縮は、圧縮されたデータから元のデータを情報損失なく完全に復元できるデータ圧縮の一種です。可逆圧縮は、現実世界のほとんどのデータが統計的冗長性を示すため可能です。[ 1 ] 対照的に、非可逆圧縮では、元のデータの近似値しか復元できませんが、通常は圧縮率が大幅に向上し（したがってメディアサイズが小さくなります）。
鳩の巣原理の作用により、可逆圧縮アルゴリズムではすべてのデータのサイズを縮小することはできません。一部のデータは少なくとも1シンボルまたは1ビット長くなります。
圧縮アルゴリズムは通常、人間が読みやすい文書や機械が読みやすい文書に対して効果的であり、冗長性のないランダムなデータのサイズを縮小することはできません。特定の種類の入力データを想定して設計されたものや、圧縮されていないデータに含まれる可能性のある冗長性の種類に関する特定の仮定に基づいて設計されたものなど、さまざまなアルゴリズムが存在します。
可逆データ圧縮は多くのアプリケーションで使用されています。たとえば、ZIPファイル形式やGNUツールgzipで使用されています。また、ロッシーデータ圧縮技術の構成要素としてもよく使用されます（たとえば、 MP3エンコーダやその他のロッシーオーディオエンコーダによるロッシーミッド/サイドジョイントステレオ前処理など）。 [ 2 ]
可逆圧縮は、元のデータと解凍後のデータが完全に一致することが重要な場合、または元のデータからのずれが好ましくない場合に使用されます。一般的な例としては、実行可能プログラム、テキスト文書、ソースコードなどがあります。PNGやGIFなどの画像ファイル形式は可逆圧縮のみを使用しますが、TIFFやMNGなどの形式は可逆圧縮と非可逆圧縮の両方を使用する場合があります。可逆オーディオ形式は、アーカイブや制作目的でよく使用されますが、非可逆オーディオファイルは、通常、ポータブルプレーヤーや、ストレージ容量が限られている場合、またはオーディオの完全な複製が不要な場合に使用されます。
ほとんどの可逆圧縮プログラムは、2つのことを順番に行います。最初のステップでは、入力データの統計モデルを生成し、2番目のステップでは、このモデルを使用して入力データをビット列にマッピングします。これにより、「可能性の高い」（つまり頻繁に遭遇する）データは、「可能性の低い」データよりも短い出力を生成します。
ビット列を生成するために使用される主な符号化アルゴリズムは、ハフマン符号化（ deflateアルゴリズムでも使用される）と算術符号化です。算術符号化は、情報エントロピーによって与えられる特定の統計モデルに対して可能な限り最高の圧縮率を実現しますが、ハフマン圧縮はより単純で高速ですが、シンボル確率が1に近いモデルでは結果が悪くなります。
統計モデルを構築する主な方法は 2 つあります。静的モデルでは、データを分析してモデルを構築し、そのモデルを圧縮データとともに保存します。このアプローチはシンプルでモジュール化されていますが、モデル自体の保存コストが高くなる可能性があり、また、圧縮されるすべてのデータに対して単一のモデルを使用する必要があるため、異種データを含むファイルではパフォーマンスが低下するという欠点があります。適応型モデルでは、データが圧縮されるにつれてモデルが動的に更新されます。エンコーダとデコーダはどちらも単純なモデルから開始するため、初期データの圧縮率は低くなりますが、データについて学習するにつれてパフォーマンスが向上します。現在、実務で使用されている最も一般的な圧縮方式は、適応型コーダーを使用しています。
可逆圧縮方式は、圧縮対象データの種類に応じて分類できます。原則として、汎用的な可逆圧縮アルゴリズム（汎用とは、任意のビット列を受け入れることができるという意味です）は、あらゆる種類のデータに使用できますが、多くの場合、圧縮対象として設計された形式ではないデータに対しては、十分な圧縮効果が得られません。テキストに使用される可逆圧縮技術の多くは、インデックスカラー画像にも比較的うまく機能します。
これらの技術は、類似したトーンの連続する2次元領域という一般的な現象など、画像の特定の特性を利用します。最初のピクセルを除くすべてのピクセルは、左隣のピクセルとの差分に置き換えられます。これにより、小さな値が大きい値よりもはるかに高い確率で出現するようになります。これは音声ファイルにもよく適用され、主に低周波数と低音量のファイルを含むファイルを圧縮できます。画像の場合、この手順は最上位のピクセルとの差分を取ることで繰り返され、ビデオの場合は、次のフレームのピクセルとの差分を取ることができます。
適応型エンコーディングでは、音声エンコーディングでは前のサンプルからの確率、画像エンコーディングでは左と上のピクセルからの確率、さらにビデオエンコーディングでは前のフレームからの確率を使用します。ウェーブレット変換では、確率は階層を通して渡されます。[ 3 ]
これらの方法の多くは、オープンソースおよびプロプライエタリなツール、特にLZWとその派生版に実装されています。一部のアルゴリズムは米国およびその他の国で特許を取得しており、合法的に使用するには特許権者によるライセンスが必要です。特定の種類のLZW圧縮に関する特許、特に特許権者であるUnisysによるライセンス慣行が多くの開発者から濫用的であるとみなされたため、一部のオープンソース支持者は、静止画像ファイルの圧縮にGraphics Interchange Format （GIF）を使用することを避け、 LZ77ベースのdeflateアルゴリズムとドメイン固有の予測フィルタの組み合わせであるPortable Network Graphics（PNG）を使用するよう人々に勧めていました。しかし、LZWの特許は2003年6月20日に失効しました。[ 4 ]
テキストに使用される多くの可逆圧縮技術は、インデックス付き画像にもかなり有効ですが、一般的なテキストには適さないものの、一部の画像（特に単純なビットマップ）には有効な技術や、画像の特定の特性（類似したトーンの連続する2次元領域という一般的な現象や、カラー画像は通常、色空間で表現可能な色のうち限られた範囲の色が大部分を占めているという事実など）を利用する技術もあります。
前述のとおり、可逆音声圧縮はやや特殊な分野です。可逆音声圧縮アルゴリズムは、データの波状の性質によって示される繰り返しパターンを利用できます。これは基本的に自己回帰モデルを使用して「次の」値を予測し、予測値と実際のデータの間の（おそらく小さな）差をエンコードします。予測値と実際のデータの間の差（誤差と呼ばれる）が小さい場合、特定の差の値（サンプル値の0、+1、-1など）が非常に頻繁に現れるため、それを少数の出力ビットでエンコードすることで利用できます。
ファイル（またはビデオ圧縮の場合は、連続する画像）の2つのバージョン間の差分のみを圧縮することが有益な場合があります。これはデルタ符号化（数学で差分を表すギリシャ文字Δに由来）と呼ばれますが、この用語は通常、圧縮と解凍以外の目的で両方のバージョンが意味を持つ場合にのみ使用されます。たとえば、前述のロスレス音声圧縮方式における誤差の圧縮プロセスは、近似音波から元の音波へのデルタ符号化として説明できますが、音波の近似バージョンは他の文脈では意味を持ちません。
可逆圧縮アルゴリズムは、あらゆるデータを効率的に圧縮することはできません。そのため、特定の種類の入力データを念頭に置いて設計されたものや、非圧縮データに含まれる可能性のある冗長性の種類に関する特定の仮定に基づいて設計されたものなど、さまざまなアルゴリズムが存在します。
最も一般的な可逆圧縮アルゴリズムを以下に示します。
compressユーティリティで使用されるロスレスビデオコーデックの一覧を参照してください
暗号システムは、セキュリティを強化するために、暗号化の前にデータ（「平文」）を圧縮することがよくあります。適切に実装された場合、圧縮は暗号解読を容易にする可能性のあるパターンを除去することで、一意性距離を大幅に増加させます。[ 9 ]しかし、多くの一般的な可逆圧縮アルゴリズムは、ヘッダー、ラッパー、テーブル、またはその他の予測可能な出力を生成し、それが逆に暗号解読を容易にする可能性があります。したがって、暗号システムは、これらの予測可能なパターンを含まない出力を生成する圧縮アルゴリズムを使用する必要があります。
遺伝子圧縮アルゴリズム（遺伝的アルゴリズムと混同しないように）は、従来の圧縮アルゴリズムと遺伝子データに適応した特定のアルゴリズムの両方を使用してデータ（通常はヌクレオチドの配列）を圧縮する最新世代のロスレスアルゴリズムです。2012年、ジョンズ・ホプキンス大学の科学者チームは、圧縮に外部遺伝子データベースに依存しない最初の遺伝子圧縮アルゴリズムを発表しました。HAPZIPPERはHapMapデータ用に調整されており、20倍以上の圧縮（ファイルサイズが95%削減）を実現し、主要な汎用圧縮ユーティリティよりもはるかに高速に2～4倍優れた圧縮を提供します。[ 10 ]
ゲノム配列圧縮アルゴリズム（DNA配列圧縮器とも呼ばれる）は、DNA配列が逆反復などの特徴的な性質を持っているという事実を利用しています。最も成功している圧縮器はXMとGeCoです。[ 11 ]真核生物の場合、XMは圧縮率でわずかに優れていますが、100MBを超える配列では 計算要件が非現実的です。
自己解凍型実行ファイルには、圧縮されたアプリケーションと解凍プログラムが含まれています。実行されると、解凍プログラムが透過的に元のアプリケーションを解凍して実行します。これは特にデモコーディングでよく使用され、1キロバイトという厳しいサイズ制限のあるデモのコンテストで用いられます。このタイプの圧縮はバイナリ実行ファイルに限定されるものではなく、 JavaScriptなどのスクリプトにも適用できます。
可逆圧縮アルゴリズムとその実装は、直接比較ベンチマークで定期的にテストされています。よく知られている圧縮ベンチマークは数多く存在します。ベンチマークの中には、データ圧縮率のみを評価するものもあり、そのため、これらのベンチマークで最高性能を発揮するものは、処理速度が遅いため、日常的な使用には適さない場合があります。また、ベンチマークによってはデータファイルが既知であるため、プログラム開発者が特定のデータセットで最高のパフォーマンスを発揮するようにプログラムを最適化する可能性があるという欠点もあります。これらのベンチマークで最高性能を発揮するのは、多くの場合、コンテキストミキシング圧縮ソフトウェアのクラスに属します。
マット・マホニーは、2010年2月版の無料小冊子「データ圧縮の説明」の中で、さらに以下の項目を挙げている。[ 12 ]
圧縮評価ウェブサイトは、圧縮比と時間の「フロンティア」のチャート概要を公開した。[ 13 ]
シレジアコーパスは、カンタベリーコーパスとカルガリーコーパスが現代のファイルをどれだけ適切に表現しているかという懸念に基づき、 2003年にこれらの代替として作成されたファイルコレクションです。これには、大きなテキスト文書、実行可能ファイル、データベースなど、さまざまなデータタイプが含まれています。[ 14 ]データ圧縮の研究で広く使用されています。[ 15 ]
このコーパスは12個のファイルで構成され、合計サイズは211MBです。これらのファイルは、コンピュータプログラムやデータベースなど、時間の経過とともにサイズが急速に増加する可能性が高いと著者が考えたデータタイプと、大きなテキストファイルなどのより伝統的な圧縮ベンチマークを代表するものとして選択されました。[ 14 ]
データ型の選択肢がより幅広く、より現代的であるため、カルガリーコーパスと比較した場合、圧縮アルゴリズムのテストデータとしてより優れたソースであると考えられています。[ 16 ]
可逆データ圧縮アルゴリズムは、すべての入力データセットの圧縮を保証することはできません。言い換えれば、どの可逆データ圧縮アルゴリズムでも、アルゴリズムで処理しても小さくならない入力データセットが存在し、少なくとも 1 つのファイルを小さくする可逆データ圧縮アルゴリズムでも、少なくとも 1 つのファイルを大きくすることになります。これは、鳩の巣原理と呼ばれる計数論法を用いた初等数学で簡単に証明できます。以下はその例です。[ 17 ] [ 18 ]
ほとんどの実用的な圧縮アルゴリズムには、エンコードによってファイルサイズが大きくなる場合に通常のエンコードを無効にする「エスケープ」機能が備わっています。理論的には、デコーダーに通常のエンコードが入力全体で無効になっていることを伝えるには、追加で1ビットだけ必要ですが、ほとんどのエンコードアルゴリズムでは、この目的のために少なくとも1バイト（通常はそれ以上）を使用します。例えば、deflateで圧縮されたファイルは、65,535バイトの入力に対して5バイト以上増えることはありません。
実際、長さNのファイルを考え、すべてのファイルが存在する確率が等しいと仮定すると、あるファイルのサイズを縮小する可逆圧縮では、圧縮されたファイルの期待長（長さNのすべての可能なファイルについて平均したもの）は必ずNより大きくなります。したがって、圧縮するデータの特性について何も知らない場合は、そもそも圧縮しない方が良いでしょう。可逆圧縮アルゴリズムは、特定の種類のファイルを他のファイルよりも圧縮する可能性が高い場合にのみ有効です。その場合、アルゴリズムは圧縮したい種類のデータをより効率的に圧縮するように設計できます。
したがって、この議論から得られる主な教訓は、大きな損失を被るリスクがあるということではなく、常に勝てるとは限らないということである。アルゴリズムを選択するということは、暗黙のうちに、すべてのファイルの中から、より短くなるファイルのサブセットを選択することを意味する。これが、ファイルの種類ごとに異なる圧縮アルゴリズムが必要となる理論的な理由である。つまり、あらゆる種類のデータに適したアルゴリズムは存在しないのである。
可逆圧縮アルゴリズムが、設計されたデータタイプに対して一貫してファイルをより短い形式に圧縮できる「秘訣」は、アルゴリズムが処理対象とするファイルにはすべて、アルゴリズムが除去するように設計された、容易にモデル化できる冗長性が含まれているため、アルゴリズムによって短くできるファイルのサブセットに属し、他のファイルは圧縮されないか、あるいは大きくなることさえあるという点にあります。アルゴリズムは一般的に、特定の種類のファイルに合わせて非常に精密に調整されています。たとえば、可逆音声圧縮プログラムはテキストファイルにはうまく機能せず、その逆もまた然りです。
特に、ランダムデータのファイルは、考えられるいかなる可逆データ圧縮アルゴリズムによっても一貫して圧縮することはできません。実際、この結果はコルモゴロフ複雑性におけるランダム性の概念を定義するために使用されています。[ 19 ]
あらゆるデータをロスレスで圧縮できるアルゴリズムを作成することは、証明上不可能です。これまで多くの企業が、任意の数Nのランダムなビットを常にN − 1 ビットに圧縮できる「完全圧縮」を実現したと主張 してきましたが、そのような主張は、その圧縮方式の詳細を検討することなく、安全に却下できます。そのようなアルゴリズムは、数学の基本法則に反します。なぜなら、もし存在すれば、それを繰り返し適用することで、あらゆるファイルをロスレスで長さ 1 に縮小できるからです。[ 18 ]
一方、コルモゴロフ複雑性の意味でファイルが非圧縮であるかどうかを判断するアルゴリズムは存在しないことも証明されています。[ 20 ]したがって、ランダムに見えるファイルであっても、解凍ツールのサイズを含めて大幅に圧縮できる可能性があります。例として、数学定数πの桁が挙げられます。これはランダムに見えますが、非常に小さなプログラムで生成できます。ただし、特定のファイルが非圧縮であるかどうかを判断することはできませんが、非圧縮文字列に関する単純な定理により、任意の長さのファイルの99%以上は、1バイト以上（解凍ツールのサイズを含む）圧縮できないことが示されています。
抽象的に言えば、圧縮アルゴリズムはシーケンス（通常はオクテット）の関数と見なすことができます。圧縮は、結果として得られるシーケンスが元のシーケンス（および解凍マップの指示）よりも短い場合に成功します。圧縮アルゴリズムが可逆であるためには、圧縮マップは「プレーン」ビットシーケンスから「圧縮」ビットシーケンスへの単射を形成する必要があります。鳩の巣原理は、長さNのシーケンスの集合と、長さN -1のシーケンスの集合の任意の部分集合との間の全単射を禁止します。したがって、考えられるすべての入力シーケンスのサイズを縮小する可逆アルゴリズムを作成することは不可能です。[ 21 ]
実際の圧縮アルゴリズムの設計者は、情報エントロピーの高いストリームは圧縮できないことを認めており、それに応じて、この状態を検出して処理する機能を含めています。検出の明白な方法は、生の圧縮アルゴリズムを適用し、その出力が入力よりも小さいかどうかをテストすることです。検出はヒューリスティックによって行われる場合もあります。たとえば、圧縮アプリケーションは、ファイル名が「.zip」、「.arj」、または「.lha」で終わるファイルを、より高度な検出を行わずに圧縮できないとみなす場合があります。この状況を処理する一般的な方法は、入力、または入力の圧縮できない部分を出力で引用し、圧縮オーバーヘッドを最小限に抑えることです。たとえば、zipデータ形式は、アーカイブにそのままコピーされた入力ファイルに対して、「圧縮方法」を「保存」に指定しています。[ 22 ]
2.6 関数部分再帰ではない。
