LZ77实现文件压缩
源代码获取：
https://github.com/akh5/C-/tree/master/LZ77
LZ77简介
LZ77是一种基于字典的算法，它将长字符串（也称为短语）编码成短小的标记，用小标记代替字典中的短语，从而达到压缩的目的。也就是说，它通过用小的标记来代替数据中多次重复出现的长串方法来压缩数据。其处理的符号不一定是文本字符，可以是任意大小的符号。
LZ77原理介绍
LZ77是基于字节的通用压缩算法，它的原理就是将源文件中的重复字节(即在前文中出现的重复字节)使用(offset，length）的元组进行替换。通过在前文中搜索，匹配到相同字符串时，记录下到匹配位置的距离，和其匹配的长度，来代替当前字符串，可以节省很多空间。
一般情况下，匹配的字符串超过3个字符以上时才进行替换，3个一下字符有时反而会使压缩文件变大
压缩
压缩时以一个缓冲区，不断向右滑动的方式来扫描前文
通过缓冲区的方式，查找缓冲区已经扫描好的字符串，而向前缓冲区中的时需要向前查找匹配内容的区域，所以查找到的距离长度对都是从查找缓冲区开始匹配的，而不是从文件最开始的部分开始进行匹配。
压缩开始时，有一个当前位置的指针，从当前位置与下一个位置的字符配合在查找缓冲区中查找相应字符串，如果找到匹配，则继续向下查找，直到找到最长的匹配字符串，如果没找到，则照原样输出该字符
标记长度距离对
为了识别长度距离对和原字符，需要用标记来来区分，用0来标记原字符，1来标记距离长度对，所以在进行压缩时，需要打开两个文件，分别写入，一个文件写入压缩数据，一个文件写标记信息
代码详解
构建哈希表
哈希表的介绍参考：https://blog.csdn.net/MPF1230/article/details/104731895
构建的hash表时，分为pre和head两个区域
每当有新的冲突值时，会将上一个地址存入到pre的对应地址中，每当有新冲突时就会进行一次更新。
而查找时，只要找到0则代表结束。
common.h
此头文件，用来定义一些经常用到的常量
#pragma once
#pragma warning(disable:4996)
typedef unsigned char UCH;
typedef unsigned short USH;
typedef unsigned long long ULL;
const USH MIN_MAT = 3;
const USH MAX_MAT = 258;
const USH WSIZE = 32 * 1024;
UCH定义为1个字节，USH定义为2个字节，ULL定义位4个字节(32位下)
MIN_MAT为最小的匹配长度
MAX_MAT为最大的匹配长度
WSIZE为进行匹配时的窗口大小
hash_table.hpp
其中的插入哈希函数并解决哈希冲突
void Insert(USH &matchHead, UCH ch, USH pos, USH& hashAddr)
{
HashFunc(hashAddr, ch);
matchHead = _head[hashAddr];
_pre[pos&HASH_MASK] = _head[hashAddr];
_head[hashAddr] = pos;
}
- 先用哈希函数计算哈希地址，hashAddr为出参
- 得到当前地址的匹配头
- 将当前地址已有的数据放入pre中
- 将当前字符的位置放入到head区域中
LZ77.hpp
此文件中封装了一个类，类中包含了压缩和解压缩方法
压缩方法
- 读取待压缩文件，打开两个文件，一个写入压缩数据，一个写入标记
- 先在固定大小的窗口区域从前向后进行遍历，遍历的同时向哈希表中插入位置
- 寻找最长匹配，如果找到则则写入长度，和距离，并向标记文件中写入1，如果没找到，则写入原字符，并向标记文件写入0
- 当读取超过窗口大小时，清空窗口数据，继续向下进行
- 合并压缩数据和标记信息，标记信息写入到压缩数据末尾，并在最后写入标记的长度，从而区分标记信息的开头位置与压缩数据的末尾位置
解压方法
- 用两个文件句柄打开压缩文件，一个句柄读取压缩数据，一个句柄读取标记信息
- 从末尾获取标记信息的大小
- 打开一个文件写入解压缩数据，但也打开两个文件句柄，一个以wb打开，一个以rb打开，前者用来写入解压缩的数据，后者用来向前查找匹配字符串
- 标记信息为0时写入原子符，当读取到1时，用另一个指针向前查找
这里需要注意的时，每次写入的时候需要用fflush()刷新缓冲区，如果不刷新缓冲区的话，我们在找到长度距离对，并向前查找时，此时写入的数据还在缓冲区中，不在文件当中，所以rb文件句柄读到的数据也全是空