基于BWT和小波树的数据压缩算法

摘要

随着互联网领域以及其他新兴领域的迅猛发展，全世界每天产生的数据急剧增加。数据里面蕴含着非常有价值的信息，于是人们开始对这些数据进行分析与研究，挖掘自己感兴趣的信息。由于数据规模本身非常大，因此数据的存储是一项很大的挑战，需要耗费很大的磁带，磁盘资源；除此之外互联网上不同主机之间的数据通信量日趋增大，这占用较多的网络带宽资源，而且是很耗时的。因此对这些数据的压缩成为大数据处理的研究热点和解决大数据问题的必然趋势。
　　首先分析了基于后缀数组计算BWT的方法，BWT变换的性质，并且提出一种BWT逆变换时的LF修正算法；其次研究了01序列上各种rank/select数据结构的原理，空间大小，并从数学角度分析了小波树上内部节点01序列的层次化对各种rank/select数据结构空间大小的影响；最后基于BWT变换和小波树，我们提出一种数据压缩及解压缩算法的框架，并且给出了该算法并发化的一些思路。我们通过定义自己的压缩文件格式，最终高效地开发了一款数据压缩软件，wzip。
　　我们还通过实验测试了小波树树形，节点压缩方式，BWT变换块大小对wzip压缩率的影响。最终我们发现在BWT变换块大小固定的条件下，基于hu-tacker[10]编码的小波树并且内部节点采用run-length Gamma[11]的wzip压缩方案能够达到最好的压缩效果。通过将wzip和bzip2，gzip，rar，zip，7z，compress这些数据压缩软件在压缩率，压缩时间，解压时间方面的对比，我们发现wzip具有压缩率好，压缩及解压缩速度快的特点。此外wzip提供丰富的参数选项，以提供不同的压缩性能需求。我们的压缩软件wzip可从Github下载使用(https://github.com/goldbeef/wzip)。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1 研究背景及意义

1.2 研究现状

1.3 本文主要工作

第二章 预备知识

2.1 后缀数组

2.2 Burrows-Wheeler变换

2.3 后向搜索

2.4 小整数编码

2.5 01比特序列上的压缩

2.6 几种常见的字符集编码

第三章 简明数据结构设计与分析

3.1 简明数据结构

3.2 01序列的层次化分析

第四章 小波树的构造及其应用

4.1 小波树的构造

4.2小波树在文本索引上的应用

4.3小波树在数据压缩上的应用

第五章 基于BWT和小波树的数据压缩算法

5.1 数据压缩模型

5.2 压缩文件的格式

5.3 数据解压模型

5.4 压缩与解压的并发化

5.5 wzip手册

第六章 实验测试及结果分析

6.1 实验环境

6.2 标准数据源

6.3 相关压缩软件

6.4 压缩参数对wzip压缩率的影响

6.5 压缩/解压缩时间的对比

6.6 其它文件的压缩测试

第七章 总结与展望

参考文献

致谢

作者简介