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アルゴリズムを標準で提供する。

用語の所属
圧縮アルゴリズム
関連する用語
ZIP (総称)
Deflate64

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club