VBA解压缩ZIP文件02——压缩过程

要实现解压缩肯定得了解压缩的过程，解压缩相比压缩来说是简单很多，简单说一下压缩的过程。

ZIP压缩过程

01

扫描文件

压缩程序首先会扫描被压缩的文件，然后将文件的信息分为3类：

• literal 未被处理的
• length 长度信息
• distance 距离信息

ZIP压缩是按照Byte为单位对原始文件进行处理的，literal代表的就是原始的Byte数据并没有被压缩。

length和distance是成对出现的，就是用2个数字来代表一些Byte，比如（仅仅是举例说明原理）：

后面的10个长度字符，就是2个数字代表了，这样就达到了压缩效果。

• literal的数字范围是0-255（1个Byte的数字范围）
• length的范围被限定为3-258
• distance的范围被限定为1-32768

所以，扫描完文件之后，就得到了3种数字。

02

数字的处理

扫描得到的3种数字，在ZIP中不是直接使用这些数据来保存压缩信息的，做了进一步的处理。

首先是对length的处理，将length和literal作为一种数字来处理，所以，规定length的数字范围是257开始（256作为了结束标志），也就是对于length来说257代表的就是3。

同时，将长度3-258分成了29个区间：

只记录length所在的那个区间，目的是减少需要记录的数字个数。

这样在读取到length的数字的时候，再到这个区间去查找，将Lengths字段的开始的那个数字，加上需要扩展的Extra bits代表的数字。

distance的做法和length差不多，划分为了29个区间：

这样处理之后，数字就变为了2种：

• 0-285
• 0-29

03

Huffman编码

扫描结束最终得到的2种数字，对这2种数字进行Huffman编码，Huffman树这种结构就是一种特殊的2叉树：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。（百度）

只要了解在ZIP中Huffman能达到的目的就是，用最少的bit（1Byte=8bit）来表示需要编码的那些数字。

Huffman树需要编码的是0-285和0-29这2种数字，所生成的2颗树分别为h1（编码literal和length）和h2（编码distance），编码完成后，ZIP中记录的并不是整棵树的编码信息，这里又进行了一个非常巧妙的处理：

• 首先ZIP中Huffman树的深度不会超过15（为什么不知道！）
• 其次，规定了树的类型，也就是所有的叶子节点都是在左边的：

就是规定了是左边那种形式的树，这样需要记录的信息又减少了。

Huffman树编码完成之后，就能够统计出每个叶子节点所在的深度，也就是每个数字对应的码长，所以ZIP记录的是Huffman Code Length，简称CL，h1对应的是CL1，h2对应的是CL2。

CL1和CL2中记录的就是0-15的码长，直接使用数组记录，也就是下标代表的是数字，数组中的值代表的是Huffman树的码长Code Length(0-15数字)。

04

Code Length的再处理

为了进一步达到压缩，ZIP中对CL1和CL2又进行了处理！

就是使用游程编码对CL1和CL2中的数字进行了进一步的压缩，主要的思想就是用1个特殊的数字来代表N个重复的数字。

因为Code Length的数字范围是0-15，所以这里又规定了3个特殊的数字：

• 16表示除了0以外的其它游程，2比特，记录连续的3-6个
• 17表示0游程，3比特，记录连续的3-10个0
• 18表示0游程，7比特，记录连续的11-138个0

这样处理之后，CL1和CL2就转换为了0-18的数字，数组的长度就被压缩了，压缩后的数组记做SQ1和SQ2（Sequence），数组的值是0-18的数字（解压的时候得到这个数字后，还需要通过游程编码还原为Code Length）。

然后ZIP中使用第3个Huffman树对SQ1和SQ2进行了编码，并且认为深度不会超过7，原理和h1、h2是一样的，编码之后，仍然记录Code Length，记录h3的Code Length记做CCL，所以CCL数字的范围是0-7，因为记录的是0-18的数字，所以CCL数组长度最长是19。

04

CCL的再处理

得到CCL的0-18的数字之后，ZIP中认为数字出现的频率不一样，把可能出现0次的数字排到后面的话，就可能只需要记录前面数字的次数，没有出现次数的数字就不需要记录了，所以CCL数组的顺序进行了一个转换：

05

压缩信息的记录

CCL的数字范围是0-7，使用的是固定的3个bit来记录，最长是19个，但是通过CCL的再处理之后，真正记录的个数是很有可能小于19的，所以要记录CCL数组的长度信息：

• 在CCL的bit流前面使用4bit记录了CCL的长度，记做HCLEN，而且认为CCL个数不会低于4个，所以CCL的个数是HCLEN+4。
• 在HCLEN的bit流前面使用5bit记录了CL2的长度，记做HDIST，而且CL2个数最少有1个，所以CL2的个数是HDIST+1。
• 在HDIST的bit流前面使用5bit记录了CL1的长度，记做HLIT，而且CL1个数最少有257个（因为至少有0-255总共256个literal，还有一个256表示解码结束），所以CL2的个数是HLIT+257。

注：上面的这些压缩信息只有动态Huffman压缩方法才有。

最前面使用3个bit记录Header信息：

第一个比特：

• 如果是1，表示此部分为最后一个压缩数据块；
• 否则表示这是.ZIP文件的某个中间压缩数据块，后面还有其他数据块

第2、3比特表示3个选择：

• 00 - no compression，没有压缩
• 01 - compressed with fixed Huffman codes ， 静态Huffman
• 10 - compressed with dynamic Huffman codes ，动态Huffman
• 11 - reserved (error)

整个压缩后的信息：

注意：ZIP是对每个文件都单独压缩的，而且每个文件还可能会分块进行压缩（这也是Header的第1个bit的作用，标志是否是最后1个块），所以每个使用了动态Huffman的压缩的块都是上面这种结构。

文章主要图片来源：

https://www.cnblogs.com/esingchan/p/3958962.html