Deflateとは何か：LZ77とハフマン符号化の仕組みと歴史・実装ガイド

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

Deflate とは — 概要

Deflate（デフレート）は、データ圧縮アルゴリズムの一つで、LZ77 に基づく系列圧縮とハフマン符号化を組み合わせた「LZ77 + ハフマン」の方式を採用します。RFC 1951 で規定され、主に zlib/gzip/ZIP/PNG など多数のフォーマットやプロトコルで広く使われてきました。ストリーム指向で処理でき、実装が比較的単純かつ汎用性が高いことから、長年にわたり標準的な汎用圧縮法として利用されています。

歴史と位置づけ

Deflate は 1990 年代に標準化され、RFC 1951（1996年）として公開されました。zlib（RFC 1950）や gzip（RFC 1952）は Deflate を実際に用いるフォーマット／ラッパー規格で、zlib は内部で Adler-32 チェックサムを使い、gzip は CRC32 などをヘッダ／トレイラに持ちます。ウェブやアーカイブ、画像（PNG）といった多くの分野でデファクトスタンダードとなった反面、近年は Brotli や Zstandard のような新世代アルゴリズムに置き換えられつつあります。

アルゴリズムの基本構造

  • LZ77 系列置換：過去のデータの繰り返しを「距離（distance）＋長さ（length）」の参照に置き換える。Deflate は最大 32KB（32768 バイト）のスライディングウィンドウを用いる。
  • ハフマン符号化：LZ77 で得られたリテラル（単一バイト）や長さ・距離のシンボルに可変長符号（ハフマン）を割り当てることでさらなる圧縮を行う。

この組合せにより、出現頻度の高いバイト列は短いビット列に、長く繰り返されるパターンは参照で置き換えられるため効率よく圧縮できます。

ブロック構造とブロックタイプ

Deflate データは複数のブロックに分割され、各ブロックは以下のいずれかのタイプでエンコードされます（各ブロックは最後のブロックか否かを示すビットで始まる）：

  • 非圧縮（Stored）：バイト境界に整列した未圧縮データブロック。長さ（LEN）とその補数（NLEN）を持つ。実装が簡単で、圧縮できないデータのために使われる。
  • 固定ハフマン（Fixed Huffman）：規定済みの（固定の）ハフマンコードを使用。エンコード／デコードが高速だが、データ特性に最適化されない。
  • 動的ハフマン（Dynamic Huffman）：ブロックごとにハフマン木（符号長テーブル）を定義して送出。データに最適化されるため圧縮率が高くなるが、ハフマン表自体のオーバーヘッドがある。

符号体系の詳細（リテラル/長さ/距離）

重要な定数やマッピング（RFC 1951 による）：

  • リテラル/長さシンボルは 0 から 285（合計 286 コード）で定義され、0–255 がバイトのリテラル、256 がブロック終端を表す。257 以降が長さコードを表現する（長さは最小 3、最大 258）。
  • 距離シンボルは 0 から 29（30 コード）で、距離は 1 から 32768（32 KB）の範囲を表現する。距離コードには追加ビットが必要なものがある。
  • 固定ハフマンの割当ては RFC 1951 に明記され、リテラル/長さコードのビット長は範囲ごとに固定されている（例：0–143 は8ビット、144–255 は9ビット、256–279 は7ビット、280–287 は8ビットなど）。

動的ハフマンでは、ハフマン木を効率的にエンコードするメタ符号（コード長のランレングス圧縮）も定義されています。

実装とフォーマットの関係

  • zlib（RFC 1950）：Deflate ストリームの軽量ラッパーで、ヘッダに圧縮メソッド／ウィンドウサイズ情報を持ち、最後に Adler-32 チェックサムを付加する。多くのライブラリがこの形式を扱う（例：zlib ライブラリ）。
  • gzip（RFC 1952）：ファイル圧縮用のフォーマット。Deflate を圧縮本体として使い、独自のヘッダ（ファイル名、タイムスタンプ等）と CRC32 チェックサムを付ける。
  • ZIP：アーカイブ形式として Deflate（圧縮方式コード 8）を採用していることが多い。ZIP のメタデータ構造により複数ファイルを格納する。
  • PNG：画像の IDAT チャンク内で zlib/Deflate のストリームを使う。PNG 自身は Deflate をそのままではなく zlib ラッパーとして利用する仕様になっている。
  • HTTP の Content-Encoding：歴史的に「deflate」の解釈が曖昧で、zlib 包装されたものと生の Deflate ストリームのいずれかを指す実装があり互換性問題が生じたため、実運用では gzip（Content-Encoding: gzip）や新しい br（Brotli）が推奨されることが多い（MDN 等参照）。

性能とトレードオフ

  • 圧縮率と速度：Deflate はアルゴリズム的にはバランス型で、圧縮率・圧縮速度・復号速度が比較的良好。高速重視／低メモリの実装も多い。
  • メモリ：スライディングウィンドウ（最大 32KB）やハッシュテーブルなどを使ってマッチ探索を行うため、実装によっては圧縮時に追加の作業領域が必要。
  • ストリーミング：Deflate はストリーム処理に適しており、データを逐次的に圧縮・解凍できる。
  • 互換性：長年の標準のため広範な互換性を持つ一方、より高圧縮率を求める用途では Zstandard、Brotli、LZMA（7zip）などに劣るケースがある。

最適化・派生実装

  • zlib（Jean-loup Gailly / Mark Adler）：汎用的で広く使われる実装。
  • zopfli（Google）：より高い圧縮率を得るために Deflate の探索を徹底的に行う（非常に遅いが出力は互換）。圧縮率は向上するが圧縮時間は大幅に増える。
  • libdeflate：高速で効率的な Deflate / Inflate 実装を目指したライブラリ。大量の実運用で性能評価が良好。
  • また、Brotli や Zstandard はウェブやアーカイブでの置換候補として注目されており、圧縮率・速度の面で Deflate を上回る場合がある。

セキュリティと運用上の注意

  • リソース枯渇：大きな圧縮データを解凍することでメモリや CPU が急増する「圧縮爆弾（zip bomb）」に注意。受信側でサイズや処理時間の上限を設けることが重要。
  • 入力検証：ファイルアーカイブ処理時はパス名を検証し、ディレクトリ・トラバーサルや上書き攻撃を防ぐ（ZIP 特有の「zip slip」問題など）。
  • HTTP の deflate：先述の通り過去には「deflate」エンコーディングの解釈差異による互換性問題があり、サーバー／クライアントの実装差に注意する必要がある。

まとめ

Deflate は LZ77 とハフマン符号を組み合わせた実用的で広く普及した圧縮方式です。歴史的経緯と互換性の高さから現代の多くのフォーマットで利用され続けていますが、用途や要件に応じて Brotli や Zstandard のような新しいアルゴリズムが採用されるケースも増えています。運用時は圧縮／解凍のコスト、互換性、セキュリティ（圧縮爆弾等）に注意して選択・実装することが重要です。

参考文献

カテゴリー
IT
前の記事
フラワー・トラベル・バンド徹底解説：日本のロック史を変えたサイケ・ヘヴィの先駆者とSatoriの魅力New!!
2025年11月22日
次の記事
筋肉少女帯のアナログ盤完全ガイド：入門盤から名盤・リイシューまでの選び方と聴き方New!!
2025年11月22日