What’s DEFLATE ?
DEFLATE 是结合LZ77和Huffman coding的一种无损压缩算法。广泛用于gzip, png和zip压缩文件中。
Algorithm Description
在介绍DEFLATE之间， 我们需要先理解上面提到的DEFLATE的两个重要组成部分 : LZ77 和 Huffman Coding。
Huffman Coding
Huffman是一种变长前缀编码格式， 对于出现频率高的字符， 使用短的编码， 而频率低的字符， 使用长编码。 例如， 对于如下权重的字符,
A 16
D 8
E 8
使用Huffman编码得到的Huffman Tree如下:
( )
0 / \ 1
( ) A
0 / \ 1
D E
LZ77 Compression
LZ77算法使用 sliding windows 来记录前面的数据流，当后面的数据流和sliding windows里数据重复时，可以使用距离之前重复数据出现的距离和重复的长度来代替实际数据。 以下面数据为例:
Blah blah blah blah blah!
可以看到， 当读入Blah b之后， 接下来的五个字符和之前的是一样的， 所以用LZ77算法表示为:
Blah b[D=5,L=5]
DEFLATE Algorithm
DEFLATE算法结合上面介绍的LZ77 Compression算法和Huffman Code，来对数据进行压缩处理。其中LZ77用来对数据中重复出现的部分进行处理， 而Huffman Coding则对LZ77处理过的数据进行编码， 将出现频率高的用更短的编码。
具体的对于DEFLATE压缩后的数据是由一系列的block组成的， 每个block格式如下:
- 第一个 bit: 是否为连续的数据中最后一个block
1: 是最后一个block
0: 后面还有连续的block
- 第二和三 bits: 当前block的编码方式:
00: 原始数据, 0到65,535字节长度
01: 使用静态Huffman 编码
10: 使用动态Huffman 编码
11: 保留