Sereinme

DEFLATE は、LZ77 アルゴリズムとハフマン符号化（Huffman Coding）を組み合わせた、非可逆データ圧縮アルゴリズムです。元々は Phil Katz が彼の PKZIP ソフトウェアの第 2 版で定義し、後に RFC 1951 で標準化されました。DEFLATE は、zip、gzip、および png ファイルで使用されています。

イントロダクション#

DEFLATE アルゴリズムは、改良された LZ77 圧縮アルゴリズムと Huffman 符号化アルゴリズムで構成されています。改良された LZ77 アルゴリズムと Huffman 符号化アルゴリズムは、元のアルゴリズムの基本原理を保持しながら、圧縮速度を向上させ、アルゴリズムの柔軟性を高め、適応性を持たせるために改良されています。

DEFLATE アルゴリズムでは、まず改良された LZ77 アルゴリズムを使用して元のデータを圧縮し、次に改良された Huffman 符号化を使用して LZ77 圧縮データを二次圧縮します。最終的な圧縮データは、Huffman 符号化された LZ77 圧縮データです。

改良された LZ77#

LZ77 圧縮アルゴリズムは、すべてのデータを三つ組の文字列として処理し、各三つ組は少なくとも 3 バイトで表されます。動的辞書に一致する文字列が見つからない場合、1 バイトが 3 バイトに出力されるため、バイトの浪費が発生します。そのため、DEFLATE アルゴリズムでは、以下の改良が行われています：

• 長さが 3 未満の一致する文字列は圧縮しない。なぜなら、長さが 3 未満の文字列は、三つ組で表されるため、元のデータを圧縮する効果がないからです。
• 文字列の一致長を制限し、範囲は（-128〜127）であり、8 ビットで表されます。スライディングウィンドウのサイズは 32KB であり、15 ビットで表されます。圧縮データは、識別子 + データの形式で構築されます。具体的な内容は以下の表に示されています。このストレージ方式により、圧縮データのストレージスペースが削減されます。
• 3 以上の一致長の文字列のみを検索するため、アルゴリズムの速度を向上させるために、一致する文字列の検索時にハッシュチェイン構造の検索アルゴリズムを使用しています。ハッシュアルゴリズムは 3 バイトを 2 バイトに圧縮します。ハッシュチェイン構造には誤った結果が得られる可能性がありますが、検索速度は大幅に向上します。

改良された Huffman#

Huffman 符号化された圧縮データは、コード表と符号化データの 2 つの部分で構成されています。DEFLATE アルゴリズムで使用される Huffman 符号化アルゴリズムは、コード表の生成方法によって静的 Huffman 符号化と動的 Huffman 符号化に分けられます。静的 Huffman 符号化は事前に定義されたコード表を使用し、常に固定されているため、圧縮データに格納する必要はありません。動的 Huffman 符号化は、処理するデータの状況に応じて動的なコード表を生成し、圧縮データに格納する必要があります。DEFLATE アルゴリズムでは、主に動的 Huffman 符号化アルゴリズムを改良しています：

• 固定された Huffman コード表の生成ルール。Huffman 符号化の構造からわかるように、同じデータでも二分木の生成方法や順序が異なるため、異なる Huffman コード表が得られます。固定された二分木の生成方法と順序を使用することで、同じデータに対して同じ Huffman コード表が得られるようにしています。
• コード長を記録するためのコード表を使用し、コード表の使用するストレージスペースをさらに圧縮します。これにより、1 バイトで 1 から 256 のコード長を表すことができます。
• 格納する必要のある Huffman コード表を二次的に圧縮します。DEFLATE アルゴリズムでは、最終的に 3 つの Huffman コード表を使用し、Huffman コード表の格納を実現しています。

改良された Huffman 符号化アルゴリズムは、演算速度を考慮しながら、圧縮データのストレージスペースを効果的に減らしています。

DEFLATE 処理フロー#

DEFLATE は、圧縮するすべてのデータをバイナリデータストリームとして扱い、基本的な処理要素はバイトです。Huffman 符号化アルゴリズムは、DEFLATE アルゴリズムによって圧縮比に応じて自動的に動的または静的な符号化が選択されます。動的 Huffman 符号化を使用する DEFLATE アルゴリズムの具体的な処理フローは、以下の図 1 に示されています。まず、元のデータを LZ77 圧縮処理し、対応する表のデータを構成し、「識別子 + データ」と「オフセット」の 2 つのデータを得ます。次に、Huffman 符号化アルゴリズムを使用して、2 つのデータをそれぞれ圧縮し、「コード表 1」と「コード表 2」、および 2 つのコード表で符号化された圧縮データ「圧縮データ 1」と「圧縮データ 2」を得ます。最後に、「コード表 1」と「コード表 2」を引き続き Huffman 符号化して、「コード表 3」と「圧縮データ 3」を得ます。

上記の処理を経て、元のデータは圧縮され、静的 Huffman 符号化を使用する DEFLATE アルゴリズムでは、「圧縮データ 1」と「圧縮データ 2」を格納する必要があります。動的 Huffman 符号化を使用する DEFLATE アルゴリズムでは、「圧縮データ 1」、「圧縮データ 2」、「圧縮データ 3」、および「コード表 3」を格納する必要があります。これは圧縮プロセスの逆操作である解凍になります。