ロスレス圧縮の原理を徹底解説 — エントロピーから実装と限界まで

2025年12月12日 最終更新日時 : 2025年12月12日 エバープレイ編集部

はじめに：ロスレス圧縮とは何か

ロスレス圧縮（lossless compression）は、元のデータを完全に復元できる圧縮技術を指します。可逆圧縮とも呼ばれ、テキスト、プログラム、可逆音声（例：FLAC）、PNG画像、アーカイブ（ZIP）など、データの完全性が要求される領域で広く使われます。本稿では、情報理論に基づく原理から代表的アルゴリズム、実装上の工夫、理論的な限界までを詳しく解説します。

情報理論とエントロピー：圧縮の理論的基盤

圧縮の基盤は情報理論にあります。シャノンの情報量（エントロピー）Hは、確率分布p(x)を持つ離散情報源に対して次のように定義されます。

H(X) = -\sum_x p(x) \log_2 p(x)

この値は長い符号列を平均的に表現するのに必要なビット数の下限を与えます。すなわち、任意の可逆符号化法は、平均符号長がエントロピー未満になることはできません（漸近的に近づけることは可能）。また、符号語の長さに関する制約を表すクラフトの不等式（Kraft inequality）により、プレフィックス符号の実現可能性が決まります。

統計的符号化：ハフマン符号と算術符号

  • ハフマン符号：確率の高いシンボルに短いビット列を割り当てる最適プレフィックス符号です。離散分布に対して整数ビット長の最適性を示しますが、符号長が整数であるためエントロピーとの差（切り上げ誤差）を持ちます。計算量は比較的小さく、静的ハフマンは事前に分布が分かっている場合に有効です。
  • 算術符号／レンジ符号：シンボル列全体を区間で表現することで、実効的に非整数ビット長表現が可能になり、理論上エントロピーに極めて近づけます。算術符号は精度管理や特許問題の歴史がありましたが、近年はレンジ符号（range coding）などの実装が広く使われています。適応型算術符号は確率分布が未知の状況でも動的にモデルを更新できます。

辞書法（LZファミリー）：繰り返しの利用

LZ77、LZ78、LZWといった辞書ベースの手法は、データ内の繰り返しパターンを検出して参照に置き換える方式です。

  • LZ77：ウィンドウ内の過去データを検索して最長一致を見つけ、（距離、長さ、次の文字）のタプルで表現します。DEFLATE（gzip、PNGなどで採用）はLZ77風の圧縮とハフマン符号を組み合わせています。
  • LZ78/LZW：逐次的に辞書を拡張してパターンを登録し、以降は辞書インデックスで参照します。GIFや古いUNIX compressで用いられた実績があります。

変換と前処理：BWT、Move-to-Front、差分、RLEなど

単純な符号化で効率が出ない場合、データを圧縮しやすい形に変換する前処理が効果的です。

  • Burrows–Wheeler Transform (BWT)：シンボルの局所的な同類集約を促す可逆変換です。BWTの後にMove-to-Front（MTF）やランレングス符号（RLE）、そして統計的符号化を適用すると高圧縮が得られます。
  • 差分（Delta）符号化：連続値（例：音声や画像のピクセル）で隣接差分を取り、差分列を符号化することでエントロピーを下げます。FLACなど音声コーデックでの線形予測と組み合わせることが多いです。
  • ランレングス符号化（RLE）：同一シンボルの連続を（シンボル、長さ）で表現。簡単だが一般には併用されます（例：FAXやBMPの一部形式）。

代表的な実装と標準

  • DEFLATE（RFC 1951）：LZ77にハフマン符号を組み合わせた方式。gzip、zlib、PNGの圧縮エンジンとして広く採用。
  • PNG：画像前処理（フィルタ）＋DEFLATEを用いることで可逆画像圧縮を実現。
  • GIF：LZWを使用。特許問題があったが既に解消。
  • FLAC：可逆音声。線形予測（LPC）に基づく残差をRice符号などで符号化。
  • JPEG-LS / JPEG 2000（可逆モード）：静止画像の可逆圧縮オプションを持ち、JPEG-LSは軽量で高速、JPEG 2000はウェーブレット変換に基づく高性能な可逆モードを持つ。

理論的限界と実用上の注意点

  • エントロピー限界：平均符号長はエントロピーH未満にできない（大きなブロック長でHに近づけられる）。
  • ランダムデータの非圧縮性：真のランダム列はほとんど圧縮できません。これはシャノン限界の直接的帰結です。
  • コルモゴロフ複雑度：あるデータ列を生成する最短プログラム長（理想的な圧縮可能性の下限）という概念は理論上有用ですが、一般には非計算可能で現実的手段の評価指標には使えません。
  • 実装上のトレードオフ：圧縮率、処理速度、メモリ使用、遅延、ランダムアクセス性はトレードオフ関係にあります。例えば、非常に高い圧縮率を得るための大きな辞書や長いブロックはメモリ消費と遅延を増やします。
  • 誤り耐性と暗号化との関係：圧縮後に暗号化するとランダム性が高まり再圧縮は無効化されます。通信路の誤りは圧縮ストリームで大きな影響を与えるため、エラーチェックや区切り単位の冗長性が必要です。

実務での選択指針

用途に応じた選択基準は以下の通りです。

  • 高速で一般的な圧縮が必要：DEFLATE（gzip/zlib）やLZ4。
  • 最高の圧縮率が必要で時間を許容する：BWT系（bzip2）やLZMA（7z）。
  • 可逆オーディオ：FLAC。
  • 可逆画像：PNG（写真はフィルタ調整で差）、医療用途や品質保証が厳しい場面ではJPEG 2000の可逆モードやJPEG‑LS。

まとめ

ロスレス圧縮は、情報理論のエントロピー概念が基盤となり、統計的符号化、辞書法、変換・前処理といった多様な手法の組み合わせで現実に適用されています。どのアルゴリズムも長所と短所があり、用途・性能要件に応じて選択することが重要です。理論的にはエントロピーが下限を定め、ランダムデータは圧縮不可能である点を念頭に置くことで、期待値の管理と適切な技術選定が可能になります。

参考文献

カテゴリー
IT
前の記事
オムニバスアルバムとは何か――歴史・制作・著作権・デジタル時代の位置づけまで徹底解説
2025年12月12日
次の記事
ヤクザ映画の系譜と魅力：任侠から実録へ、表現と社会性を読み解く
2025年12月12日