Deflate

Deflate（デフレート）とはLZ77とハフマン符号化を組み合わせた可逆データ圧縮アルゴリズム。フィル・カッツが開発した圧縮ツールPKZIPのバージョン2で使われていた。ZIPやgzipなどで使われている。1996年5月に  としてドキュメント化された。ヘッダーやフッターをつけた zlib () 形式や gzip () 形式とともに使われる事が多い。

特徴 
 可逆圧縮
 インターネットで広く使われている圧縮形式
 圧縮は比較的高速、伸長（元に戻すこと/展開）は非常に高速。ただし、LZWなどと比べると計算量は多い。
 特許問題：LZ77には色々な会社・法人・人物が特許を取っていた。zlibの実装においては、特許を回避するように注意深く実装された。保証されておらず、かつ、議論もあったが特許にかかわるアルゴリズムは全て回避できたと考えられている。また、開発当初は問題となった特許も現在では大半は特許権、ライセンス等が消滅し、パブリックドメインとなっている。

日本人により考案されたLHAとほぼ同じアルゴリズムを使う。

技術詳細 
deflateは、LZ77（実際にはその変種のLZSS）でデータを「文字そのもの」または （一致長, 一致位置） ペアに符号化する。その結果のうち、「文字そのもの」および「一致長」を合わせて一つのハフマン符号で符号化し、「一致位置」を別のハフマン符号で符号化する。deflateのハフマン符号化は、ブロック毎に符号を(再)構築する方式で、ダイナミックハフマン符号（）と呼んでいる。日本で一般に動的ハフマン符号と呼ばれているとは異なるので注意。

利用例 
Deflateアルゴリズムが利用されているソフトウェアの一例を挙げる。
 zlib
 ZIP
 GZIP
 7z
 Portable Network Graphics (PNG)

また、ほとんどのプログラミング言語で利用できる。以下はその一例。
 Java - Deflater クラスで nowrap を有効にすることにより素の deflate が扱え、別途 zlib 形式や gzip 形式のヘッターやフッターの付いた物も扱える。
 Perl
 PHP
 Python
 Ruby
 C#、VB.NET等の.NET Framework 2.0以降対応言語 - DeflateStream クラスで素の deflate もしくは GZipStream クラスで gzip 形式。 

Apache HTTP ServerなどのWebサーバでも圧縮通信を zlib 形式で Deflate を使って実装している。

zlibとgzip
deflateとともによく使われるヘッダー・フッターには zlib () と gzip () などがある。zlib はヘッダーが2バイト以上、フッターが4バイトであるのに対して、gzip はヘッダーが10バイト以上、フッターが8バイトである。gzip の方が情報が多く、どのファイルシステム上で圧縮されたかも書いてある。フッターには zlib は Adler-32 を使い、gzip は CRC-32 を使っている。

関連項目 
 データ圧縮
 アルゴリズム

外部リンク 
 統合アーカイバプロジェクト

 
 (zlib)
 (Deflate)
 Archiver Compression Test

データ圧縮
アルゴリズム
1951