Deflate

Deflate（デフレート）とはLZ77とハフマン符号化を組み合わせた可逆データ圧縮アルゴリズム。フィル・カッツが開発した圧縮ツールPKZIPのバージョン2で使われていた。ZIPやgzipなどで使われている。1996年5月に RFC 1951 としてドキュメント化された。ヘッダーやフッターをつけた zlib (RFC 1950) 形式や gzip (RFC 1952) 形式とともに使われる事が多い。
特徴.
日本人により考案されたLHAとほぼ同じアルゴリズムを使う。
技術詳細.
deflateは、LZ77（実際にはその変種のLZSS）でデータを「文字そのもの」または （一致長, 一致位置） ペアに符号化する。その結果のうち、「文字そのもの」および「一致長」を合わせて一つのハフマン符号で符号化し、「一致位置」を別のハフマン符号で符号化する。deflateのハフマン符号化は、ブロック毎に符号を(再)構築する方式で、ダイナミックハフマン符号（）と呼んでいる。日本で一般に動的ハフマン符号と呼ばれているとは異なるので注意。
利用例.
Deflateアルゴリズムが利用されているソフトウェアの一例を挙げる。
また、ほとんどのプログラミング言語で利用できる。以下はその一例。
Apache HTTP ServerなどのWebサーバでも圧縮通信を zlib 形式で Deflate を使って実装している。
zlibとgzip.
deflateとともによく使われるヘッダー・フッターには zlib (RFC 1950) と gzip (RFC 1952) などがある。zlib はヘッダーが2バイト以上、フッターが4バイトであるのに対して、gzip はヘッダーが10バイト以上、フッターが8バイトである。gzip の方が情報が多く、どのファイルシステム上で圧縮されたかも書いてある。フッターには zlib は Adler-32 を使い、gzip は CRC-32 を使っている。