ロスレス圧縮

可逆圧縮は、圧縮されたデータから情報を失うことなく元のデータを完全に再構築できるデータ圧縮の一種です。可逆圧縮が可能なのは、ほとんどの実世界のデータが統計的な冗長性を示すためです。^[1] 対照的に、非可逆圧縮では、通常、圧縮率が大幅に向上しますが（したがってメディアサイズが縮小されます） 、元のデータの近似値のみを再構築できます。

鳩の巣原理の作用により、ロスレス圧縮アルゴリズムではすべてのデータのサイズを縮小することはできません。一部のデータは少なくとも 1 シンボルまたは 1 ビット長くなります。

圧縮アルゴリズムは通常、人間と機械が判読可能な文書には効果的ですが、冗長性のないランダムデータのサイズを縮小することはできません。特定の種類の入力データを念頭に置いて設計されたアルゴリズムや、圧縮されていないデータに含まれる可能性のある冗長性の種類に関する特定の仮定に基づいて設計されたアルゴリズムが存在します。

ロスレスデータ圧縮は多くのアプリケーションで使用されています。たとえば、ZIPファイル形式やGNUツールgzipで使用されています。また、ロスレスデータ圧縮技術のコンポーネントとしてもよく使用されます（例： MP3エンコーダやその他のロスレスオーディオエンコーダによるロスレスミッド/サイドジョイントステレオ前処理）。 ^[2]

ロスレス圧縮は、元のデータと解凍後のデータが同一で​​あることが重要な場合、または元のデータからの偏差が好ましくない場合に使用されます。一般的な例としては、実行可能プログラム、テキスト ドキュメント、ソース コードなどがあります。PNG や GIF などの一部の画像ファイル形式はロスレス圧縮のみを使用しますが、TIFFやMNGなどの他のファイル形式はロスレスまたはロッシー方式のいずれかを使用します。ロスレス オーディオ形式は、アーカイブまたは制作目的でよく使用されますが、より小さなロッシー オーディオファイルは通常、ポータブル プレーヤーや、ストレージ スペースが限られている場合、またはオーディオの正確な複製が不要な場合に使用されます。

ほとんどのロスレス圧縮プログラムは、2 つの処理を順番に実行します。最初のステップでは、入力データの統計モデルを生成し、2 番目のステップでは、このモデルを使用して、入力データをビット シーケンスにマッピングします。このマッピングによって、「確率の高い」(つまり、頻繁に発生する) データは、「確率の低い」データよりも短い出力を生成します。

ビット シーケンスを生成するために使用される主なエンコード アルゴリズムは、ハフマン コーディング( deflate アルゴリズムでも使用される) と算術コーディングです。算術コーディングは、情報エントロピーによって与えられる特定の統計モデルで可能な最高値に近い圧縮率を実現します。一方、ハフマン圧縮はより単純で高速ですが、1 に近いシンボル確率を扱うモデルでは結果が悪くなります。

統計モデルを構築するには、主に 2 つの方法があります。静的モデルでは、データが分析され、モデルが構築され、このモデルが圧縮データとともに保存されます。このアプローチはシンプルでモジュール化されていますが、モデル自体の保存コストが高くなる可能性があるという欠点があります。また、圧縮されるすべてのデータに対して 1 つのモデルを使用する必要があるため、異種データを含むファイルではパフォーマンスが低下します。適応型モデルでは、データが圧縮されるにつれてモデルが動的に更新されます。エンコーダーとデコーダーはどちらも単純なモデルから開始するため、初期データの圧縮率は低くなりますが、データについて学習するにつれてパフォーマンスが向上します。現在、実際に使用されている最も一般的な圧縮タイプでは、適応型コーダーが使用されています。

ロスレス圧縮方式は、圧縮するデータのタイプに応じて分類できます。原則として、汎用ロスレス圧縮アルゴリズム (汎用とは、任意のビット文字列を受け入れることができるという意味) は、あらゆるタイプのデータに使用できますが、その多くは、圧縮するように設計された形式ではないデータに対しては、大幅な圧縮を実現できません。テキストに使用されるロスレス圧縮技術の多くは、インデックス付き画像に対しても十分に機能します。

これらの技術は、類似した色調の連続した 2D 領域という一般的な現象など、画像特有の特性を活用します。最初のピクセル以外のすべてのピクセルは、その左隣のピクセルとの差に置き換えられます。これにより、小さな値の確率が大きな値よりはるかに高くなります。これはサウンド ファイルにも適用されることが多く、主に低周波数と低音量のファイルを圧縮できます。画像の場合、この手順は、最上位のピクセルとの差を取得することで繰り返すことができ、ビデオの場合は、次のフレームのピクセルとの差を取得できます。

この技術の階層バージョンでは、隣接するデータ ポイントのペアを取得し、その差と合計を保存し、解像度の低い上位レベルで合計を続けます。これは離散ウェーブレット変換と呼ばれます。JPEG2000では、他のペアのデータ ポイントと乗算係数を使用して、それらを差に混ぜます。これらの係数は整数である必要があるため、結果はどのような状況でも整数になります。そのため、値が増加し、ファイル サイズが増加しますが、値の分布はより尖ったものになる可能性があります。^{[引用が必要]}

適応符号化では、音声符号化では前のサンプルからの確率、画像符号化では左上と上のピクセルからの確率、さらにビデオ符号化では前のフレームからの確率を使用します。ウェーブレット変換では、確率も階層を通過します。^[3]

これらの方法の多くは、オープンソースおよびプロプライエタリツール、特に LZW とその派生で実装されています。一部のアルゴリズムは米国およびその他の国で特許を取得しており、その合法的な使用には特許所有者によるライセンスが必要です。特定の種類のLZW圧縮に関する特許、特に多くの開発者が不正とみなした特許所有者 Unisys によるライセンス慣行のため、一部のオープンソース支持者は静止画像ファイルの圧縮にグラフィックス インターチェンジ フォーマット(GIF) の使用を避け、代わりにLZ77ベースのデフレート アルゴリズムとドメイン固有の予測フィルターの選択を組み合わせたポータブル ネットワーク グラフィックス(PNG) を使用するよう推奨しました。ただし、LZW の特許は 2003 年 6 月 20 日に失効しました。^[4]

テキストに使用されるロスレス圧縮技術の多くは、インデックス付き画像でも十分に機能しますが、一般的なテキストには機能しないが、一部の画像 (特に単純なビットマップ) には役立つ技術や、画像の特定の特性 (類似した色調の連続した 2D 領域という一般的な現象や、カラー画像では通常、色空間で表現できる色のうち限られた範囲の色が優勢であるという事実など) を利用する技術もあります。

前述のように、ロスレス サウンド圧縮はやや特殊な領域です。ロスレス サウンド圧縮アルゴリズムは、データの波のような性質によって示される繰り返しパターンを利用できます。つまり、基本的には自己回帰モデルを使用して「次の」値を予測し、予測値と実際のデータとの (おそらく小さな) 差をエンコードします。予測データと実際のデータとの差 (エラーと呼ばれる)が小さい傾向がある場合、特定の差の値 (サンプル値の 0、+1、-1 など) が非常に頻繁に発生するため、これを少数の出力ビットでエンコードすることで利用できます。

ファイルの 2 つのバージョン (または、ビデオ圧縮では、シーケンス内の連続する画像) の差異のみを圧縮すると効果的な場合があります。これはデルタ エンコーディング(数学で差異を表すギリシャ文字Δに由来) と呼ばれますが、この用語は通常、両方のバージョンが圧縮と解凍以外で意味がある場合にのみ使用されます。たとえば、上記のロスレス オーディオ圧縮方式でエラーを圧縮するプロセスは、近似音波から元の音波へのデルタ エンコーディングとして説明できますが、音波の近似バージョンは他のコンテキストでは意味がありません。

ロスレス圧縮アルゴリズムでは、すべてのデータを効率的に圧縮することはできません(詳細については、§ 制限事項を参照してください)。このため、特定の種類の入力データを念頭に置いて設計されたり、圧縮されていないデータにどのような冗長性が含まれる可能性があるかという特定の仮定に基づいて設計されたさまざまなアルゴリズムが存在します。

最も一般的なロスレス圧縮アルゴリズムのいくつかを以下に示します。

• ANS – LZFSEおよびZstandardで使用されるエントロピー エンコーディング
• 算術符号化– エントロピー符号化
• Burrows–Wheeler 変換は、テキストデータをより圧縮しやすくするための可逆変換で、bzip2で使用されます。
• ハフマン符号化- エントロピー符号化、他のアルゴリズムとよく組み合わせられる
• Lempel-Ziv 圧縮(LZ77 および LZ78) – 他の多くのアルゴリズムの基礎となる辞書ベースのアルゴリズム
  • Deflate – LZ77 圧縮とハフマン符号化を組み合わせたもので、ZIP、gzip、PNG画像で使用されます。
  • Lempel–Ziv–Markov 連鎖アルゴリズム(LZMA) – 非常に高い圧縮率。7zipやxzで使用
  • Lempel–Ziv–Storer–Szymanski (LZSS) – WinRARでハフマン符号化と併用される
  • Lempel–Ziv–Welch (LZW) – GIF画像やUnixのcompressユーティリティで使用される
• 部分一致による予測（PPM） –プレーンテキストの圧縮に最適化
• ランレングス符号化（RLE） – 同じ値が連続して続くデータを圧縮するシンプルな方式

• 適応変換音響符号化(ATRAC)
• Apple ロスレス(ALAC – Apple ロスレス オーディオ コーデック)
• オーディオロスレスコーディング（MPEG-4 ALSとも呼ばれる）
• ダイレクトストリーム転送(DST)
• ドルビーTrueHD
• DTS-HDマスターオーディオ
• 無料のロスレスオーディオコーデック（FLAC）
• メリディアンロスレスパッキング(MLP)
• モンキーズオーディオ（モンキーズオーディオAPE）
• MPEG-4 SLS (HD-AAC とも呼ばれる)
• オプティムフロッグ
• オリジナルサウンドクオリティ（OSQ）
• RealPlayer (RealAudio ロスレス)
• ショートン（SHN）
• TTA (トゥルーオーディオロスレス)
• WavPack (WavPack ロスレス)
• WMA ロスレス(Windows Media ロスレス)

• ロスレスのみのエンコード
  • ＢＭＰ
  • PNG – ポータブル ネットワーク グラフィックス
  • GIF – グラフィックス交換フォーマット
• 非可逆および可逆エンコードオプション
  • AVIF – AV1 画像ファイル形式
  • FLIF – 無料のロスレス画像フォーマット
  • HEIF – HEVCを使用した高効率画像ファイル形式
  • ILBM – ( Amiga IFFイメージの RLE 圧縮)
  • JBIG2 – 白黒画像の圧縮
  • JPEG 2000 – （Le Gall–Tabatabai 5/3 ^{[5] [3] [6]}可逆整数ウェーブレット変換経由）
  • JPEG-LS
  • JPEG XL
  • JPEG XR – 旧称WMPhotoおよびHD Photo
  • LDCT –離散コサイン変換^{[7] [8]}
  • PCX – 写真交換
  • QOI – 非常に良い画像フォーマット
  • TGA – トゥルービジョンTGA
  • TIFF – タグ画像ファイル形式
  • ウェブP

• OpenCTM – 3D 三角形メッシュのロスレス圧縮

ロスレスビデオコーデックのリストを見る

暗号システムでは、セキュリティを強化するために、暗号化の前にデータ (「プレーンテキスト」) を圧縮することがよくあります。適切に実装されると、圧縮によって暗号解読を容易にする可能性のあるパターンが削除され、単一性距離が大幅に増加します。^[9]しかし、多くの一般的なロスレス圧縮アルゴリズムは、ヘッダー、ラッパー、テーブル、またはその他の予測可能な出力を生成するため、暗号解読が容易になる可能性があります。したがって、暗号システムでは、出力にこれらの予測可能なパターンが含まれない圧縮アルゴリズムを使用する必要があります。

遺伝学的圧縮アルゴリズム（遺伝的アルゴリズムと混同しないでください）は、従来の圧縮アルゴリズムと遺伝的データに適応した特定のアルゴリズムの両方を使用してデータ（通常はヌクレオチドの配列）を圧縮する最新世代のロスレスアルゴリズムです。2012年に、ジョンズホプキンス大学の科学者チームが、圧縮に外部の遺伝的データベースに依存しない最初の遺伝的圧縮アルゴリズムを発表しました。HAPZIPPERはHapMapデータに合わせて調整されており、20倍以上の圧縮（ファイルサイズの95％削減）を実現し、主要な汎用圧縮ユーティリティよりもはるかに高速で2～4倍の圧縮を実現します。^[10]

ゲノム配列圧縮アルゴリズムは、DNA配列コンプレッサーとも呼ばれ、DNA配列が逆反復などの特徴的な特性を持っているという事実を利用します。最も成功したコンプレッサーはXMとGeCoです。^{[11] 真}核生物の場合、XMは圧縮率がわずかに優れていますが、100MBを超える配列の場合、その計算要件は非現実的です。

自己解凍型実行ファイルには、圧縮されたアプリケーションと解凍プログラムが含まれています。実行されると、解凍プログラムは透過的に元のアプリケーションを解凍して実行します。これは、1キロバイトという厳しいサイズ制限のあるデモのコンテストが開催されるデモコーディングで特によく使用されます。このタイプの圧縮は、バイナリ実行ファイルに限定されるわけではなく、 JavaScriptなどのスクリプトにも適用できます。

ロスレス圧縮アルゴリズムとその実装は、直接比較ベンチマークで定期的にテストされています。よく知られている圧縮ベンチマークは数多くあります。一部のベンチマークはデータ圧縮率のみをカバーしているため、これらのベンチマークの勝者は、トップのパフォーマーの速度が遅いため、日常的な使用には適さない可能性があります。一部のベンチマークのもう 1 つの欠点は、データ ファイルが既知であるため、一部のプログラム作成者が特定のデータ セットで最高のパフォーマンスを発揮するようにプログラムを最適化する可能性があることです。これらのベンチマークの勝者は、多くの場合、コンテキスト混合圧縮ソフトウェアのクラスから生まれます。

マット・マホニーは、2010年2月発行の無料小冊子「データ圧縮の説明」の中で、さらに次のことを列挙している。^[12]

• 1987 年に遡る Calgary Corpus は、サイズが小さいため、現在では広く使用されていません。Matt Mahoney は、1996 年 5 月 21 日から 2016 年 5 月 21 日まで Leonid A. Broukhis によって作成および管理されていた Calgary Compression Challenge を管理していました。
• 大規模テキスト圧縮ベンチマーク^[13]と類似のHutter Prizeはどちらも、トリミングされたWikipedia XML UTF-8データセットを使用しています。
• マット・マホニーが管理する汎用圧縮ベンチマーク^{[14]は、ランダム}チューリングマシンによって生成されたデータの圧縮をテストします。
• Sami Runsas (NanoZip の作者) は、圧縮評価を維持しています。これは、最大圧縮複数ファイル テストに似ていますが、速度要件が最小限であるベンチマークです。これは、ユーザーが速度と圧縮率の重要性を重み付けできる計算機を提供しました。トップ プログラムは、速度要件によってかなり異なります。2010 年 1 月、トップ プログラムは NanoZip で、FreeArc、CCM、flashzip、7-Zipがそれに続きました。
• Nania Francesco Antonio による Monster of Compression ベンチマークでは、40 分の制限時間で 1Gb の公開データの圧縮をテストしました。2009 年 12 月、アーカイバのトップは NanoZip 0.07a で、単一ファイル コンプレッサーのトップは ccmx 1.30c でした。

圧縮定格のウェブサイトでは、圧縮比と時間の「限界」をまとめたチャートが公開されました。^[15]

圧縮分析ツール^[16]は、エンドユーザーが独自のデータを使用してLZF4、Deflate、ZLIB、GZIP、BZIP2、LZMAのストリーミング実装のパフォーマンス特性をベンチマークできるWindowsアプリケーションです。このツールは測定値とグラフを生成し、ユーザーはさまざまな圧縮方法の圧縮速度、解凍速度、圧縮率を比較し、圧縮レベル、バッファサイズ、フラッシュ操作が結果にどのように影響するかを調べることができます。

ロスレスデータ圧縮アルゴリズムは、すべての入力データセットの圧縮を保証するものではありません。言い換えれば、ロスレスデータ圧縮アルゴリズムでは、アルゴリズムで処理しても小さくならない入力データセットが存在し、ロスレスデータ圧縮アルゴリズムでは、少なくとも1つのファイルが小さくなると、少なくとも1つのファイルが大きくなります。これは、次のように鳩の巣原理と呼ばれる計算論法を使用して、初等数学で簡単に証明できます。 ^{[17] [18]}

• 各ファイルは任意の長さのビットの文字列として表されると仮定します。
• すべてのファイルを元のファイルより長くない出力ファイルに変換する圧縮アルゴリズムがあり、少なくとも 1 つのファイルが元のファイルより短い出力ファイルに圧縮されるとします。
• M を、長さがMビットのファイルF を圧縮すると短くなる最小の数とします。NをFの圧縮バージョンの長さ (ビット単位) とします。
• N < Mなので、長さNのすべてのファイルは圧縮後もサイズが維持されます。このようなファイルは 2 ^N個考えられます。 Fと合わせると、長さNの2 ^Nファイルのいずれかに圧縮される2 ^N +1 個のファイルが作成されます。
• しかし、2 ^Nは 2 ^N +1 より小さいため、鳩の巣原理によ​​り、2 つの異なる入力に対する圧縮関数の出力である長さNのファイルが存在するはずです。そのファイルは確実に解凍できません (2 つの元のファイルのどちらが得られるのでしょうか?)。これは、アルゴリズムがロスレスであるという仮定と矛盾します。
• したがって、当初の仮説 (圧縮機能によってファイルが長くなることはない) は必ずしも真実ではないという結論に至らなければなりません。

実用的な圧縮アルゴリズムのほとんどは、エンコードによって長くなるファイルの通常のコーディングをオフにできる「エスケープ」機能を備えています。理論上は、デコーダーに入力全体に対して通常のコーディングがオフになっていることを通知するには、1 つの追加ビットのみが必要です。ただし、ほとんどのエンコード アルゴリズムでは、この目的のために少なくとも 1 バイト (通常は 1 バイト以上) を使用します。たとえば、deflate圧縮されたファイルは、65,535 バイトの入力に対して 5 バイト以上大きくなることはありません。

実際、長さ N のファイルについて考えた場合、すべてのファイルが等しく発生する可能性があるとすれば、あるファイルのサイズを縮小するロスレス圧縮では、圧縮されたファイルの予想長さ (長さ N のすべての可能性のあるファイルの平均) は必然的にN より大きくなければなりません。 ^[19]したがって、圧縮するデータの特性について何も知らない場合は、まったく圧縮しないのと同じです。ロスレス圧縮アルゴリズムは、特定の種類のファイルを他のファイルよりも圧縮する可能性が高い場合にのみ役立ちます。その場合、アルゴリズムはそれらの種類のデータをより適切に圧縮するように設計できます。

したがって、この議論から得られる主な教訓は、大きな損失のリスクがあるということではなく、単に常に勝てるわけではないということだけです。アルゴリズムを選択するということは、暗黙的に、すべてのファイルのうち、有効に短くなるサブセットを選択することを意味します。これが、異なる種類のファイルに対して異なる圧縮アルゴリズムが必要である理論的な理由です。すべての種類のデータに適したアルゴリズムは存在しないのです。

ロスレス圧縮アルゴリズムが、そのアルゴリズムが設計されたデータの種類で使用され、そのようなファイルを一貫してより短い形式に圧縮できるようにする「トリック」は、アルゴリズムが作用するように設計されたファイルはすべて、アルゴリズムが削除するように設計された、簡単にモデル化できる何らかの冗長性を持っているため、そのアルゴリズムで短くできるファイルのサブセットに属し、他のファイルは圧縮されないか、大きくなることさえあることです。アルゴリズムは、通常、特定の種類のファイルに合わせて非常に具体的に調整されています。たとえば、ロスレス オーディオ圧縮プログラムはテキスト ファイルではうまく機能せず、その逆も同様です。

特に、ランダムデータのファイルは、考えられるいかなるロスレスデータ圧縮アルゴリズムでも一貫して圧縮することはできません。実際、この結果はコルモゴロフ複雑性におけるランダム性の概念を定義するために使用されます。^[20]

あらゆるデータをロスレスで圧縮できるアルゴリズムを作ることは不可能である。長年にわたり、ランダムなビット数Nを常にN − 1 ビットに圧縮できる「完全な圧縮」を実現したと主張する企業が数多くあったが 、こうした主張は、主張されている圧縮方式に関する詳細を調べることさえなく、安全に却下できる。このようなアルゴリズムは数学の基本法則に反する。なぜなら、もし存在すれば、それを繰り返し適用して、あらゆるファイルをロスレスで長さ 1 に縮小できるからである。^[18]

一方、コルモゴロフ複雑性の意味でファイルが非圧縮かどうかを判断するアルゴリズムは存在しないことも証明されています^{[21] 。したがって、ランダムに見えても、特定のファイルは、解凍器のサイズを含めても大幅に圧縮される可能性があります。一例として、数学定数}piの数字が挙げられます。これはランダムに見えますが、非常に小さなプログラムで生成できます。ただし、特定のファイルが非圧縮かどうかを判断できない場合でも、非圧縮文字列に関する簡単な定理から、任意の長さのファイルの 99% 以上は、1 バイト以上圧縮できないことがわかります (解凍器のサイズを含む)。

抽象的には、圧縮アルゴリズムはシーケンス（通常はオクテット）の関数として考えることができます。圧縮が成功するのは、結果のシーケンスが元のシーケンス（および解凍マップの指示）よりも短い場合です。圧縮アルゴリズムがロスレスであるためには、圧縮マップが「プレーン」ビットシーケンスから「圧縮」ビットシーケンスへの注入を形成する必要があります。ピジョンホール原理により、長さNのシーケンスのコレクションと長さN −1のシーケンスのコレクションの任意のサブセットとの間の一対一変換が禁止されます。したがって、あらゆる入力シーケンスのサイズを縮小するロスレスアルゴリズムを作成することはできません。^[22]

実際の圧縮アルゴリズムの設計者は、情報エントロピーの高いストリームは圧縮できないことを認めており、この状態を検出して処理する機能を組み込んでいます。検出の明らかな方法は、生の圧縮アルゴリズムを適用し、その出力が入力よりも小さいかどうかをテストすることです。検出はヒューリスティックによって行われることもあります。たとえば、圧縮アプリケーションは、名前が「.zip」、「.arj」、または「.lha」で終わるファイルを、より高度な検出を行わなくても圧縮できないと見なす場合があります。この状況を処理する一般的な方法は、入力を引用するか、入力の圧縮できない部分を出力に引用して、圧縮のオーバーヘッドを最小限に抑えることです。たとえば、zipデータ形式では、入力ファイルがそのままアーカイブにコピーされた場合、「圧縮方法」として「保存」を指定します。^[23]

マーク・ネルソンは、comp.compression に登場した「魔法の」圧縮アルゴリズムの主張に応えて、高度にエントロピー化された内容の 415,241 バイトのバイナリ ファイルを作成し、その入力と合わせて、彼が提供したバイナリ データよりも小さく、エラーなしで再構成できるプログラムを作成する人に 100 ドルの公開チャレンジを発行しました。^[24] マイク・ゴールドマンは、5,000 ドルの報酬で同様のチャレンジを発行しました。^[25]

• Sayood, Khalid (2017 年 10 月 27 日)。データ圧縮入門。Morgan Kaufmann シリーズ マルチメディア情報およびシステム (第 5 版) 。Morgan Kaufmann。ISBN 978-0-12809474-7。（790ページ）
• Sayood, Khalid 編 (2002 年 12 月 18 日)。ロスレス圧縮ハンドブック (通信、ネットワーク、マルチメディア) (第 1 版) 。Academic Press。ISBN 978-0-12390754-7。（488ページ）

• 「LZF 圧縮形式」。github。2017年10 月 17 日閲覧。
• Phamdo, Nam. 「データ圧縮の理論」。データ圧縮。2016年5月8日時点のオリジナルよりアーカイブ。2017年10月17日閲覧。
• 「ロスレス比較」。Hydrogenaudio Knowledgebase。2015年1月5日。 2017年10月17日閲覧。
• 「音楽用のロスレスおよびロッシーオーディオフォーマット」。Bobulous Central。2003年11月6日。 2017年10月17日閲覧。
• 「画像圧縮ベンチマーク」。2013 年 2 月 10 日時点のオリジナルよりアーカイブ。概要
  • 米国特許 #7,096,360、2017 年 2 月 2 日、Wayback Machineにアーカイブ、「各周波数が多数のビットを表す周波数を通じて、多数のバイナリ桁の圧縮、暗号化、解凍、復号化、および永続化をサポートする「周波数時間ベースのデータ圧縮方法」」