GZIP文件压缩

目录

基于huffffman树的文件压缩

huffffman树

huffffman树构建

获取huffffman编码

huffman文件压缩格式：

huffman编码压缩过程:

huffman编码解压缩过程:

代码实现：

LZ77

LZ77原理:

代码实现前的一些问题：

哈希表实现：

LZ77处理大文件：

LZ77压缩

压缩格式数据保存

解压缩

代码实现：

huffman压缩之后的结果为什么会变大：

LZ77压缩之后的结果为什么会变大

GZIP: LZ77和Huffman的结合

---

基于huffffman树的文件压缩

• 根据字符重复出现的次数的不同，进行编码：

  • 

• huffffman树

  • 从二叉树的根结点到二叉树中所有叶结点的路径长度与相应权值的乘积之和为该二叉树的带权路径长度WPL。

  • 

  • 上述四棵树的带权路径长度分别为：
    • WPLa = 1 * 2 + 3 * 2 + 5 * 2 + 7 * 2 = 32
    • WPLb = 1 * 2 + 3 * 3 + 5 * 3 + 7 * 1 = 33
    • WPLc = 7 * 3 + 5 * 3 + 3 * 2 + 1 * 1 = 43
    • WPLd = 1 * 3 + 3 * 3 + 5 * 2 + 7 * 1 = 29
  • 将带权路径最小的二叉树称为Huffffman树

• huffffman树构建

  • 1. 由给定的n个权值{ w1, w2, w3, … , wn}构造n棵只有根节点的二叉树森林F={T1, T2 , T3, … ,Tn},每棵二叉树Ti只有一个带权值wi的根节点，左右孩子均为空。
  • 2. 重复以下步骤，直到F中只剩下一棵树为止
    • 在F中选取两棵根节点权值最小的二叉树，作为左右子树构造一棵新的二叉树,新二叉树根节点的权
    • 值为其左右子树根节点的权值之和
    • 在F中删除这两棵二叉树
    • 把新的二叉树加入到F中

• 获取huffffman编码

  • 1.以字符串中每个字符出现的总次数为权值构建huffman树
  • 2.令huffman树中左分支用0代替，右分支用1代替
  • 3.所有权值节点都在叶子位置，遍历每条到叶子节点的路径获取字符的编码

• huffman文件压缩格式：

  • 

• huffman编码压缩过程:

  • 1.统计源文件中每个字节出现的次数
  • 2.字节频次来创建huffman树
  • 3.获取每个字节的huffman编码
  • 4.添加压缩文件头部信息
  • 5.用得到的编码对源文件中的每个字节进行改写

• huffman编码解压缩过程:

  • 1. 从压缩文件中获取源文件的后缀
  • 2. 从压缩文件中获取字符次数的总行数
  • 3. 获取每个字符出现的次数
  • 4. 重建huffffman树
  • 5. 解压压缩数据
    • a. 从压缩文件中读取一个字节的获取压缩数据ch
    • b. 从根节点开始，按照ch的8个比特位信息从高到低遍历huffffman树：
      • 该比特位是0，取当前节点的左孩子，否则取右孩子，直到遍历到叶子节点位置，该字符就被解析成功，将解压出的字符写入文件
    • 如果在遍历huffffman过程中，8个比特位已经比较完毕还没有到达叶子节点，从a开始执行
    • c. 重复以上过程，直到所有的数据解析完毕

• 代码实现：

  • 哈夫曼压缩 · 1bd11ce · 丘啊哈/代码空间 - Gitee.com
  • 哈夫曼树的构建 · 2b7ef7a · 丘啊哈/代码空间 - Gitee.com

LZ77

• 在文件中，发现局部范围内，有些语句可能重复出现，对于重复出现的词语能否想办法让其变短，如果可以，则能够起到压缩的目的:
• 对于文件中重复出现的词语，可以使用<长度，距离>对方式来进行替换
  • 长度:重复文件所占的字节
  • 距离:后文中重复出现词语首字节与前文中重复的词语首字节位置差

• LZ77原理:

  • 将重复出现的内容替换成更短的<长度，距离>对

    • 

  • 没有较长语句的重复,但是在字节层面有一些重复
    • 

• 代码实现前的一些问题：

  • 1.LZ77压缩整个就在一个窗口中进行的，就是从先行缓冲区中的字符串在查找缓冲区中找重复，刚开始，查找缓冲区中字符个数为0，随着压缩的不断进行，查找缓冲区在增大，先行缓冲区在缩小

    • 

  • 2.在前文中找到多少个重复的字符才需要替换?
    • gzip中的LZ77<长度，距离>对总共占3个字节长度:
      • 一个字节表示一表示范围:0~255
      • 距离:使用2个字节表示
    • 为什么要将长度设置为1个字节?
      • 因为绝大多数情况下，在查找缓冲区中找到的重复字符串的长度都不会超过255，如果将长度设置为2个字节或者更多个字节，高位都使用不上，而且会让<长度，距离>对变大，影响压缩结果。如果真的出现匹配长度超过255的情况，将其替换多多个长度距离对即可。
    • 长度设置为2个字节:0~65535，往start左侧可以查找的最远的距离65535，如果超过这个数值，查找的时间成本将会增加
  • 3.LZ77的 匹配长度：
    • MIN_MATHC:最小的匹配长度3。为什么?
    • MAX_MATCH:最大的匹配长度255+3 = 258
      • MAX_MATCH为258的原因：将匹配字符串使用<长度，距离>对替换时，长度统一减去3，然后再解压缩的时候遇到<长度，距离>，给长度统一再加上3

• 哈希表实现：

  • 使用哈希“桶”保存每三个相邻字符构成的字符串中首字符的窗口索引。
  • 1. 哈希桶的大小
    • 三个字符总共可以组成2^24种取值，桶的个数需要2^24个，而索引大小占2个字节，总共桶占32M字节，是一个非常大的开销。随着窗口的移动，表中的数据会不断过时，维护这么大的表，会降低程序运行的效率。LZ77作者认为哈希桶的个数设置为：2^15 (即32K)。
  • 2. 哈希表的结构
    • 原本需要2^24个哈希桶，现在减少为2^15个，必然会产生哈希冲突。哈希表由一整块连续的内存构成，分为两个部分，每部分大小为一个WSIZE(32K)

    • 

    • head数组用来保存三个字符串首字符的索引位置，head的索引为三个字符通过哈希函数计算的哈希值。
    • prev是来解决哈希冲突的
  • 3. 哈希函数
    • 此处的哈希函数设计如下：
      • A(4,5) + A(6,7,8) ^ B(1,2,3) + B(4,5) + B(6,7,8) ^ C(1,2,3) + C(4,5,6,7,8)
      • 说明：
        • A 指 3 个字节中的第 1 个字节，B 指第 2 个字节，C 指第 3 个字节，
        • A(4,5) 指第一个字节的第 4,5 位二进制码，“^”是二进制位的异或操作， “+”是“连接”而不是“加”，“^”优先于“+”
        • 这样使 3 个字节都尽量“参与”到最后的结果中来，而且每个结果值 h 都等于 ((前1个h << 5) ^ c)取右 15位
  • 4. 哈希表构建(插入字符串)

    • 

• LZ77处理大文件：

  • 数据不能一次性读到内存，此时窗口就发挥了显著作用
  • lookahead:标记先行缓冲区中剩余的数据，即:_pWin中待压缩的数据个数
  • 当先行缓冲区中的数据小于MIN_LOOKAHEAD时，就需要往窗口中补充数据，MIN LOOKAHEAD = MIN_MATCH + MAX_MATCH + 1
    • MIN LOOKAHEAD = MIN_MATCH + MAX_MATCH + 1的目的:让匹配能够达到最优
      • 1.至少要达到一次的最长匹配MAX_MATCH
      • 2.如果匹配长度达到MAX_MATCH， 匹配完成之后需要将匹配的字符三个三个一组往哈希表中插入-->MIN_MATCH+1
  • 除了MIN_LOOKAHEAD，还有一个限制条件，MAX_DIST，最远匹配距离，且MIN_LOOKAHEAD + MAX_DIST = WSIZE(32K)
    • 设置MAX_DIST的原因：
      • 在前文中找重复匹配的时候，不需要找到窗口的最左侧，因为当start进入到右窗之后,_pWin（窗口）的起始位置距离start已经非常远了，太远了就不用找了，因为重复具有局部原理性--理论找的越远找到匹配更高，但是按照局部原理性思想，距离越远，重复性不一定好，而且找的越远耗费的时间越长，为了那么一点点的压缩率让压缩的效率变得非常低划不来
  • FillWindow():往右窗中填充32k的数据进去
    • 1.将右窗中的所有数据搬移到左窗中
    • 2.更新哈希表

      • 

    • 3.往左窗中补充32k的数据
  • 往哈希表中插入时存在的问题:当start在_pWin中走到右窗口的时候，start现在已经大于32*1024，直接将三个字节往哈希表中插入的时候，传递的三个字节首字节的位置岂不是越界了吗?
    • 哈希掩码：当start进入右窗之后，直接将三个字节一组往哈:start就越界了，因此需要通过HASH_MASK保证其不越界,用pos & HASH_MASK
    • 但这又引入了新的问题，pos & HASH_MASK之后的位置可能已经有值，导致某条链遭到破坏，形成环，从而导致在找最长匹配时陷入死循环，因此在找最长匹配的代码中，增加一个限制条件，匹配趟数的阈值，当匹配的趟数超过这阈值时，无论有没有找到最长匹配，都让其结束循环。

• LZ77压缩

  • 1. 打开带压缩的文件(注意：必须按照二进制格式打开，因为用户进行压缩的文件不确定
  • 2. 获取文件大小，如果文件大小小于3个字节，则不进行压缩
  • 3. 读取一个窗口的数据，即64K
  • 4. 用前两个字符计算第一个字符与其后两个字符构成字符串哈希地址的一部分，因为哈希地址是通过三个字节算出来的，先用前两个字节算出一部分，在压缩时，再结合第三个字节算出第一个字符串完整的哈希地址。
  • 5. 循环开始压缩
    • 计算哈希地址，将该字符串首字符在窗口中的位置插入到哈希桶中，并返回该桶的状态matchHead
    • 根据matchHead检测是否找到匹配
      • 如果matchHead等于0，未找到匹配，表示该三个字符在前文中没有出现过，将该当前字符作为源字符写到压缩文件中
      • 如果matchHead不等于0，表示找到匹配，matchHead代表匹配链的首地址，从哈希桶matchHead位置开始找最长匹配，找到后用该(距离，长度对)替换该字符串写到压缩文件中，然后将该替换串三个字符一组添加到哈希表中。
  • 6. 如果窗口中的数据小于MIN_LOOKAHEAD时，将右窗口中数据搬移到左窗口，从文件中新读取一个窗口的数据放置到右窗，更新哈希表，继续压缩，直到压缩结束。

• 压缩格式数据保存

  • 压缩格式分两个文件保存：
    • 文件1保存比特标记位信息，0表示原字符，1表示长度距离对，最后用8个字节记录原文件大小。
    • 文件2保存压缩数据，包含原字符、长度和距离

• 解压缩

  • 1. 从文件1中读取标记，并对该标记进行分析
  • 2. 如果当前标记是0，表示原字符，从文件2中读取一个字节，直接写到解压缩之后的文件中
  • 3. 如果当前标记是1，表示遇到(距离，长度对)，从文件2中读取一个三个字节表示(距离，长度)对，然后从已解压缩过的结果中找出匹配长度
  • 4. 获取下一个标记，直到所有的标记解析完。

• 代码实现：

  • Lz77压缩 · 707b41d · 丘啊哈/代码空间 - Gitee.com

huffman压缩之后的结果为什么会变大：

• 1.需要在压缩文件中保存解压缩用到的信息，这些信息占用的空间可能也比较大----不是主要原因
• 2.主要原因:每个字节平均下来找到的编码超过8个比特位
• 3.为什么平均字节的编码超过8个比特位:不同字符的种类比较多，或者字符出现的次数比较均匀，导致huffman树非常大。
• 注意: huffman树对于文本文件压缩情况要比二进制格式文件要好
• 一个文件压缩之后，再次对压缩结果再来进行压缩，不是每次都会变小

LZ77压缩之后的结果为什么会变大

• 1.压缩结果中要保存用于区分原字符和长度距离对的标记为信息，而标记为的信息几乎占到源文件大小的1/8
• 2.文件中重复出现的字符串越多，LZ77压缩越理想，否则不太理想

GZIP: LZ77和Huffman的结合

• 1.LZ77的压缩结果可以使用huffman直接进行压缩吗?
  • 答案:是可以，但是压缩率不太好
  • 原因：
    • a.LZ77之后，有接近1/8的大小是标记为，如果直接采用Huffman的方式压缩LZ77的结果，标记为也会参与其中
    • b.LZ77之后，压缩文件的结果也会非常大，直接交给huffman压缩，可能会导致huffman树非常高，可能就会导致平均每个字节的编码超过8个比特位，就会导致压缩结果变大或者压缩结果不理想
• 2.直接采用范式huffman树----最终只需要保存编码位长，通过计算就可以获得哈夫曼编码
  • 原因：直接采用huffman树压缩，最终再压缩文件中需要保存解压缩的字节出现的频次信息，这些数据保存到压缩结果中也是非常大的，会硬性压缩率
• 3.LZ77的压缩后结果:源字符和长度距离对，以及标记信息（给标记为是为了区分:源字符和长度距离对）
  • 在LZ77压缩中，将长度设置1个字节的原因︰1个字节正好可以表示256种长度，而原字符也用1个字节表示，也是256中情况，在Gzip中，使用huffman对LZ77压缩结果再次压缩时，可以将原字符和长度放到一棵huffman树中进行压缩，此时就可以用2个字节来表示原字符和长度出现的情况，0到255表示原字符，257到512表示长度，中间的256有特殊意义，它用来表示块结束的标志。
  • 如果按照上述的方案来处理:将来huffman树将会非常大，最多会有513个叶子节点，这样会导致哈夫曼编码很长，最终会影响压缩结果
  • 解决方式：将距离进行分组，长度出现频次高的，划分的区间间隔就小，出现频次低的，划分的区间间隔就大,即小的值就用较少比特表示，大的值就用较多比特表示

    • 

    • 总共29个分组，因此原字符和长度分组最终对应的huffman树中最多情况下节点个数: 255+1+29 = 285
    • 例如：
      • 长度是40，压缩时，
      • 1.先要找到该长度属于那个分区:273分区
      • 2.从huffman树中找到273分区对应的编码----写入压缩文件中
      • 3.40属于该分组中的第40-35=5 : 而外的编码为101，再将其写入到压缩文件中
• 4.将距离放在另一颗huffman树中压缩
  • 距离的范围:0~32767
  • 假设LZ77压缩之后，有3万个距离，huffman树中将来有要3万个节点?
  • 在当是ZIP作者所处的年代，这棵树可能无法创建出来，主要是因为当是计算机内存都比较小
  • 因此需要对距离也进行分组

  • 

  • ZIP的作者:
  • 没有直接对距离进行压缩，而是对距离按照一定的方式来进行分组，每个组中元素的个数恰巧是2的幂次方，最终对每个分组中的code来进行压缩的。一共0~29=30个分组。
  • 例如：
    • 距离40:属于33~48的分组，将来压缩:10对应的编码---直接从huffman树中获取，再压缩额外的比特位:40-33=70111
• 5.在huffman压缩时，采用的范式huffffman树
  • 范式huffffman树是在huffffman树的基础之上，进行了一些强制性的约定，即：对于同一层节点中，所有的叶子节点都调整到左边，然后，对于同一层的叶子节点按照符号顺序从小到大调整 ，最后按照左0右1的方式分配编码。如下图：

  • 

  • 

  • 只要知道一个符号的编码位长就可以知道它在范式树上的位置。即：码表中只要保存每个符号的编码长度(即节点在树中的高度)即可
  • 通过构建的huffffman树，获取到编码位长，然后按编码位长为第一字段，符号为第二字段进行排序，就可以计算出huffffman编码
  • huffffman编码计算原则：
    • 相同位长的编码之间都相差1
    • 当前层编码=（上一层首字符编码+上一层字符个数）<<(层数差)
• 6.在真正进行压缩的时候，huffman并没有对LZ77完整的结果进行压缩，而是按块当进行压缩，当LZ77压缩结果大小为BUFF_SIZE（32k），再对其进行huffman压缩。
  • 1.写入判断块结束的标记：标记为1，说明不是最后一个块，标记为0，说明当前是最后一个块
  • 2.写入编码位长信息
  • 3.压缩数据
• 7.对LZ77压缩的结果按块进行压缩
  • 1.先清空前一个块中的LZ77压缩信息
  • 2.统计每个字节出现的次数
  • 3.创建huffman树
  • 4.获取编码位长
  • 5.生成huffman编码
  • 6.写解压缩时需要用到的信息----写编码位长
  • 7.压缩数据
• 代码实现
  • GZIP压缩 · d64cf85 · 丘啊哈/代码空间 - Gitee.com
  • SYZip.cpp · 丘啊哈/代码空间 - Gitee.com