C++ LZ77压缩
引言
lz77压缩是基于字典做数据压缩的方法，由以色列的两位大神Jacob Ziv与Abraham Lempel在1977年提出，LZ77算法名字就取于这两个人的名字，77表示是1977年提出
压缩过程
LZ77是通过字节来对文件进行压缩，就是将源文件中重复的字节通过（距离，长度）的方式来进行替换，进而达到压缩的目的。
例如源文件内容为：mnoabczxyuvwabc123456abczxydefgh
上述字符串中出现多次abc，就可以通过长度距离对的方式来进行压缩
并且我们发现，在上述过程中，只有遇见三个字符才会进行替换，这是为什么？？
首先，目前距离长度对占两个字节
一个字符重复？不替换，替换之后文件反而会变得更大
两个字符重复？不替换，替换之后和原文件大小一样，没必要
三个字符重复？替换，替换之后三个字符变成两个字节，达到压缩的目的
结论：大于等于三个字符重复就进行替换
如何找最长匹配
通过上面的压缩过程，我们可以发现这样几个问题：
如何查找最长匹配？
找到了怎么办？
未找到怎么办？
暴力求解
首先，我们最容易想到的就是暴力求解，因为暴力求解比较简单，只需从后往前开始匹配即可，意见更长的匹配串进行替换标记，但是暴力求解也太慢了，算法时间复杂度为O(N^2)，查找起来会非常的慢，如果是小文件还好，但要是大文件尼？？
哈希桶
另外一个容易想到的就是采用哈希表，计算出三个字符的哈希地址，进行插入，然后查询起来就会很快了，哈希结构有两种方式：闭散列、开散列。如果采用闭散列的方式，哈希函数该如何设计？如果存在冲突了怎么办？怎么查找最长匹配串，就会出现问题。于是我们采用开散列的方式：哈希桶。
如果采用普通的哈希桶，因为三个字符也就是三个字节，有2^24种情况，就需要16M的空间，而一个索引占两个字节，所以就需要32M的空间，浪费的空间太大了，维护起来也很麻烦，所以我们采用一种类似于哈希桶的方式：
通过上述这种方式，就可以很好的避免空间开销过大的问题，并且能够很快的找到匹配的字符串，这时候只需要判断哪个是最长的就行，效率也大大提高。
但如果说，找不到最长匹配怎么办？？
找不到实际上就是上述的第一步，因为第一步也是第一次插入。
但上述我们针对的都是小文件，如果是一个很大的文件？这时候，一个窗口中的数据是存放不下的，因为我们一个窗口的大小定义的是64k，我们把这个窗口分为两部分，各占32k，如果说数据不够了，就需要补充数据，但如何进行补充数据？？
如何区分源文件还是(距离，长度)
就如上面提到的，进行替换的时候，是没有 () 和 , 的，只有两个数据，那么如何和源文件中的内容加以区分尼？这时候，很容易想到用标记，0 和 1 (注意：这里的标记使用的是bit位)，0表示是源文件的内容，1 表示是(距离，长度)对，这样就能区分了，但这时我们就又需要一个压缩文件，用于存放标记，但在数据完全压缩结束，就可以吧标记文件的内容全部拷贝到压缩文件中，这时候再把标记文件删除即可
压缩文件中的内容
第一行：源文件后缀(换行)
接下来：压缩后的数据（也就是进行(距离，长度)对更换后的数据）
接下来：标记文件中的数据（事先保存在另一个文件中的）
接下来：压缩后数据的大小（用于解压缩后判断是否还需要拷贝数据）
接下来：标记数据的大小（用于将压缩数据和标记数据划分开，知道从哪里开始往后是标记数据）
解压缩
LZ77的解压缩过程会非常的简单
-
准备工作
a. 获取源文件大小
b. 获取标记数据 -
开始解压缩
读取一个字节，并及时获取一个标记，看当前标记的bit 为0还是1
a. 为0 ：当前字符为源字符，直接写入压缩文件
b. 为1：(距离，长度)从当前文件指针位置，找到匹配的起始位置，从该位置开始的长度个字符写 入压缩文件中重复上述过程
遇到的问题
- 一定要看清楚(距离，长度)中的距离占两个字节，而长度占一个字节，在解压缩文件的时候一定要读正确。。
- 第一次解压缩的时候，将源文件和解压缩后的文件对比，多出来了几个空格？？
那是因为没有及时更新缓冲区，比如，文件中的内容为 aaaaab ，这时候写入压缩文件中的数据为a14b，其中的14就是距离长度对 (1, 4)，如果进行解压缩