Deflate

使用LZ77算法与哈夫曼编码的无损数据压缩算法

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

菲爾·卡茨及其所擁有的PKWARE, Inc英語PKWARE, Inc為該演算法申請了美國專利5051745號[2]。人們普遍認為DEFLATE不受任何專利所覆蓋,並且在LZWGIF檔案格式使用)相關的專利失效之前,這種格式除了應用在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命名空間中。

參見

參考文獻

外部連結