Deflate(通常按早期計算機編程習慣寫為DEFLATE)是同時使用了LZ77算法與哈夫曼編碼(Huffman Coding)的一個無損數據壓縮算法。它最初是由美國程式設計師菲爾·卡茨(Phil Katz)為他的PKZIP軟件第二版所定義的,後來被RFC 1951標準化[1]。
菲爾·卡茨及其所擁有的PKWARE, Inc為該算法申請了美國專利5051745號[2]。人們普遍認為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命名空間中。
參見
參考文獻
外部連結
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.