# GZip文件压缩

**Repository Path**: lianchen5/gzip-file-compression

## Basic Information

- **Project Name**: GZip文件压缩
- **Description**: 将huffman和lz77压缩算法结合进行高效文件压缩
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2023-08-07
- **Last Updated**: 2023-08-07

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# GZip文件压缩

#### 介绍
1. 利用变形的LZ77压缩算法，先快速的从重复语句层面进行快速压缩
2. 利用huffman编码方式再从字节上面进行压缩
将两种压缩算法结合起来，以达到高效快速的压缩

#### 软件架构
1. huffman文件压缩
1.1.压缩原理：使用文件中字符出现的次数构造Huffman树，生成Huffman编码，使用Huffman编码对源文件进行压缩
1.2huffman树: 从二叉树的根结点到二叉树中所有叶结点的路径长度与相应权值的乘积之和为该二叉树的带权路径长度WPL。
1.3. huffman树构建
   (1). 由给定的n个权值{ w1, w2, w3, … , wn}构造n棵只有根节点的二叉树森林F={T1, T2 , T3, … ,Tn},每棵二
叉树Ti只有一个带权值wi的根节点，左右孩子均为空。
   (2). 重复以下步骤，直到F中只剩下一棵树为止
        在F中选取两棵根节点权值最小的二叉树，作为左右子树构造一棵新的二叉树,新二叉树根节点的权值为其左右子树根节点的权值之和
        在F中删除这两棵二叉树
        把新的二叉树加入到F中
1.4. 压缩过程
        (1). 打开被压缩文件，获取文件中每个字符串出现的总次数。
        (2). 以每个字符出现的总次数为权值构建huffman树。
        (3). 通过huffman树获取每个字符的huffman编码。
        (4). 读取源文件，对源文件中的每个字符使用获取的huffman编码进行改写，将改写结果写到压缩文件中，直到文件结束。
1.5. 压缩文件的格式
        假设按照上述操作已经对源文件压缩完毕，怎么解压缩？解压缩之后文件的后缀怎么与源文件保持一致？因此：压缩文件中除了保存压缩数据外，还必须保存解压缩所需的信息。压缩文件格式
        ![输入图片说明](GO6V7X4%7DIW%7B889@MD$Z5D7Q.png)
1.6. 解压缩过程
        (1). 从压缩文件中获取源文件的后缀
        (2). 从压缩文件中获取字符次数的总行数
        (3). 获取每个字符出现的次数
        (4). 重建huffman树
2.LZ77压缩
2.1. LZ77原理
    LZ77是基于字节的通用压缩算法，它的原理就是将源文件中的重复字节(即在前文中出现的重复字节)使用(offset，length，nextchar)的三元组进行替换
2.2.压缩格式数据保存
        压缩格式分三个文件保存：
        (1). 文件1保存比特标记位信息，用8个字节表示标记为长度，后面紧跟标记位
        (2). 文件2保存原字符和长度
        (3). 文件3保存所有的距离
2.3.压缩过程
        （1）打开待压缩的文件（注意：必须按照二进制的格式打开，因为用户进行压缩的文件不确定）
        （2）获取文件的大小，如果文件大小小于3个字节，则不进行压缩
        （3）读取一个窗口的数据，即64K
        （4）用前两个字符计算第一个字符与后两个字符构成字符串哈希地址的一部分，因为哈希地址是通过3个字节计算出来的，先用前两个字节算出一部分，再结合第三个字节算出第一个字符串完整的哈希地址。
        （5）循环开始压缩
            计算哈希地址，将该字符串首地址在窗口中的位置插入到哈希桶中，并返回该桶的状态matchHead
            根据matchHead检测是否找到匹配
            如果matchHead等于0，未找到匹配，表示该三个字符在前文中没有出现过，将该字符作为源字符写到压缩文件中
            如果matchHead不等于0，表示找到匹配，matchHead代表匹配链的首地址，从哈系统matchHead位置开始找最长匹配，找到后用该（距离，长度对）替换该字符串写到压缩文件中，然后将该替换串三个字符一组添加到哈希表中
         (6)如果窗口中的数据小于MIN_LOOKAHEAD时，将右窗口中数据搬移到左窗口，从文件中重新读取一个窗口的数据放到右窗，更新哈希表，继续压缩，直到压缩结束。
2.4.解压缩过程
        (1). 从文件1中读取标记，并对该标记进行分析
        (2). 如果当前标记是0，表示原字符，从文件2中读取一个字节，直接写到解压缩之后的文件中
        (3). 如果当前标记是1，表示遇到(距离，长度对)，从文件3中读取一个两个字节表示距离，从文件1中读取一个字节表示长度，构建(距离，长度)对，然后从解压缩过的结果中找出匹配长度
        (4). 获取下一个标记，直到所有的标记解析完。
3.GZIP压缩算法
3.1.原理:GZIP压缩就是LZ77压缩和Huffman压缩的结合，但并不是直接将LZ77压缩的结果使用Huffman再压缩一次
        原因:LZ77的输出结果中包含：原字符、长度距离对以及标记信息,标记信息也参加huffman压缩,因次直接采用huffman树对LZ77的结果进行压缩，会对最终的压缩结果产生很大的影响。
        由于LZ77压缩结果中包含原字符、长度以及距离对，而原字符和长度都是当个字节的，距离占两个字节，因此：GZIP将原字符和长度采用同一棵huffman树压缩，距离采用另一棵huffman树单独压缩。
3.2.原字符和长度的压缩
        原字符表示在LZ77中未匹配的字符，长度表示重复字符串的个数，都占了一个字节，因此GZIP将其压缩合二为一了，即对于原字符和距离采用同一棵huffman树进行处理。原字符的范围是[0, 255]，距离是[3, 258](注意：实际存储时候距离减去了个3，即存储的也是[0,255])，那如何区分原字符和长度呢？
        GZIP用整数0~255表示原字符，256表示结束标志，即解码以后是256表示解码结束，从257开始表示距离，比如：257表示重复3个字符，258重复4个字符，但GZIP并没有一直这么一一对应，而是采用了和distance类似的方式进行分区，将长度划分成了29个区间，如下图：
![输入图片说明](BMQWT8V%25IVOU6%60@UH0(XCKK.png)
        原字符和长度的huffman编码的输入元素一共有286个，当解码器接收到一个比特流的时候，首先可以按照literal/length这个码表来解码，如果解出来是0-255，就表示原字符，如果是256，那就表示块结束，如果是257-285之间，则表示length，把后面扩展比特加上形成length后，后面的比特流肯定就表示distance，因此，实际上通过一个Huffman码表，对各类情况进行了统一，而不是通过加一个什么标志来区分到底是literal还是重复字符串。
3.3.压缩流程
        a.在LZ77中不是将找到的字符和长度距离对直接写入源文件，而是使用数组保存（源字符和长度保留在一个数组，距离保留在一个数组，标记位保存在一个数组中），以待进一步压缩
        b.当保存字符和长度的大小达到设定的块大小时对文件进行压缩
        压缩步骤：
         (1）统计字符出现的次数
        （2）构建Huffman树
        （3）获取编码位长：每个叶子节点的高度
        （4）生成Huffman编码：按照编码位长为第一字段，然后以字节大小为第二字段进行排序
        （5）写解压缩时需要用到的信息及编码位长
        （6）压缩
3.4. LZ77与huffman结合注意
        (1). LZ77压缩结果可以直接统计出字符出现次数，然后直接用来创建huffman树
        (2). 不是等LZ77全部压缩完成之后才进行huffman压缩，而是分块来进行压缩的，因为交给huffman树的数据不是非常大的情况下，字节的种类越少，生成的huffman编码越短，最终压缩的效果越好。
        (3). huffman压缩LZ77的结果时，采用了静态编码、动态编码和不压缩总共三种方式，即：静态编码压缩效果更好，则采用静态编码进行压缩，动态编码压缩效果更好则采用动态编码进行压缩，如果不论采用静态还是动态编码都会使文件压缩结果变大，则采用直接存储即不压缩
        (4). huffman压缩完LZ77之后，需要保存码字长度用以解压缩，Gzip采用了游程编码对码字长度再次进行了压缩，可以让压缩效率进一步提升
        (5). huffman树的高度不能超过15层,否则树会非常大，因此当huffman树的高度超过15时，需要对树中的部分节点进行合并