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アルゴリズムは、様々なものに使われている(順不同)。
その他の応用
- HTTP圧縮 (Deflateアルゴリズムと、gzipファイルフォーマットを使う)
以下のプログラミング言語や環境も、Deflateアルゴリズムを標準で提供する。
再検索