圧縮アルゴリズム入門: 可逆・非可逆の基礎から主要手法・実務運用まで徹底解説

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

圧縮アルゴリズムとは — 概要と目的

圧縮アルゴリズムは、データの冗長性を取り除き、格納や伝送に必要な容量や帯域を削減するための手法群です。ITの現場ではファイル保存、ネットワーク転送、データベース、バックアップ、ストリーミングなど幅広い用途で用いられます。圧縮には「可逆（ロスレス）」と「非可逆（ロッシー）」の二種類があり、利用目的に応じて使い分けられます。

基本概念と理論的背景

圧縮の理論的基盤は情報理論にあり、クロード・シャノンの「情報理論（1948年）」で定式化されたエントロピーが重要な概念です。エントロピーはある情報源が持つ平均的不確実性を表し、その理想的な最小平均ビット数（限界）を示します（シャノンの源符号化定理）。また、圧縮可能性の別の観点としてコルモゴロフ複雑性（任意のデータ列を生成する最短プログラム長）がありますが、これは計算上評価困難です。

実用上は理論限界に近づけつつ、速度・メモリ・ランダムアクセス性・エラー耐性・実装の容易さなどのトレードオフを考慮してアルゴリズムが選ばれます。

可逆圧縮と非可逆圧縮（Lossless vs Lossy）

  • 可逆圧縮（Lossless）：元データを完全に復元できる。テキスト、ソースコード、可逆バックアップ、法的文書などに必須。代表例：ZIP（DEFLATE）、gzip、PNG、LZMA、Zstandard。
  • 非可逆圧縮（Lossy）：人間の知覚に基づく冗長情報（視覚・聴覚の許容誤差）を捨てることで高い圧縮率を実現。画像（JPEG）、音声（MP3、AAC）、映像（H.264、HEVC、AV1）などで用いられる。

主要な圧縮手法とその仕組み

以下は代表的な手法とその概念的な説明です。

  • ランレングス符号化（RLE）：連続する同一シンボルを「シンボル+繰り返し回数」で表す単純手法。単純だが特定のパターン（例：単色領域）に有効。
  • ハフマン符号化：出現頻度に応じて可変長ビット列を割り当てるエントロピー符号化。符号語は整列木（バイナリツリー）で表現され、最短平均長を達成することが数学的に示されている（ただし確率分布の精度に依存）。
  • 算術符号化 / レンジ符号化：シンボル列全体を1つの実数（区間）として表現する高度なエントロピー符号化。理論的にハフマンより効率が良い（特に確率のばらつきが大きい場合）。実装は複雑だが近年はレンジ符号化が高速実装として普及。
  • LZファミリー（LZ77, LZ78, LZWなど）：過去の出現パターンを辞書（スライディングウィンドウや静的/動的辞書）として参照し、繰り返しを参照コピーに置換する。DEFLATE（gzip/ZIP）はLZ77とハフマンを組み合わせた代表例。
  • バローズ・ウィーラー変換（BWT）：文字列をソートベースで変換して局所的な同一文字の塊を作り出し、それに対してムーブ・トゥ・フロントやRLE、ハフマン等を適用する（bzip2が採用）。
  • 変換符号化（Transform coding）：非可逆圧縮の中核。画像なら離散コサイン変換（DCT）や離散ウェーブレット変換（DWT）を用いて空間的相関を周波数領域に移し、高周波成分を量子化して捨てる（JPEGはDCT、JPEG2000はDWT）。音声/音楽ではMDCT等が使われ、知覚モデル（心理音響）で不要成分を除去する。
  • 予測と残差の符号化（Predictive coding）：隣接ピクセルや過去のサンプルから予測値を作り、その誤差（残差）を符号化する手法。PNGのフィルタリングや一部音声コーデックでも採用される。
  • 統計的モデル（Context modeling / PPMなど）：文脈を考慮した確率推定を行い、高精度なエントロピー符号化（算術符号化等）と組み合わせることで高圧縮を実現する。ただし計算量が大きい。

代表的なフォーマットと実装例

  • ZIP / gzip（DEFLATE: LZ77 + ハフマン） — 汎用的で互換性高。
  • bzip2（BWT + MTF + ハフマン） — 圧縮率は良いが遅め。
  • LZMA / 7z — 高圧縮だがメモリや時間コストが高い。
  • Zstandard（zstd） — Facebook（Meta）開発。高速かつ良好な圧縮率で近年普及。
  • Brotli — ウェブ配信用に設計（HTTP圧縮）。テキスト系に強い。RFC 7932で仕様化。
  • PNG（可逆画像: フィルタ + DEFLATE）／JPEG（非可逆画像: DCT + 量子化）
  • MP3, AAC（音声: MDCT + 心理音響）
  • H.264/HEVC/AV1（映像: ブロック変換、動き補償、エントロピー符号化）

評価指標とトレードオフ

圧縮アルゴリズムの選定では以下の指標を総合的に評価します。

  • 圧縮率（サイズ削減率）
  • 圧縮速度（エンコード時間）と解凍速度（デコード時間）
  • メモリ利用量（エンコード/デコード時）
  • 遅延（リアルタイム性が必要な場面）
  • ランダムアクセス性（部分的にデコードできるか）
  • 耐障害性（データ損傷時の復旧性）
  • 特許・ライセンス（商用利用時の制約）

一般に「圧縮率と速度はトレードオフ」の関係にあり、同等の圧縮率を得るにはより多くの計算資源やメモリが必要になることが多いです。実運用では目的（バックアップなら最大圧縮、ウェブ配信ならデコード速度と遅延重視）を明確にしてアルゴリズムを選びます。

実運用での注意点・落とし穴

  • 既に圧縮済みデータの圧縮は意味がない：JPEGやMP3などは既に圧縮されており、再圧縮しても効果が薄いどころか容量が増えることもある。
  • 圧縮→暗号化の順序：一般に先に圧縮し、その後暗号化する（compress-then-encrypt）が推奨。暗号化後はデータが擬似乱数化されるため圧縮効果が期待できない。
  • 圧縮に伴う脆弱性：CRIMEやBREACHのような圧縮を悪用したサイドチャネル攻撃が存在するため、機密性の高いWeb通信では注意が必要。
  • 圧縮爆弾（zip bomb）：極度に展開時サイズが大きくなるファイルで、サービス拒否（DoS）を引き起こす恐れがある。アンチウイルスやアップロード処理では展開上限を設けるべき。
  • ランダムアクセスと部分的復元：圧縮方式によってはファイルの真ん中だけ取り出せないものがある。大容量データのストリーミングや分割保存を考慮する場合はランダムアクセス性を確認する。

実践的な選択ガイド（用途別）

  • テキストログやソースコード：gzip/DEFLATE（互換性）、またはzstd（高速かつ良圧縮）
  • 長期アーカイブ・バックアップ：7z（LZMA）や高圧縮モードのzstd
  • ウェブ配信（HTML/CSS/JS）：Brotli（最高圧縮は時間かかるが配信サイズ最小）、あるいはgzip互換
  • 画像（ウェブ）：写真はWebP/AVIF（非可逆で高圧縮）、ロゴ等はPNG（可逆）
  • 音声・映像配信：ストリーミングはH.264/H.265/AV1等、レイテンシーやデバイス互換を考慮

最新動向と将来展望

近年は下記のような動きが見られます。

  • 新世代の映像コーデック（AV1、VVC/H.266など）が普及しつつあり、帯域節約と品質向上が進む。
  • 機械学習を用いた「学習圧縮（Neural Compression）」が研究・実装段階に入り、特に画像・映像分野で従来手法を凌ぐ事例が増えている。ただし計算コストやデプロイの難しさが残る。
  • 汎用の高速・高効率圧縮ライブラリ（例：Zstandard, Brotli）が普及し、リアルワールドでの適用が増加。
  • セキュリティ面では圧縮と暗号化の組合せ、及びサイドチャネル対策が重要性を増している。

まとめ（IT担当者への提言）

圧縮アルゴリズムは単に「圧縮率」だけで判断せず、速度、メモリ、ランダムアクセス、エラー耐性、ライセンス、セキュリティなど複数の要素を勘案して選定することが重要です。運用では「用途に応じた最適化」と「悪用・障害を防ぐ運用ルール（展開制限、圧縮前のファイルタイプ判定、暗号化の順序など）」を整備してください。将来的には学習ベースの手法や新コーデックの成熟が期待されますが、互換性や実行コストを踏まえた段階的導入が現実的です。

参考文献

カテゴリー
IT
前の記事
マイク・ブルームフィールド徹底解説：East-WestとSuper Sessionを軸に長尺インプロとブルース・ロックの革新を辿る名盤ガイドNew!!
2025年11月22日
次の記事
Alvin Lee（アルヴィン・リー）— Ten Years Afterのギタリストとウッドストック伝説：速弾きと歌心で綴るブルース・ロック史New!!
2025年11月22日