学习笔记：用实现全手工解压zip文件，包含所有实现的源代码
目录2、静态哈夫曼算法3、非压缩数据算法4、0x7，第7步lz77解码 三、总结
一、引子
前些日子，因为自己手写了一个编码和解码，有点小开心，随口说了句有空挑战一下用手写解压zip文件的代码 。前几天有空，在网上搜索了一下，发现一篇很好的文章《ZIP压缩算法详细分析及解压实例解释》，原文地址:
这篇文章对ZIP压缩算法进行了详细的分析并用一个解压文件实例进行了字节和二进制位的逐步解码和解释，非常感谢作者的讲解，我从中学到了很多知识！
郑重声明：本文引用了《ZIP压缩算法详细分析及解压实例解释》中的部分图片和文字信息，本人在此郑重声明，所有这些图片和文字的版权均归原文作者所有 。如有侵权，请告知我，我会立即删除！
这篇文章大概两万多字，要想全部弄懂弄通确实要动动脑筋，说实话我看了好几遍，终于看懂了，当然后期在编写代码过程中又多次翻看！经过好几天的编写，经历了N次进坑出坑，终于在我疯之前实现了zip文件的解压工作 。
附上全手工解压zip文件源代码地址(编码不易，收费4.99元，以资鼓励)：
【学习笔记：用python3实现全手工解压zip文件，包含所有实现的源代码】（目前只写了单文件的解压算法，多文件和带目录部分还没有写，因为这几天我的工作比较忙，等有空了再完善一下） 。
废话太多，先上解压效果图（本图为解压了一个玫瑰花.jpg文件）：
接下来我就把我的学习和编码过程带给大家，为了简化，我和《原文》例子一样，解压的是一个不带目录的压缩了单个文件的zip文件 。因为本人算法比较弱，而且语文也很一般，写文章是我的弱项！所以难免很多疏忽和错误，有些部分也存在很大的优化空间，希望大家批评指正 。另外，因为是全手工编码，所以内容比较多，文章有点长 。
二、说干就干，七步解码ZIP
《ZIP压缩算法详细分析及解压实例解释》（以下简称《原文》）中讲的很详细，我在这里不再啰嗦，有兴趣可以去原文看分析过程 。这里只列出原文中我需要用到的部分 。
既然是说干就干，那么看懂了《原文》以后我就开工了 。首先我们要明确《原文》的编码流程图如下：
这个图是动态哈夫曼算法的整个编码的流程，如果是静态哈夫曼和非压缩数据要简单得多，下面会给出所有算法的解码方法 。
我们既然是要解码，那么就要从下向上反着来解码！原文举了一个压缩文件的例子，并且一步一步的把zip文件中的字节及二进制数据拆开进行逐步解压展示，非常直观，最后又总结了动态哈夫曼算法的译码过程如下(以下粗体字引用自《原文》)：
1、根据HCLEN得到截尾信息，并参照固定置换表，根据CCL比特流得到CCL整数序列；
2、根据CCL整数序列构造出等价于CCL的二级码表3；
3、根据二级码表3对CL1、CL2比特流进行解码，得到SQ1整数序列,SQ2整数序列；
4、根据SQ1整数序列,SQ2整数序列,利用游程编码规则得到等价的CL1整数序列、CL2整数序列；
5、根据CL1整数序列、CL2整数序列分别构造两个一级码表：/码表、码表；
6、根据两个一级码表对后面的LZ压缩数据进行解码得到//流；
7、根据//流按照LZ规则进行解码 。
接下来我们就一步一个脚印的来解码！
0、先读取数据区数据
进入上面的步骤有个前提，就是需要先把zip文件中的数据区读出来，那么我们先用16进制编辑器看一下《原文》的zip解压例子文件内容：
我们要读出的数据区是从红线之后到蓝线之前，当然我们实际读取的时候需要先找到这个位置，我们可以利用zip文件头的结构以及其中的信息找到这个位置 。《原文》中有文件结构的详细信息，这里不再列举，我们只要跳过头部的固定字节数，再跳过紧接着的文件名的字节数（这个值不固定，但是记录这个文件名所占字节数的位置是固定的第26和第27字节处），再跳过扩展区的字节数（与文件名同理，在第28和第29字节处）就可以直接找到数据区的开始了，数据区的结束在哪呢？我们是单文件的解压，而蓝线部分（ ）是以0x50、0x4B、0x01、0x02开头的，的开头也就是数据区的结束，那么我们只要找到0x50、0x4B、0x01、0x02，也就找到数据区的结束了 。获取数据区的主要代码如下：
# 在列表中查找匹配的一串数值的位置def findvalue(content,subdata):sublen=len(subdata)if content==0 or sublen==0: # 搜索数据为空！return(-1)pos=0catch=0while pos
这样就把zip中的数据区读出来放进data中了，注意data为bytes类型 。data数据由一个或多个数据块构成(每个数据块都可以是不同的算法)，单个动态哈夫曼算法数据块的结构如《原文》的下图：
注意，这个图是一个动态哈夫曼编码数据块的结构图，不适用静态哈夫曼编码数据块以及非压缩数据块（这是我后期发现的，并且网上相关资料很少，只有官方文档中草草提了几句）
这里要着重说一下，里有两个重要标识，第1位标识本数据块是否为最后一个，“1”就是最后一个，“0”说明后面还有数据块，我就是根据这个位来控制读取data中的多个数据块的循环逻辑的; 的第2和第3位用来标识解压的算法，"10"为动态哈夫曼算法，"01"为静态哈夫曼算法，"00"为非压缩算法 。下面我就根据三种不同的算法来继续讲解我们的解码过程！
1、动态哈夫曼算法(前6步)
如果读取的数据块是动态哈夫曼算法(根据的第2和第3位来区分)，我们要进行1~6步骤如下：
0x1、读取CCL
先看代码如下：
isnotend=True# 待解压数据没有结束bindata=http://www.kingceram.com/post/data2bin(data)# 将数据转换为二进制位字符串curpos=0# curpos是当前在bindata中的位置lz77=[]# 待lz77解压列表unzipdata=[]# 解压后数据while isnotend:# 多块解压循环体# Header:3个位,HLIT:5位,HDIST:5位,HCLEN:4位,共17位,所以得先读入四个字节的数据Header=bindata[curpos:curpos+3]if Header[0]=="1":print("Header[0]=",Header[0],"“1说明为最后一个压缩数据块”") ####else:print("Header[0]=",Header[0],"“0说明后面还有数据块”") ####print("压缩算法：",Header[1:3][::-1]) ####if Header[0]=="1":# 1表示此部分为最后一个压缩数据块isnotend=False# 下一次跳出循环if Header[1:3][::-1]=="10":# 因zip中采用的是低位在前的存储方法，所以需要倒序，01倒过来是10，所以是动态哈夫曼print("zip压缩算法：",Header[1:3][::-1],"动态哈夫曼")HLIT=int(bindata[curpos+3:curpos+8][::-1],2)# 说明后面存在HLIT+257=259个CL1,CL1即0-258被编码后的长度，其中0-255表示Literal，256表示无效符号，257、258分别表示Length=3、4（length从3开始）HDIST=int(bindata[curpos+8:curpos+13][::-1],2)# 说明后面存在HDIST+1=11个CL2,CL2即Distance Code=0-10被编码的长度HCLEN=int((bindata[curpos+13:curpos+17])[::-1],2) # 说明紧接着跟着HCLEN+4=18个CCL（每个ccl为3个位）ccl=[]# zip文件中最后生成的ccl序列for k in range(HCLEN+4): # 从二进制数据中取出ccl原始数据ccl.append(bindata[k*3+17+curpos:k*3+20+curpos])for l in range(19-len(ccl)):# ccl补齐19个元素（用"000"补），生成ccl序列ccl.append("000")
注释比较详细，要注意的是，我为了简化，一次性就把所有数据（data）转换为二进制位了，这种方法对于特大文件很耗内存，大家可以根据实际情况进行改进 。另外代码中的HLIT、HDIST、HCLEN解释起来非常麻烦，涉及算法原理 。如果看不懂注释请看《原文》 。
上面代码中用到的转换二进制函数如下：
# 给一个字做按位倒叙def getbin(highbyte,lowbyte):mybyte=str(bin(highbyte*256+lowbyte))# 取出两个字节，小端序mybyte="6d"%int(mybyte[2:])# 二进制数如果不够16位则前面加“0”补齐16位mybyte=mybyte[::-1]# 倒过来return(mybyte)# 将data全部转换为bin字符串def data2bin(data): # data为二进制listresultstr=""lendata=http://www.kingceram.com/post/len(data)if len(data)%2!=0:lendata-=1for i in range(0,lendata,2):resultstr+=getbin(data[i+1],data[i])if len(data)%2!=0:resultstr+=getbin(0,data[len(data)-1])# 如果data不是偶数个字节，在最后补上一个字节的“0”return(resultstr)
要强调的是，因为zip中存储二进制位时都是反序的，所以在中最后要倒过来！之后经常会遇见这样的操作 。还有就是中要补齐偶数个字节，这是掉坑里后发现的 。
读出CCL后，根据算法，按照pk的要求需要交换ccl序列如《原文》的下图：
好，我们进行置换，恢复初始ccl序列：
# 交换ccl,并顺便按二进制取值def changeccl(ccl):ccl=[ccl[3],ccl[17],ccl[15],ccl[13],ccl[11],ccl[9],ccl[7],ccl[5],ccl[4],ccl[6],ccl[8],ccl[10],ccl[12],ccl[14],ccl[16],ccl[18],ccl[0],ccl[1],ccl[2]]for i in range(len(ccl)):ccl[i]=int(ccl[i][::-1],2) # 还是要倒叙，并取值return(ccl)ccl=changeccl(ccl) # 置换ccl
0x2、构造二级码表3
接着我们根据CCL整数序列构造出等价于CCL的二级码表3，也就是用ccl序列生成树3：
deflatetree3=lzq_deflate.mydeflate(ccl)# 返回的是一个字典类型
这里为了方便管理，我专门编了一个动态哈夫曼算法来生成zip专用的哈夫曼树，命名为.py，内容如下：
# coding: utf-8# author: 泉中流# function : 生成zip中的哈夫曼树(定制的huffman树，右边深度优先)# date: 2021.3.10，最后更新时间：2021.3.13# 生成zip中的哈夫曼树对应的编码字典def mydeflate(ccl):MAX_BITS=max(ccl)# ccl中的最大值bl_count=[0]# 存储ccl中每个码长值的个数，bl_count的索引值对应码长值！for i in range(1,MAX_BITS+1):# 不统计ccl中0的个数，因为用不着，上句直接赋0bl_count.append(ccl.count(i))#bl_count=[0,0,2,3,0,4]# 统计ccl中各个码长值的个数，例如得到0个1,2个2,3个3,0个4,4个5#print("bl_count",bl_count)# 算出下一个码长值的初始编码，例如码长值为5的初始编码为28(11100)code = 0bl_count[0]=0next_code=[0]# 索引值为0的第一个值强制为0，这个编码时用不到！for bits in range(1,(MAX_BITS+1)):code = (code + bl_count[bits-1]) << 1# 下一个编码要给当前编码的个数留出足够空间！next_code.append(code)# 从next_code中获取哈夫曼树编码deflatetree={}# print("解码得到哈夫曼树编码(定制的huffman树):")next_code_org=next_code.copy()#备份一下next_code，此句可以不要for index in range(len(ccl)):if(ccl[index]!=0):# ccl数据中的0没有用，所以不编码tmp=str(bin(next_code[ccl[index]]))[2:]if len(tmp)
这段代码我是根据官方文档中的代码片段改写的，核心算法为：code = (code + [bits-1])