Skip to content
This repository has been archived by the owner on Sep 10, 2021. It is now read-only.
/ nxzip Public archive

The final project in my undergraduate life, a data compressor based on BWT, MTF and Huffman-coding.

License

Notifications You must be signed in to change notification settings

zhang-stephen/nxzip

Repository files navigation

Preface


这是我本科阶段最后一个成熟项目,也是我的毕业设计:

设计一款基于BWT的数据压缩程序

思考

目前可供参考的项目是bzip2,但是bzip2并无算法相关文档,仅提供API手册,可供参考之处并不多

bzip2的压缩比大概在80%-85%,但是由于使用了BWT算法,处理速度要比gzip(LZ77/LZ78)等慢一些,此外,压缩时占用的内存大概是解压时的三到七倍

BWT算法唯一的难点在于内存,随着原数组的增长,原理算法占用的内存以指数形式增长,而且遍历原理算法的缓存矩阵的时间复杂度在最好的情况下应该是O($n^3$),因此主要针对BWT算法的时间复杂度和空间复杂度进行优化

文件

  • 后缀名暂定为zipx

工程

language Compiler Project Management Version Control Project Name
c++17(gnu++17) GCC v8.2.0 cmake 3.13.2 github nxzip

任务列表

  • 实现基本的BWT算法
  • 实现基本的IBWT算法
  • 使用quick sort替换bubble sort(注:实际使用merge sort)
  • 实现基本的MTF和IMTF算法
  • 实现Huffman Coding算法
  • 实现范式Huffman Coding算法
  • 实现仅利用STL的文件读写和其他file IO
  • 定义压缩文件的结构
  • 实现软件的CRC-32C校验算法
  • 实现基于SSE4.2指令集的CRC-32C算法

其他

2019-06-09 Freeze This Project 毕业设计业已完成,虽然程序仍有些许错误,但是眼下亦无时间修复订正,留待日后解决 算法的世界是很奇妙的,希望日后仍有机会遨游其中

已知问题:

  1. BWT算法的正变换和逆变换无法对应,导致解压时CRC32校验失败(Fatal Error)
  2. 文件结构中一些冗余成分未能删除

created by vscode, wrote with markdown(MPE), 2019.02.04

About

The final project in my undergraduate life, a data compressor based on BWT, MTF and Huffman-coding.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published