title: README.md
author: Adam-Xi
date: 2020-02-24
前言
文件压缩概念
数据压缩是指在不丢失有用信息的前提下，缩减数据量以减少存储空间，提高其传输、存储和处理效率，或按照一定的算法对数据进行重新组织，减少数据的冗余和存储的空间的一种技术方法
必要性
-
- 紧缩数据存储容量，减少存储空间
-
- 可以提高数据传输的速度，减少带宽占用量，提高通讯效率
-
- 对数据的一种加密保护，增强数据在传输过程中的安全性
文件压缩分类
- 有损压缩
有损压缩是利用了人类对图像或声波中的某些频率成分不敏感的特性，允许压缩过程中损失一定的息；虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像的影响缩小，却换来了大得多的压缩比，即指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解
- 无损压缩
对文件中数据按照特定的编码格式进行重新组织，压缩后的压缩文件可以被还原成与源文件完全相同的格式，不会影响文件内容，对于数码图像而言，不会使图像细节有任何损失,如接下来的GZIP算法就是无损压缩
GZIP压缩算法
GZIP压缩算法经历了两个阶段:
- 第一阶段，使用改进的LZ77压缩算法对上下文中的重复语句进行压缩
- 第二阶段，采用huffman编码思想对第一阶段压缩完成的数据进行字节上的压缩
从而实现对数据的高效压缩存储
LZ77算法
LZ77是基于字节的通用压缩算法，它的原理就是将源文件中的重复字节(即出现在前文中出现的重复字节)使用(offset, length, netchar)的三元组进行替换
但是GZIP中的LZ77压缩算法并没有采用三元组进行替换，因为nextchar是否出现在三元组中对压缩率的提升并不能起到什么作用，因此GZIP采用<长度,距离>对的方式进行替换
压缩思路
- LZ77压缩时，是在一个滑动窗口中进行的，初始状态下，先加载一个窗口的数据，随着压缩的进行，滑动窗口可以分为两部分：已扫描过的数据与待压缩数据（可称为查找缓冲区和先行缓冲区）
- 压缩开始后，每扫描到一个新字符后，用当前字符与其后的两个字符构成当前串，子查找缓冲区中查找，若找到匹配，使用长度距离对进行替换，否则将该字符写入压缩文件中
- 但是真正的压缩，是在一个比较大的窗口中进行的，窗口越大，找到匹配的可能性就越大，但不是无限大，因为会增加时间成本和空间成本。因此，GZIP决定窗口的大小取为64K，分为两部分，每部分为32K
- 先行缓冲区：即待压缩数据，每次都用先行缓冲区中的第一个字符与其后紧跟的两个在查找缓冲区中找匹配，随着压缩的不断进行，查找缓冲区不断增大，先行缓冲区不断缩小，当查找缓冲区增大到32K之后，就不增大了，随着先行缓冲区向右移动。如果先行缓冲区中的数据少于一个MIN_LOOKAHEAD时，将右窗口中的数据搬移到左窗口，给右窗口中重新补充32K的数据，继续压缩，直到压缩结束
- MIN_LOOKAHEAD为最大匹配长度+1，即待压缩区域至少有一个字节以及该字节的一个匹配长度
查找最小匹配（采用哈希桶的方式）：
- 利用哈希函数计算该字符与紧跟其后的两个字符构成字符串的哈希地址
- 将该字符串中首字符在窗口中的索引插入上述计算出哈希位置的哈希桶中，返回插入之前该桶的状态
- 根据上一步返回的状态监测是否找到匹配串：如果当前桶为空，说明未找到匹配；否则表示可能找到匹配，再定位到匹配串位置详细进行匹配即可
压缩流程
压缩
- 打开待压缩文件（二进制打开）
- 获取文件大小，如果文件大小小于3个字节，则不进行压缩
- 读取一个窗口的数据，即64K
- 用前两个字符计算第一个字符与其后两个字符后两个字符串哈希地址的一部分，因为 哈希地址是通过三个字节算出来的，先用前两个字节短处一部分，在压缩时，再结合第三个字节算出第一个字符串完整的哈希地址
- 循环开始压缩
- 计算哈希地址，将该字符串首字符在窗口中的位置插入到哈希桶中，并返回该桶的状态matchHead
- 根据matchHead检测是否找到匹配
- 如果matchHead等于0，未找到匹配，表示该三个字符在前文中没有出现过，将该当前字符作为源字符写到压缩文件中
- 如果matchHead不等于0，表示找到匹配，matchHead代表匹配链的首地址，从哈希桶matchHead位置开始找最长匹配，找到后用该<长度,距离>对替换该字符串写到压缩文件中，然后将该替换串三个字符一组添加到哈希表中
- 如果窗口中的数据小于MIN_LOOKAHEAD时，将右窗口中数据搬移到左窗口，从文件中新读取一个窗口的数据放置到右窗，更新哈希表，继续压缩，直到压缩结束
压缩数据保存格式
压缩数据分为两个文件保存
- 压缩数据，用以保存压缩后的数据或者<长度,距离>数据
- 标记信息，用以保存标记当前字节是源字符还是<长度,距离>
解压缩
- 从标记文件中读取标记，并对该标记进行分析
- 如果当前标记是0，表示源字符，从压缩数据文件中读取一个字节，直接写到解压缩之后的文件中
- 如果当前标记是1，表示遇到<长度,距离>，从压缩数据文件中先读取一个字节作为压缩的长度，再继续读取两个字节作为距离，然后从解压缩过的结果中找出匹配长度
- 获取下一个标记，直到所有的标记解析完
Huffman算法
在前面使用LZ77变形思想对源数据进行语句的重复压缩之后，语句层面的重复性已经解决，但并不代表压缩效果已经达到最大，字节层面可能也存在着大量重复
由此，GZIP算法中引入了Huffman的思想
压缩
- 在字节层面找待压缩文件中的重复字节，并统计各个字节重复的次数
- 根据重复字节及重复次数构建Huffman树
- 根据构建的Huffman树获取Huffman编码
- 利用Huffman编码对源文件进行压缩
- 对压缩文件格式进行记录(文件后缀，字符次数对的总行数、字符及字符出现的次数)
压缩文件格式
- 源文件的后缀
- 字符次数对的总行数
- 字符以及字符出现次数
- 压缩数据
解压缩
- 从压缩文件中获取源文件的后缀
- 获取字符的总行数
- 获取每个字符出现的次数
- 重建Huffman树
- 解压缩
- 从压缩文件中一个一个字节的获取压缩数据，每获取到一个字节的压缩数据，从根节点开始，按照该字节的二进制比特位信息遍历Huffman树，若该比特位是0，去当前节点的左孩子，否则取右孩子，直到遍历到叶子节点位置，该字符就被解析成功。
- 继续此过程，直到所有的数据解析完毕
GZIP算法性能测试
使用Beyond Compare4对文件压缩前后进行比较，格式、数据等完全一致
- 对.txt、.doc、.docx、.pdf等文档格式文件压缩效率区间为50%~98%，其中，.txt文件压缩效果最好，普遍为55%~80%
- 对.jgp、.png等图片格式文件压缩效率区间为80%~95%
- 对.mp3、.flac等音频格式文件压缩效率区间为75%~100%
- 对.avi、.flv等视频格式文件压缩效率为80%~100%
- 对.exe等的可执行程序格式文件压缩效率为85%~100%
经过简单的测试可以看出，GZIP算法对文档文件压缩效率较高，但是同时耗时较长
路遇问题及解决方法
- 压缩数据的格式需要进行统一，确保压缩和解压缩的一致性
- LZ77压缩需要约定将压缩数据、压缩标记信息、标记信息长度、压缩数据长度依次在LZ77压缩文件中进行排列
- Huffman压缩需要约定将源文件的后缀、字符次数对的总行数、字符次数对以怎样的格式排布在压缩文件中
- 对存在汉字文件的压缩
- 在编写代码时给简单测试用例中加入一个汉字时，发现程序会崩溃，利用变量监视窗口进行排查问题时，发现用来表示Huffman中权值的结构体中表示具体字符的变量定义为char类型，到用char变量表示汉字时为负值，所以用unsigned char进行代替，即可表示汉字
- 文件压缩和解压缩了一部分
- 由于使用C接口对文件的打开方式为"w"或"r"，会发现有时候程序莫名其妙的压缩和解压缩了一部分，针对这个头疼的问题，在确认了自己的处理逻辑没有问题后，在网上查了很多资料，无果，最后将压缩的文件用二进制的方式查看时发现了解压了一半的程序都终止在了FF，意识到文本文件是以FF结尾的，于是更改了文件的打开方式，以二进制文件读写打开，完美地解决了这个问题
- 保证解压缩后的正确性
- 对于有些文件比如结尾是以很多歌换行或者空格结束的，等等，许多奇奇怪怪的格式的文件，肉眼是无法看出来的，所以在网上找到了Beyond Commpare这款软件，尽管是收费的，但是一个月体验时间足够了！！！
- 使用LZ77算法解压缩时，由于是对之前解压缩过写入文件中的字符进行匹配，所以牵扯到IO缓冲区问题，所以在每次写入文件后，都需要刷新缓冲区。
- 在测试大文件的压缩时，对于动辄上百M的文件的压缩和解压缩是一个令人头疼的问题，因为过程太漫长了，有时候将近十几分钟的压缩周期不仅对开发人员（me）而且对机器都是一个煎熬，终究是因为Huffman算法的时间效率确实很低，导致程序运行时间过长，用户体验不是很好
- 在测试文件压缩前后大小时，发现对于很多的文件的压缩效率并不能使人满意，如上一版块算法性能测试所示，这是因为Huffman压缩算法本身带来的问题，它是根据源文件中同一字节重复出现的次数而设计的算法，若是源文件中并没有存在很多的重复字节，又或者源文件中存在很多重复一次两次的字节，导致还要耗费很大的空间来存储该字符次数对，得不偿失
- 在压缩前后文件大小比较时，发现并不是每次压缩压缩文件都比源文件小，对此的解释为：例如对存储着"ABBCCDD"的文件，压缩后首行存储文件的后缀，下面一行存储总行数，再下面几行存储字符次数对，形如"B:2"，再下面才是存储的数据，所以导致解压缩后的文件会比源文件大，以此类推，对于其他大的文件而言，同理
- 由于在代码中的文件打开方式为二进制读写打开，所以对于任意文件类型的文件，该程序都可以进行压缩解压缩
待改进
- 目前该算法的时间效率并不是很高，尤其Huffman算法时间复杂度很高，为此，后期需将当前仿写的Huffman算法换为GZIP原生的范式Huffman算法
- 后期可以学习duilib或Qt等的UI库，为该程序做一个界面，方便与用户进行交互