基于小波树的后缀数组压缩算法

摘要

后缀数组是一种简单的、功能强大的数据结构,在全文索引设计、数据压缩算法、生物信息学等领域中都有着广泛的应用。但是,后缀数组需要庞大的空间进行存储,因此研究后缀数组的压缩算法有着重大的意义。
　　本文提出基于小波树的后缀数组压缩算法,对后缀数组的占有空间进行了有效的压缩。在研究压缩后缀数组(CSA)的基础上,分析CSA的建立过程,对CSA进行了局部优化。结合后缀数组上的后向搜索算法以及CSA数据结构特点,探究后缀数组的压缩算法应具备的特性,据此特性提出问题转化,并验证了利用小波树压缩后缀数组的可行性。详细设计了基于小波树的后缀数组压缩算法,降低了后缀数组所需的存储空间。在两种不同树形的小波树编码方式上,分析算法能获得的压缩比。进一步提出利用二进制压缩编码对小波树进行压缩,使算法达到更高的压缩比。
　　经过理论及实验分析得出,采用Huffma n形的小波树对后缀数组进行压缩编码,进一步采用Run-Length?编码对小波树进压缩,能够在合理的时间内完成后缀数组的压缩编码过程,并取得较好的压缩比。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1. 1 研究背景

1. 2 国内外研究现状

1. 3 本文主要工作

第二章 相关知识介绍

2. 1 后缀数组

2. 2 小波树

2.3 经验熵及rank/select

2. 4 本章小结

第三章 压缩后缀数组及其分析与改进

3. 1 压缩后缀数组

3.2 CSA的局部改进

3. 3 后缀数组上的压缩算法可行性研究

3. 4 本章小结

第四章 基于小波树的后缀数组压缩算法

4. 1 基于小波树的后缀数组压缩算法的可行性分析

4. 2 基于小波树的后缀数组压缩算法的设计

4. 3 编码结果的进一步处理

4. 4 本章小结

第五章 实验结果及分析

5. 1 实验的软硬件环境

5. 2 实验数据来源及内容

5. 3 实验结果及分析

第六章 总结与展望

致谢

参考文献