基于后缀树和后缀数组的带有通配符多模式匹配研究

发布时间：2023-03-26 21:09

　　模式匹配问题在大数据时代下的信息检索、文本挖掘、网络安全以及生物信息学等很多领域都具有重要的应用价值,尤其是带有通配符的多模式近似匹配,相比正则表达式、单模式匹配和精确模式匹配,可以解决更加复杂的模式匹配问题,如从海量异构数据的碎片化知识中提取有价值的信息等。因此,根据带有通配符的模式特性,借助后缀树、后缀数组等高效的数据结构及其相应特性,对带有通配符的多模式近似匹配问题研究具有重要的研究意义和应用价值。目前对于带有通配符的模式匹配多是针对单模式匹配,而对于多模式匹配的研究更多的是针对精确匹配,对于带有通配符的多模式近似匹配问题的研究相对较少。而后缀树、后缀数组在精确字符串匹配中非常高效,常用于查找字符串中的频繁子串、最长重复子串、最长公共前缀及回文串等问题,而在近似匹配中多是理论分析,缺少实验分析及论证。因此,采用后缀树、后缀数组的方法进行带有通配符的多模式近似匹配研究具有重要的研究意义。本文在对国内外有关带有通配符的模式匹配、多模式近似匹配、后缀树和后缀数组在近似匹配中的理论研究以及其相关数据结构特性,进行分析总结的基础上,提出了基于后缀树和后缀数组的新算法,用于解决带有通配符的多...

【文章页数】：112 页

【学位级别】：博士

【文章目录】：
致谢
摘要
abstract
第一章 绪论
    1.1 课题背景及研究意义
    1.2 国内外研究现状
        1.2.1 多模式匹配研究现状
        1.2.2 带有通配符的模式匹配问题研究现状
    1.3 研究内容和组织结构
        1.3.1 主要研究内容
        1.3.2 内容组织
    1.4 本章小结
第二章 相关研究工作
    2.1 模式匹配
        2.1.1 单模式匹配
        2.1.2 多模式匹配
        2.1.3 带有通配符的模式匹配
    2.2 后缀树
        2.2.1 字典树
        2.2.2 后缀树
        2.2.3 后缀树特性
    2.3 后缀数组
        2.3.1 后缀数组
        2.3.2 后缀数组特性
    2.4 本章小结
第三章 基于后缀树的带有通配符的单模式匹配
    3.1 引言
    3.2 问题定义
    3.3 算法设计与分析
        3.3.1 算法描述
        3.3.2 算法复杂度分析
    3.4 实验结果及分析
        3.4.1 算法的完备性
        3.4.2 算法的时间性能
        3.4.3 算法的其他性能
    3.5 本章小结
第四章 基于后缀树的带有通配符的多模式匹配
    4.1 引言
    4.2 问题定义
    4.3 算法设计与分析
        4.3.1 算法描述
        4.3.2 算法复杂度分析
    4.4 实验结果及分析
        4.4.1 实验环境及数据集
        4.4.2 实验结果
    4.5 本章小结
第五章 基于后缀数组的带有通配符的多模式匹配
    5.1 引言
    5.2 问题定义
    5.3 算法设计与分析
        5.3.1 算法描述
        5.3.2 算法复杂度分析
    5.4 实验结果及分析
        5.4.1 基于DNA序列的实验结果及分析
        5.4.2 基于蛋白质序列的实验结果及分析
    5.5 本章小结
第六章 总结与展望
    6.1 主要研究工作
    6.2 下一步工作
参考文献
攻读博士学位期间的学术活动及成果情况



本文编号：3771737