Deflate - 维基百科,自由的百科全书
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命名空间中。
- 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
|