無損失圧縮の基礎と主要アルゴリズム：エントロピーから実用フォーマットまで徹底解説
エバープレイ編集部無損失圧縮とは — 概要と定義
無損失圧縮（可逆圧縮、lossless compression）は、元のデータを完全に復元できることを保証するデータ圧縮方式です。圧縮と展開（伸長）を経ても、ビット単位で元のファイルと同一になる点が特徴です。これに対して、画像や音声で用いられる不可逆圧縮（lossy）は一部情報を捨てて圧縮率を高めるため、元のデータを完全には復元できません。
基本原理：エントロピーと情報理論
無損失圧縮の理論的な限界は、情報理論で定義されるエントロピーに基づきます。シャノンの源符号化定理によれば、ある確率分布に従う情報源は、そのエントロピーにほぼ等しいビット数までしか平均的に圧縮できません。すなわち、データに高い冗長性（繰り返しや偏り）があるほど効果的に圧縮できますが、真のランダムデータ（高エントロピー）を圧縮することは原理的に難しいか不可能です。
代表的なアルゴリズムと仕組み
ハフマン符号（Huffman coding） — シンボルの出現確率に応じて可変長のビット列を割り当てる方法です。頻出シンボルには短い符号語を、稀なシンボルには長い符号語を与えることで平均ビット長を下げます。最適な接頭辞符号の一つであり、多くの複合方式で利用されます。
算術符号化（Arithmetic coding） — シーケンス全体を一つの実数区間にマッピングすることで、理論上エントロピーに近い符号長が得られます。ハフマンよりも柔軟で、長期的な確率モデルと組み合わせると高効率を示します。
LZファミリー（LZ77, LZ78, LZW） — 辞書ベースのアルゴリズム群で、過去に出現したシーケンスを参照することで冗長性を取り除きます。GIFやZIP、gzip、PNG（DEFLATE）などの基礎になっています。モデルを事前に学習する必要がない「普遍的」な圧縮法です。
Burrows–Wheeler変換（BWT）と可逆変換群 — 文字列を並べ替えて同種文字を近接させ、後続のランレングス符号化やハフマン符号化で高効率を引き出す手法です。bzip2はBWTを核にしています。
前処理と可逆変換
多くの実装は、単一の符号化技術だけでなく前処理（プリプロセッシング）を組み合わせます。例としてはデルタ符号化（差分を取ることで連続値の変化を小さくする）、行単位・ピクセル単位の予測、ランレングス符号化（RLE）などがあります。これらはデータの冗長性を顕在化させ、後続の圧縮アルゴリズムの効率を高めます。重要なのは、全ての処理が可逆であること、すなわち復号時に元どおりに戻せることです。
代表的なフォーマットとツール
テキスト・汎用：ZIP（DEFLATE）、gzip、bzip2（BWT）、xz（LZMA）、Zstandard、Brotli
画像（可逆）：PNG、WebP（無損失モード）
音声（可逆）：FLAC、ALAC
アーカイブ：tarなどのコンテナに圧縮アルゴリズムを組み合わせて利用（例：tar.gz、tar.xz）
近年はZstandardやBrotliのように、圧縮率と高速性をバランスさせた新しいアルゴリズムが注目されています。用途によっては圧縮速度や展開速度、メモリ使用量が重要な選択基準になります。
無損失圧縮の利点と限界
利点：データの完全な復元が必要な場面（ソースコード、データベース、可逆音声・画像、医療画像、アーカイブ、バックアップ）で必須。検証や法的要件に対応可能。
限界：不可逆圧縮に比べて最大圧縮率は低く、エントロピーが高いデータはほとんど圧縮できない。さらに、圧縮アルゴリズムの複雑性や計算コスト、メモリ要件が実用上の課題になる。
実用上の注意点と落とし穴
既に圧縮されたデータ（JPEG画像やMP3、動画ストリームなど）を無損失圧縮しようとすると、ほとんど効果がないか、逆にヘッダやメタデータでサイズが増えることがあります。
暗号化されたデータや乱数に近いデータは高エントロピーであり、圧縮の余地がほとんどありません。暗号化→圧縮の順は避け、先に圧縮してから暗号化するのが一般的です。
圧縮ファイルはビットの破損に弱い場合があります。小さな破損があると展開に失敗するか、出力が大きく乱れることがあるため、アーカイブにはCRCやSHA等のチェック、バックアップや冗長化が重要です。
ビッグデータやストリーミングでは、圧縮率だけでなく、ランタイムの遅延、ランダムアクセス性能、並列処理適性も評価軸になります。
ケーススタディ：画像と音声の扱い
同じ「可逆」のラベルでも用途で選択肢が異なります。例えば写真をウェブで配信する場合、画質と帯域を重視すれば不可逆のJPEGやAVIFを選ぶことが多いですが、医療画像やアーカイブ用途ではPNGやJPEG-LS、可逆HEVCなど無損失が要求されます。音楽制作やアーカイブではFLACやALACがスタンダードで、作業用ワークフローや長期保存に適しています。
まとめ：設計と選択のポイント
無損失圧縮は「データを完全に失わずに小さくする」ための方法であり、用途に応じてアルゴリズムやフォーマットを選ぶことが重要です。要求される圧縮率、速度、メモリ、ストリーミング性、ランダムアクセス性、耐障害性（チェックサムや冗長性）を総合的に評価して最適な方式を採用してください。また、理論的な限界（エントロピー）を理解することで、圧縮の効果予測や期待値の設定が可能になります。
参考文献
- 無損失圧縮 - Wikipedia（日本語）
- エントロピー (情報理論) - Wikipedia（日本語）
- ハフマン符号 - Wikipedia（日本語）
- LZ77 - Wikipedia（日本語）
- 算術符号化 - Wikipedia（日本語）
- DEFLATE - Wikipedia（日本語）
- PNG - Wikipedia（日本語）
- FLAC - Wikipedia（日本語）
- Zstandard (公式ドキュメント)
- Brotli - Wikipedia（英語）
投稿者プロフィール
