Deflate
Deflate（デフレート）とはLZ77とハフマン符号化を組み合わせた可逆データ圧縮アルゴリズム。フィル・カッツが開発した圧縮ツールPKZIPのバージョン2で使われていた。ZIPやgzipなどで使われている。1996年5月に RFC 1951 としてドキュメント化された。ヘッダーやフッターをつけた zlib (RFC 1950) 形式や gzip (RFC 1952) 形式とともに使われる事が多い。
特徴
- 可逆圧縮
- インターネットで広く使われている圧縮形式
- 圧縮は比較的高速、伸長（元に戻すこと／展開）は非常に高速。ただし、LZWなどと比べると計算量は多い。
- 特許問題：LZ77には色々な会社・人物が特許を取っていた。zlibの実装においては、特許を回避するように注意深く実装された。保証されていなく、かつ、議論もあったが特許にかかわるアルゴリズムは全て回避できたと考えられている。また、開発当初は問題となった特許も現在では大半は有効期限が切れた。
日本人により考案されたLHAとほぼ同じアルゴリズムを使う。
技術詳細
deflateは、LZ77（実際にはその変種のLZSS）でデータを「文字そのもの」または （一致長, 一致位置） ペアに符号化する。その結果のうち、「文字そのもの」および「一致長」を合わせて一つのハフマン符号で符号化し、「一致位置」を別のハフマン符号で符号化する。deflateのハフマン符号化は、ブロック毎に符号を(再)構築する方式で、ダイナミックハフマン符号（英: Dynamic Huffman coding）と呼んでいる。日本で一般に動的ハフマン符号と呼ばれている適応形ハフマン符号（en:Adaptive Huffman coding）とは異なるので注意。
利用例
Deflateアルゴリズムが利用されているソフトウェアの一例を挙げる。
また、ほとんどのプログラミング言語で利用できる。以下はその一例。
- 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 (RFC 1950) と gzip (RFC 1952) などがある。zlib はヘッダーが2バイト以上、フッターが4バイトであるのに対して、gzip はヘッダーが10バイト以上、フッターが8バイトである。gzip の方が情報が多く、どのファイルシステム上で圧縮されたかも書いてある。フッターには zlib は Adler-32 を使い、gzip は CRC-32 を使っている。
関連項目
外部リンク
- 統合アーカイバプロジェクト
- アーカイブ形式解説
- RFC 1950(zlib)
- RFC 1951(Deflate)
- Archiver Compression Test
