Sereinme

DEFLATE 是同时使用了 LZ77 算法和哈夫曼编码（Huffman Coding）的一个无损数据压缩算法。它最初由 Phil Katz 为其 PKZIP 软件第二版所定义，后来被 RFC 1951 标准化。DEFLATE 在 zip、gzip 和 png 文件中均有应用。

引言#

DEFLATE 算法由改进的 LZ77 压缩算法和 Huffman 编码算法组成。改进的 LZ77 算法和 Huffman 编码算法保留了原算法的基本原理，提高了 DEFLATE 算法的压缩速度，增加了算法灵活度，使其具备良好的适应性。

在 DEFLATE 算法中，首先使用改进的 LZ77 算法对原始数据进行压缩，然后使用改进的 Huffman 编码对 LZ77 压缩数据进行二次压缩，最终压缩数据为 Huffman 编码后的 LZ77 压缩数据。

改进 LZ77#

LZ77 压缩算法将所有数据都处理成为一个三元组串，每个三元组至少需要 3 个字节表示，如果在动态字典中未找到匹配字符串，会将 1 个字节输出为 3 个字节，这就导致了字节浪费。因此在 DEFLATE 算法中对其使用的 LZ77 算法进行了以下改进：

• 对匹配字符串长度小于 3 的字符串不压缩。因为长度小于 3 的字符串，使用三元组表示，对原始数据不能起到压缩的作用。
• 对字符串的匹配长度进行了限制，范围为（-128~127），用 8bit 表示，滑动窗口大小为 32KB ，用 15bit 表示，将压缩数据构造为标识 + 数据的形式，具体如表所示。该存储方式，降低了压缩数据的存储空间。
• 由于只查找匹配长度大于 3 的字符串，为提高算法速度，在查找匹配字符串时，使用了哈希链结构搜索算法，其中哈希算法将 3 字节压缩到 2 字节，虽然哈希链结构存在搜索到错误结果的可能，但还是大幅提高了搜索速度。

改进 Huffman#

经过 Huffman 编码压缩后的压缩数据由码表和编码数据两部分组成，在 DEFLATE 算法中使用的 Huffman 编码算法，根据码表的生成方式不同，分为静态 Huffman 编码和动态 Huffman 编码，其中静态 Huffman 编码使用预先定义码表并始终固定，无需在压缩数据中存储，动态 Huffman 编码需要根据待处理数据情况，生成动态码表，并在压缩数据中存储，DEFLATE 算法中主要对动态 Huffman 编码算法进行了以下改进：

• 固定 Huffman 码表生成规则，从 Huffman 编码的构造可知，同样的数据由于二叉树的生成方式或顺序不同，可以得到不同的 Huffman 码表，通过固定二叉树生成方式及顺序，使同样的数据得到相同的 Huffman 码表。
• 使用码长记录码表，进一步压缩码表占用的存储空间，这样使用 1 字节就可以表示码长为 1 到 256 的任一码字。
• 对需要存储的 Huffman 码表进行了二次编码压缩，在 DEFLATE 算法中最终使用 3 张 Huffman 编码表，实现了其 Huffman 编码表的存储。

改进后的 Huffman 编码算法，在兼顾运算速度的情况下，有效减少了压缩数据的存储空间。

DEFLATE 处理流程#

DEFLATE 将所有待压缩的数据都看成二进制数据流，最基本的处理元素为字节，其中 Huffman 编码算法采用动态或静态编码由 DEFLATE 算法根据压缩比进行自动选择。其中采用动态 Huffman 编码的 DEFLATE 算法具体处理流程如图 1 所示。首先将原始数据进行 LZ77 压缩处理，对应表中的数据构成，得到 “标识 + 数据” 和 “偏移” 两部分数据；然后使用 Huffman 编码算法对两部分数据分别进行压缩，得到 “码表 1 ” 和 “码表 2 ”，以及使用两张码表编码压缩的 “压缩数据 1 ” 和 “压缩数据 2 ”；最后继续使用 Huffman 编码对 “码表 1” 和 “码表 2 ” 进行压缩，得到 “码表 3 ” 和 “压缩数据 3 ”。

经过上述处理，原始数据经过压缩后，采用静态 Huffman 编码的 DEFLATE 算法需要存储的数据为 “压缩数据 1” 和 “压缩数据 2 ”；采用动态 Huffman 编码的 DEFLATE 算法需要存储的数据为 “压缩数据 1 ”、“压缩数据 2 ”、“压缩数据 3 ” 和 “码表 3 ”，解压缩为压缩过程的逆运算。