Deflate

Deflate（通常按早期計算機編程習慣寫為DEFLATE）是同時使用了LZ77算法與哈夫曼編碼（Huffman Coding）的一個無損數據壓縮算法。它最初是由美國程式設計師菲爾·卡茨（Phil Katz）為他的PKZIP軟件第二版所定義的，後來被RFC 1951標準化。

菲爾·卡茨及其所擁有的PKWARE, Inc為該算法申請了美國專利5051745號。人們普遍認為DEFLATE不受任何專利所覆蓋，並且在LZW（GIF文件格式使用）相關的專利失效之前，這種格式除了應用在ZIP文件格式中，也使用於gzip壓縮文件以及PNG圖像文件中。

DEFLATE壓縮與解壓的源代碼可以在自由、通用的壓縮函式庫zlib上找到。

7-zip實作了更高壓縮比的DEFLATE，AdvanceCOMP也使用這種實作，它可以對gzip、PNG、MNG以及ZIP文件進行壓縮從而得到比zlib更小的文件大小。在Ken Silverman的KZIP與PNGOUT中使用了一種更加高效同時要求更多用戶輸入的DEFLATE程序。

串流格式

Deflate串流是指比特串流。也即，我們首先把它看作字節串流，然後對每個字節，確定其比特順序。對於X86這樣的小端序平台，就是按照字節內部最不顯著比特（Least Significant Bit） 到最顯著比特（Most Significant Bit）的順序。例如，對於字節0x15，它的比特序列是10101000。

Deflate串流包含一系列數據塊。每塊以3比特的標頭開始:

• 第1比特: Last-block-in-stream marker:
  • 1: 串流的最後一塊
  • 0: 不是串流的最後一塊
• 第2、第3比特: 編碼方法
  • 00: 無壓縮的stored/raw/literal, 長度在0至65,535字節
  • 01: 靜態霍夫曼壓縮。採用事先定義（因而無須存儲在串流中）的霍夫曼樹
  • 10: 動態霍夫曼樹
  • 11: 保留，未使用

編程接口

Deflate可以免費在很多編程語言中使用。C語言通常使用zlib函式庫。C++語言可以使用7-Zip/AdvanceCOMP。Java語言包含在標準函式庫java.util.zip中。Microsoft .NET Framework 2.0包含在System.IO.Compression命名空間中。

• PKZIP: 該算法最早的實作
• zlib/gzip: 標準參考實作（standard reference implementation），由於其公共可用性，得到了及其廣泛的使用。
• Crypto++: C++開源實作
• 7-Zip/AdvanceCOMP: Igor Pavlov的C++開源自由實作
• PuTTY 『sshzlib.c』: 一份單獨實作
• Plan 9 from Bell Labs 的libflate（頁面存檔備份，存於網際網路檔案館）
• Hyperbac: C++與組合語言實作
• Zopfli: Google的C語言實作

參見

• 歸檔格式列表
• 壓縮軟件列表
• 壓縮軟件比較

外部連結

• PKWARE, Inc.'s appnote.txt, .ZIP File Format Specification（頁面存檔備份，存於網際網路檔案館）; Section 10, X. Deflating – Method 8.
• RFC 1951 – Deflate Compressed Data Format Specification version 1.3
• zlib Home Page（頁面存檔備份，存於網際網路檔案館）
• An Explanation of the Deflate Algorithm（頁面存檔備份，存於網際網路檔案館） – by Antaeus Feldspar
• Extended Application of Suffix Trees to Data Compression （頁面存檔備份，存於網際網路檔案館） – an excellent algorithm to implement Deflate by Jesper Larsson