简单实现LZ77压缩算法

引言

因为哈弗曼编码对于大文件的压缩有很大的局限性 且压缩比十分有限 所以决定根据LZ77算法写一个简单的压缩库

组成

因为时间较为紧张 目前完成了最基础的ZIP算法的编写 即根据LZ77算法(滑动窗口压缩)先对压缩文件得到一个数据三元组 然后针对数字出现的频率再进行哈弗曼算法 为了更好的压缩比 我并没有先参考的资料中的方法 采用了建三棵哈弗曼树的做法

效率

对于一般的文件 压缩比可以达到百分之30到40
对于重复性较高的文件 压缩比可以达到百分之10到20 甚至更低
且克服了哈弗曼编码无法压缩大文件的缺点

不足

在计算数据三元组的时候使用了一个O(n2)的朴素匹配 使得效率比预想的更为不尽人意 改进之处可以参考LZ4算法 在匹配时使用哈希降低时间复杂度
因为是压缩库 本来想再顺便写一个打包工具 但是时间临近期末 有点紧张 遂打算假期补上

使用

整体使用C++17编写 关键部分提供注释
只需要把本文件夹放在您的项目中 然后包含"LZL-zip.h"即可

//默认压缩名称为　ｘｘｘ.LZL-zip
g++ -std=c++17 test.cpp -o test

这是源码的地址: ​​https://github.com/Super-long/LZ-zip​​