一种外存后缀数组构造算法的工程实现及性能评估

发布时间：2017-06-02 14:22

  本文关键词：一种外存后缀数组构造算法的工程实现及性能评估，由笔耕文化传播整理发布。

【摘要】：后缀数组最初是作为后缀树的一种替代被提出的，与后缀树相比，存储后缀数组所需的空间更少，应用范围更广。在后缀数组被提出后，后缀数组作为一种重要的索引数据结构，被广泛的应用于生物信息学、全文索引、字符串匹配、频繁字符串挖掘以及顺序分析和聚类分析等领域。到目前为止，国内外关于后缀数组构造算法的研究已经取得了丰硕的成果。但随着信息技术的发展，在许多领域，需要处理的数据集日益增长。当利用原有后缀数组内存构造算法为一个非常大的数据集构建后缀数组时，所需的内存空间远远超出了一般商用电脑的内存限制。这时，后缀数组内存构造算法不再适用，极大的限制了后缀数组的应用范围。 在本文中，我们探讨了一种基于SA-IS算法的后缀数组外存构造算法，对算法的主要思想进行了深入分析，从理论上验证了算法的正确性和可行性。在深入理解算法的基础上，我们采用面向过程的程序设计方法对算法加以实现。在具体实现过程中，我们对原算法中的PCI和name两种中间辅助数据结构进行精简，通过采用分块的策略将原算法中所需的外存排序过程转化为多次的内存基数排序过程，保证了算法的执行效率和I/O性能。同时，通过实验对比分析，对算法的性能进行评估，最终的实验结果显示，，该算法是线性的并且具有与EM-SA-DS算法相近的性能。
【关键词】：后缀数组 外存 构造 SA-IS
【学位授予单位】：中山大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP333
【目录】：

• 摘要3-4
• Abstract4-7
• 第一章 绪论7-12
• 1.1 研究背景与意义7-8
• 1.2 后缀数组构造算法的研究现状8-10
• 1.3 研究目标与主要工作10-11
• 1.4 论文结构11-12
• 第二章 几种主流后缀数组构造算法介绍12-24
• 2.1 相关名词及符号介绍12-13
• 2.2 SA-IS 算法13-17
• 2.3 EM-SA-DS 算法17-24
• 第三章 一种基于 SA-IS 的后缀数组外存构造算法24-36
• 3.1 相关符号、概念及定理24-25
• 3.2 算法原理分析25-29
• 3.3 实例验证29-34
• 3.4 复杂度分析34-36
• 第四章 算法工程实现36-59
• 4.1 算法实现总体框架36-37
• 4.2 数据设计37-40
• 4.3 流程设计40-45
• 4.4 主要函数具体实现45-59
• 第五章 实验设计与分析59-66
• 5.1 实验方案设计59-60
• 5.2 实验数据收集与分析60-66
• 第六章 总结与展望66-68
• 6.1 论文总结66-67
• 6.2 前景与展望67-68
• 参考文献68-70
• 致谢70

【参考文献】

中国期刊全文数据库 前1条

1 王红;内存抖动问题分析及解决对策[J];潍坊高等专科学校学报;2000年01期

  本文关键词：一种外存后缀数组构造算法的工程实现及性能评估，由笔耕文化传播整理发布。

本文编号：415594