Deflate

読み：デフレート
読み：ディフレート
外語：Deflate

品詞：名詞

Phillip Walter Katzが開発し、PKZIPバージョン2以降で採用された圧縮アルゴリズム。

概要

LZ77(スライド辞書法)系のアルゴリズムで、インターネットで広く使われている。deflateは英語でそのまま「しぼませる」という意味がある。

アルゴリズムは、RFC 1951(DEFLATE Compressed Data Format Specification version 1.3)として文書化され、情報提供(Informational)扱いで公開された。

奥村晴彦と吉崎栄泰がLHAで使用するために開発したものを、ハッシュで高速化したもの。その後LHAもハッシュを使用するようになったため、zip/gzipとLHAとで実質的な相違はなくなっている。

つまりLHAとほぼ同様のアルゴリズムを使い、次のような特徴を持っている。

特許問題については保証されているわけではないが、ベースとなるLZ77自体には特許がなく、また現時点でサブマリン特許を主張する者も現われていない。

Deflateは、ZIPでの圧縮方法番号は8である。

LHAと同じくLZ77系、具体的にはLZSSというアルゴリズムを用いて、データを符号化する。ここで得られる結果は、「データそのもの」または「一致位置&一致長」の何れかである。後段では、一致長とそれ以外を分けて二種類のハフマン符号化を行なう。

LHAの場合、あらかじめ全てのデータを検索してハフマンツリーを作って圧縮する静的ハフマン符号である。圧縮率が高いが、速度が遅くなるという難点がある。

一方、Deflateは動的ハフマン符号である。圧縮速度は比較的速いが、圧縮率は悪いという難点がある。

Deflateアルゴリズムは、様々なものに使われている(順不同)。

その他の応用

以下のプログラミング言語や環境も、Deflateアルゴリズムを標準で提供する。

用語の所属