要实现解压缩肯定得了解压缩的过程,解压缩相比压缩来说是简单很多,简单说一下压缩的过程。
01
扫描文件
压缩程序首先会扫描被压缩的文件,然后将文件的信息分为3类:
ZIP压缩是按照Byte为单位对原始文件进行处理的,literal代表的就是原始的Byte数据并没有被压缩。
length和distance是成对出现的,就是用2个数字来代表一些Byte,比如(仅仅是举例说明原理):
后面的10个长度字符,就是2个数字代表了,这样就达到了压缩效果。
所以,扫描完文件之后,就得到了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种:
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中记录的并不是整棵树的编码信息,这里又进行了一个非常巧妙的处理:
就是规定了是左边那种形式的树,这样需要记录的信息又减少了。
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个特殊的数字:
这样处理之后,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数组的长度信息:
注:上面的这些压缩信息只有动态Huffman压缩方法才有。
最前面使用3个bit记录Header信息:
第一个比特:
第2、3比特表示3个选择:
整个压缩后的信息:
注意:ZIP是对每个文件都单独压缩的,而且每个文件还可能会分块进行压缩(这也是Header的第1个bit的作用,标志是否是最后1个块),所以每个使用了动态Huffman的压缩的块都是上面这种结构。
文章主要图片来源:
https://www.cnblogs.com/esingchan/p/3958962.html