Deflate

概要

Deflateとは、辞書圧縮とハフマン符号という異なる圧縮方式を組み合わせたデータ圧縮アルゴリズム。任意の形式のデータを欠損無く圧縮できる可逆圧縮を行うアルゴリズムの一つで、様々なデータ形式やソフトウェアに採用され広く普及している。

辞書圧縮としてLZ77（実際には改良版のLZSS）方式を参照している。これはデータを先頭から読み込んでいき、すでに読み込み済みの一定の範囲の中に同じ符号列が見つかったら、一致した箇所の（位置,長さ）という二つの値の組で符号列を置き換える（見つからなければ符号列をそのまま記す）というものである。

辞書圧縮したデータは、（値に置き換えられなかった）符号列そのもの、一致箇所の位置、一致箇所の長さという3種類のデータが交互に現れる。これを、出現頻度が高い符号ほど短い表現で置き換えるハフマン符号でさらに圧縮していく。その際、符号列そのものと位置情報から生成したハフマン符号、長さ情報だけから生成したハフマン符号という2種類の符号を組み合わせる。

歴史と応用

1992年にフィル・カッツ（Phillip W. Katz）氏が「PKZIP」という圧縮ソフトのバージョン2に組み込んだアルゴリズムで、1996年にはIETFによってRFC 1951として標準化されている。DeflateはLZWのような特許問題が無いことから、オープンソースソフトウェアや標準規格などに広く普及した。

汎用の圧縮ファイル形式としてはZipやgzip、7zなどに、画像圧縮形式としてPNGに採用された。オープンソースのライブラリとしてzlibが整備され、商用を含む様々なソフトウェアやプログラミング言語処理系にも組み込まれていった。

Webサーバが送信データを圧縮する形式（Content-Encoding: deflate）の一つとしても採用されており、メディアタイプ（MIMEタイプ）として「application/gzip」（gzipファイル形式）あるいは「application/zlib」（zlibデータ形式）が定められている。

(2023.5.9更新)