収縮する

コンピューティングの分野では、Deflate（DEFLATEと表記され、Flate ^{[1] [2]とも呼ばれる）は、} LZ77とハフマン符号化を組み合わせたロスレス データ圧縮 ファイル形式です。これは、 Phil KatzがPKZIPアーカイブツールのバージョン2用に設計しました。Deflateは後にRFC 1951（1996）で仕様化されました。^[3]

Katzは、Deflateストリームの構築に使用されるオリジナルのアルゴリズムも設計しました。このアルゴリズムは米国特許5,051,745として特許を取得し、PKWARE, Inc.に譲渡されました。 ^{[4] [5]} RFC文書に記載されているように、Deflateファイルを生成するアルゴリズムは、特許でカバーされていない方法で実装可能であると広く考えられていました。^{[3]これにより、Katzが最初に設計した}ZIPファイル形式に加えて、 gzip圧縮ファイルやPNG画像ファイルなど、広範囲に使用されるようになりました。特許はその後失効しています。

Deflate ストリームは一連のブロックで構成されます。各ブロックの前には 3ビットのヘッダーが付きます。

• 最初のビット: ストリーム内の最後のブロックマーカー:
  • 1: これはストリームの最後のブロックです。
  • 0: このブロックの後に処理するブロックがさらにあります。
• 2 番目と 3 番目のビット: このブロック タイプに使用されるエンコード方法:
  • 00: 保存された（別名rawまたはliteral）セクション。長さは0〜65,535バイト
  • 01: RFCで定義された事前合意されたハフマンツリーを使用した静的ハフマン圧縮ブロック
  • 10:動的ハフマン圧縮ブロック。ハフマンテーブルが付属。
  • 11: 予約済み - 使用しないでください。

保存されたブロック オプションは、最小限のオーバーヘッドを追加し、圧縮できないデータに使用されます。

圧縮可能なデータのほとんどは、最終的には、各データ ブロックごとにカスタマイズされた最適化されたハフマン ツリーを生成する動的ハフマン10エンコーディングメソッドを使用してエンコードされます。必要なハフマン ツリーを生成するための命令は、ブロック ヘッダーの直後に続きます。静的ハフマン オプションは、ツリーを省略することで得られる固定の節約が、最適でない (したがって、技術的にはハフマンではない) コードを使用することによる圧縮率の低下を上回っている短いメッセージに使用されます。

圧縮は次の 2 つのステップで実現されます。

• 重複する文字列をポインターで照合して置換します。
• 使用頻度に基づいて、シンボルを新しい重み付けされたシンボルに置き換えます。

圧縮ブロック内で、重複するバイト列 (繰り返し文字列) が見つかった場合、後方参照が挿入され、その同一文字列の前の位置へのリンクが張られます。以前の文字列とのエンコードされた一致は、8 ビットの長さ (3 ～ 258 バイト) と、重複の先頭までの 15 ビットの距離 (1 ～ 32,768 バイト) で構成されます。距離がデコードされた非圧縮データの最後の 32  KiB (スライディング ウィンドウと呼ばれる) 内に収まっている限り、任意の数のブロックにわたって相対的な後方参照を作成できます。

距離が長さより短い場合、重複部分は重複し、繰り返しを示します。たとえば、10 個の同一バイトの連続は 1 バイトとしてエンコードされ、その後に前のバイトから始まる長さ 9 の重複部分が続きます。

先行するテキストで重複する部分文字列を検索する処理は、DEFLATE アルゴリズムの中で最も計算コストがかかる部分であり、圧縮レベルの設定が影響する操作です。

2 番目の圧縮段階では、よく使用されるシンボルを短い表現に置き換え、あまり使用されないシンボルを長い表現に置き換えます。使用される方法はハフマン コーディングで、重複しない間隔のプレフィックスなしツリーを作成します。各シーケンスの長さは、そのシンボルをエンコードする必要がある確率の対数に反比例します。シンボルをエンコードする必要がある可能性が高くなるほど、そのビット シーケンスは短くなります。

288 個のシンボルのためのスペースを含むツリーが作成されます。

• 0～255: リテラルバイト/シンボル0～255を表します。
• 256: ブロックの終わり – 最後のブロックの場合は処理を停止し、そうでない場合は次のブロックの処理を開始します。
• 257～285: 追加ビットと組み合わせると、一致の長さは 3～258 バイトになります。
• 286、287: 使用されていない、予約済み、違法ですが、それでもツリーの一部です。

一致長さコードの後に​​は必ず距離コードが続きます。読み取られた距離コードに基づいて、最終的な距離を生成するためにさらに「追加」ビットが読み取られる場合があります。距離ツリーには 32 個のシンボル用のスペースがあります。

• 0～3: 距離1～4
• 4～5: 距離5～8、追加ビット1つ
• 6～7: 距離9～16、追加ビット2つ
• 8～9: 距離17～32、追加ビット3つ
• ...
• 26～27: 距離 8,193～16,384、追加ビット 12 個
• 28～29: 距離 16,385～32,768、追加ビット 13
• 30～31: 使用されていない、予約済み、違法ですが、それでもツリーの一部です。

一致距離シンボル2～29の場合、追加ビットの数は次のように計算できることに注意してください。 ${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor -1}$

2 つのコード (288 シンボル長/リテラル​​ ツリーと 32 シンボル距離ツリー) は、各シンボルのコードのビット長を指定することにより、標準ハフマン コードとしてエンコードされます。ビット長自体は、可能な限りコンパクトな表現を生成するためにランレングス エンコードされます。ツリー表現を含める代わりに、「静的ツリー」オプションは、標準の固定ハフマン ツリーを提供します。静的ツリーを使用した圧縮サイズは、動的ツリーの生成に使用されるのと同じ統計 (各シンボルの出現回数) を使用して計算できるため、圧縮器は小さい方を簡単に選択できます。

圧縮段階では、一致する文字列の検索に費やす時間を選択するのはエンコーダーです。zlib/gzipリファレンス実装では、ユーザーは、結果の圧縮レベルとエンコード速度のスライディング スケールから選択できます。オプションの範囲は、0(圧縮を試みず、圧縮せずに保存する)から、zlib/ 9gzip のリファレンス実装の最大機能を表すものまであります。

他にも Deflate エンコーダーが開発されており、それらはすべて、既存の Deflate デコーダーで解凍できる互換性のあるビットストリームを生成します。実装が異なると、最終的に生成されるエンコードされたビットストリームも異なる可能性があります。zlib 以外のバージョンのエンコーダーでは、通常、より効率的に圧縮され、より小さなエンコードされたストリームを生成することに重点が置かれています。

PKWARE が規定する Deflate64 は、Deflate の独自バージョンです。基本的には同じアルゴリズムです。変更点は、辞書サイズが 32 KB から 64 KB に増加したこと、距離コードが 16 ビットに拡張されて 64 KB の範囲をアドレス指定できるようになったこと、長さコードが 16 ビットに拡張されて 3 から 65,538 バイトの長さを定義できるようになったことです。^[6]これにより、Deflate64 は Deflate よりも圧縮時間が長くなり、圧縮率がわずかに高くなる可能性があります。^[7] 7-Zipなどのいくつかの無料および/またはオープン ソース プロジェクトは Deflate64 をサポートしていますが、^zlibなどの他のプロジェクトは、この手順が独自仕様であること^[9]と、Deflate に比べてパフォーマンスがわずかに向上することから、サポートしていません。^[10]

Deflate の実装は、多くの言語で無料で入手できます。C で書かれたアプリは通常、zlib ライブラリを使用します(寛容なzlib ライセンス)。Borland Pascal (および互換言語) のアプリは、paszlib を使用できます。C ++のアプリは、 7-Zipの改良された Deflate ライブラリを利用できます。Javaと.NET Framework はどちらも、ライブラリ (それぞれ、および System.IO.Compression) で Deflate のすぐに使用できるサポートを提供しています。Adaのアプリは、Zip-Ada (純粋) または ZLib-Ada を使用できます。 java.util.zip

• PKZIP : 最初の実装。元々はPhil KatzがPKZipの一部として行ったもの。
• zlib : オープンソースで許容的なライセンスのため、多くのアプリで採用されている標準リファレンス実装。より高性能なフォークについては、Zlib § フォークを参照してください。
• Crypto++ : 潜在的なセキュリティ脆弱性を減らすことを目的としたC++のパブリック ドメイン実装が含まれています。作者の Wei Dai は、「このコードはそれほど巧妙ではありませんが、zlib よりも理解しやすく、保守しやすいと思います」と述べています。
• 7-Zip : Igor Pavlov がC++で作成したこのバージョンは、ライセンスが無料で、CPU 使用率を犠牲にして zlib よりも高い圧縮率を実現します。DEFLATE64 ストレージ形式を使用するオプションがあります。
• PuTTY 'sshzlib.c': Simon Tatham によるMIT ライセンスに基づくスタンドアロン実装。完全なデコード機能を備えていますが、静的ツリーのみの作成のみをサポートしています。
• libflate: ^[11]ベル研究所のPlan 9の一部で、deflate圧縮を実装している。
• Hyperbac : 独自の圧縮ライブラリ (C++ およびアセンブリ) を使用し、DEFLATE64 ストレージ形式を実装するオプションを備えています。
• Zopfli : GoogleによるApache ライセンスに基づく C 実装。CPU 使用率を犠牲にして、より高い圧縮率を実現します。ZopfliPNG は、 PNGファイルで使用するための Zopfli のバリエーションです。
• igzip: x86アセンブリ言語で書かれたエンコーダー。IntelがMITライセンスの下でリリース。zlib-1より3倍高速。ゲノムデータの圧縮に便利。^[12]
• libdeflate: ^[13]高速なバッファ全体のDEFLATEベースの圧縮と解凍のためのライブラリ。libdeflateは、特にx86プロセッサ上で高度に最適化されています。

AdvanceCOMPは、7-Zip、libdeflate、ZopfliのDeflateの高圧縮率バージョンを使用して、gzip、PNG、MNG、ZIPファイルの再圧縮を可能にし、zlibが最大設定で達成できるよりも小さなファイルサイズを実現します。^[14]

• Comtech AHA の AHA361-PCIX/AHA362-PCIX は、Wayback Machineに 2006-12-08 にアーカイブされています。Comtech は、圧縮されていない受信データに対して最大 3.0 Gbit/s (375 MB/s) の速度で Deflate を使用してストリームを圧縮できるPCI-Xカード (PCI-ID: ) を製造しました。AHA361 -PCIX のLinux カーネルドライバーには、 Apacheのハードウェア圧縮を使用できる" " ユーティリティとカスタマイズされた " " が付属しています。ハードウェアは、 Xilinx Virtex FPGAと 4 つのカスタム AHA3601 ASICに基づいています。 AHA361/AHA362 ボードは静的ハフマン ブロックの処理のみに制限されており、サポートを追加するにはソフトウェアを変更する必要があります。カードは完全な Deflate 仕様をサポートできなかったため、カード自身の出力 (動的ハフマン タイプ 2 ブロックを含まないストリーム) のみを確実にデコードできました。193f:0001 ahagzipmod_deflate_aha
• Indra Networks の StorCompress 300/MX3。これは、1 から 6 個の圧縮エンジンを搭載し、最大 3.6 Gbit/s (450 MB/s) の処理速度を誇るPCI (PCI-ID: ) または PCI-X カードのシリーズです。このカードのバージョンは、 SANやバックアップではなく Web サービス用に特別に設計された別ブランドのWebEnhanceで提供されています。PCIeリビジョンのMX4E も製造されています。17b4:0011
• AHA363-PCIe/AHA364-PCIe/AHA367-PCIe。2008 年、Comtech は新しいハードウェア AHA3610 エンコーダ チップを搭載した 2 つの PCIe カード ( PCI-ID: 193f:0363/ 193f:0364) の製造を開始しました。この新しいチップは、持続 2.5 Gbit/s に対応できるように設計されました。これらのチップを 2 つ使用すると、AHA363-PCIe ボードは 2 つのチャネル (2 つの圧縮と 2 つの解凍) を使用して、最大 5.0 Gbit/s (625 MB/s) の速度で Deflate を処理できます。AHA364-PCIe バリアントは、送信ロード バランサ用に設計されたカードのエンコード専用バージョンで、代わりに複数のレジスタ セットを備え、2 つの物理圧縮エンジンに 32 の独立した仮想圧縮チャネルを供給できます。Linux、 Microsoft Windows、およびOpenSolarisカーネル デバイス ドライバーは、両方の新しいカードで使用できます。また、動的にリンクされたアプリケーションが内部の変更なしでハードウェア サポートを自動的に使用できるように、変更された zlib システム ライブラリも使用できます。 AHA367-PCIe ボード ( PCI-ID: 193f:0367) は AHA363-PCIe に似ていますが、持続的な圧縮速度 10 Gbit/s (1250 MB/s) を実現するために 4 つの AHA3610 チップを使用しています。AHA362-PCIX とは異なり、AHA363-PCIe ボードと AHA367-PCIe ボードの解凍エンジンは完全に deflate に準拠しています。
• Cavium, Inc. のNitrox および Octeon ^{[ permanent dead link ]}プロセッサには、ZLIB と GZIP の両方と互換性のある高速ハードウェア デフレートおよびインフレート エンジンが搭載されており、一部のデバイスでは複数のデータ ストリームを同時に処理できます。
• HDL-Deflate GPL FPGA 実装。
• CAST Inc. の ZipAccel-C。これは、Deflate、 Zlib、Gzip圧縮をサポートするシリコン IP コアです。ZipAccel-C はASICまたはFPGAに実装でき、動的および静的ハフマン テーブルの両方をサポートし、100 Gbps を超えるスループットを提供できます。同社は、Intel FPGA (ZipAccel-RD-INT) および Xilinx FPGA (ZipAccel-RD-XIL) 用の圧縮/解凍アクセラレータ ボード リファレンス デザインを提供しています。
• Intel Xeon E5-2600およびE5-2400プロセッサシリーズ（Sandy Bridge-EP/EN）用のIntel Communications Chipset 89xxシリーズ（Cave Creek）は、QuickAssistテクノロジを使用したハードウェア圧縮と解凍をサポートしています。チップセットに応じて、5Gbit/s、10Gbit/s、または20Gbit/sの圧縮および解凍速度が利用できます。^[15]
• IBM z15 CPUには、RFC1951で規定されているハードウェアDeflate圧縮および解凍用にz14システムで使用されるzEDC Express I/O拡張カードのNest Accelerator Unit (NXU)ハードウェアアクセラレーションの改良版が組み込まれています。^{[16] [17]}
• POWER9アーキテクチャー以降、IBMは、 POWER7+で導入された以前は暗号中心だったNestアクセラレーター（NX）コアに、Deflate（RFC 1951で指定）の圧縮と解凍のハードウェアサポートを追加しました。このサポートは、 zlibNXライブラリを通じて、 AIX 7.2テクノロジーレベル4拡張パックまたはAIX 7.2テクノロジーレベル5サービスパック2で実行されるプログラムで利用できます。^{[18] [19]}

Inflate は、Deflate ビットストリームを解凍して、元のフルサイズのデータ​​またはファイルを正しく生成するデコード プロセスです。

代替の Inflate 実装の通常の目的は、高度に最適化されたデコード速度、またはマイクロコントローラ組み込みシステムの非常に予測可能な RAM 使用量を実現することです。

• 組み立て
  • 6502 inflate は、Piotr Fusik によって6502アセンブリ言語で記述されました。
  • SAMflate は、 SAM Coupé用のオプションのメモリ ページング サポートを備え、 Andrew Collier によってZ80アセンブリ言語で作成され、BSD / GPL / LGPL / DFSGライセンスの下で利用可能になりました。
  • gunzip は、Laurens Holst によってMSX用のZ80アセンブリ言語で書かれ、BSDライセンスで提供されています。
  • inflate.asm は、 Keir Fraser によって書かれ、パブリック ドメインにリリースされた、 M68000マシン言語での高速かつ効率的な実装です。

• C / C++ 言語
  • kunzip は Michael Kohn によるもので、「KZIP」とは無関係です。GNU LGPL ライセンスの C ソース コードが付属しています。GIMPインストーラーで使用されます。
  • puff.c ( zlib ) は、zlib ディストリビューションの /contrib/puff ディレクトリに含まれる、小さくて邪魔にならない単一ファイルのリファレンス実装です。
  • tinf は Jørgen Ibsen によって ANSI C で書かれ、zlib ライセンスが付属しています。約 2k のコードが追加されます。
  • tinfl.c (miniz)、パブリック ドメイン Inflate 実装は、単一の C 関数に完全に含まれています。
• PCDEZIP、ボブ・フランダースとマイケル・ホームズ、PC Magazine 1994-01-11 に掲載。
• John Foderaro による inflate.cl。GNU LGPLライセンスで配布される自立型Common Lispデコーダー。
• inflate.s7i/gzip.s7i は、 Thomas Mertes による、Deflate および gzip 解凍の純粋なSeed7実装です。GNU LGPLライセンスに基づいて提供されています。
• pyflate は、Paul Sladen による純粋なPythonスタンドアロン Deflate ( gzip ) およびbzip2デコーダーです。研究/プロトタイピング用に作成され、 BSD / GPL / LGPL / DFSGライセンスの下で提供されています。
• deflatelua は、 David Manura による、 Deflate およびgzip /zlib 解凍の純粋なLua実装です。
• inflate は、Chris Dickinson による Inflate の純粋なJavascript実装です。
• pako: JavaScript の速度に最適化された zlib のポート。inflate のみを含む個別のビルドが含まれています。

• BitSim の Serial Inflate GPU。Inflate のハードウェア実装。組み込みシステム向けのBitSim のBADGE (Bitsim Accelerated Display Graphics Engine) コントローラー製品の一部です。
• HDL-Deflate GPL FPGA 実装。
• CAST Inc. の ZipAccel-D。これは、Deflate、Zlib、Gzipファイルの解凍をサポートするシリコン IP コアです。ASICまたはFPGAに実装できる ZipAccel-D IP コア。同社は、Intel FPGA (ZipAccel-RD-INT) および Xilinx FPGA (ZipAccel-RD-XIL) 用の圧縮/解凍アクセラレータ ボード リファレンス デザインを提供しています。
• IBM z15 CPUには、RFC1951で規定されているハードウェアDeflate圧縮および解凍用にz14システムで使用されるzEDC Express I/O拡張カードのNest Accelerator Unit (NXU)ハードウェアアクセラレーションの改良版が組み込まれています。^{[16] [17]}
• POWER9アーキテクチャー以降、IBMは、 POWER7+で導入された以前は暗号中心だったNestアクセラレーター（NX）コアに、Deflate（RFC 1951で指定）の圧縮と解凍のハードウェアサポートを追加しました。このサポートは、 zlibNXライブラリを通じて、 AIX 7.2テクノロジーレベル4拡張パックまたはAIX 7.2テクノロジーレベル5サービスパック2で実行されるプログラムで利用できます。^{[18] [19]}

• アーカイブ形式のリスト
• ファイルアーカイバのリスト
• ファイルアーカイバの比較

• PKWARE, Inc.のappnote.txt.ZIP ファイル形式の仕様 ( Wayback Machineに 2014-12-05 にアーカイブ) ; セクション 10、X. デフレート - 方法 8。
• RFC 1951 –デフレート圧縮データ形式仕様バージョン 1.3
• zlib ホームページ
• Deflate アルゴリズムの説明 – Antaeus Feldspar 著
• データ圧縮へのサフィックスツリーの拡張アプリケーション 2016-09-23 にWayback Machineでアーカイブ– Jesper Larsson による Deflate を実装するための優れたアルゴリズム
• Zip ファイル: 歴史、説明、実装 - Deflate 実装のウォークスルー