引言
因为哈弗曼编码对于大文件的压缩有很大的局限性 且压缩比十分有限 所以决定根据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