基于后缀数组的近似字符串匹配

摘要

字符串匹配问题是计算机科学研究中最基础的问题之一。早期的研究多集中于精确字符串匹配领域，就精确字符串匹配提出了许多单模式和多模式匹配算法。然而在信息检索、模式识别和计算生物学等一些实际应用中有时候更需要查找的是近似匹配字符串。因此研究高效的近似字符串匹配算法具有重要的理论价值和实际意义。
　　本文首先介绍了近似字符串匹配算法的研究现状和近似字符串的相关理论和主要研究方法—动态规划、自动机、位并行、过滤等技术。结合后缀数组这一索引结构，本文提出了基于后缀数组的近似字符串匹配算法，即IS-DP算法。算法使用后缀数组加快在动态规划矩阵上的迭代速度，从而达到O(kn)的时间复杂度和空间复杂度。用后缀数组构造算法可以预先排序文本串后缀，求解后缀数组中相邻后缀的最长公共前缀，从而可以在O(1)时间内计算出任意两个后缀串的最长共有前缀长度。本文算法是对原有的基于动态规划的近似字符串匹配算法的改进，通过加速矩阵对角线上扩展的方式降低了构造动态规划矩阵的时间消耗，进而在O(kn)时间内查找出文本中所有的近似匹配字符串，与一些在后缀树上查找近似字符串匹配的算法相比较，本文算法采用后缀数组结构可以节省约5n的存储空间。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究目的及意义

1.2 字符串匹配研究现状

1.3 本文的主要工作

第二章 近似字符串匹配算法概述

2.1 串匹配的定义

2.2 近似串匹配算法概述

2.3 本章小结

第三章 加强的后缀数组

3.1 后缀数组相关定义

3.2 后缀数组构造算法

3.3 后缀数组构造算法性能比较

3.4 lcp 数组

3.5 本章小结

第四章 基于后缀数组的近似字符串匹配

4.1 lcp 数组预处理与区域最小值查询 RMQ

4.2 用加强的后缀数组查找近似匹配串算法

4.3 算法复杂度分析

4.4 实验结果及分析

第五章 总结与展望

5.1 论文总结

5.2 研究前景与展望

致谢

参考文献