论文部分内容阅读
字符串匹配问题是在给定符号序列（称为文本）中按照一定的匹配条件，搜索给定符号序列或给定符号序列集合中元素（称为模式）出现位置的搜索问题。该问题是计算机科学的基础问题之一，被广泛的应用于各种涉及文字和符号处理的领域中，是网络安全、信息检索、计算生物学等重要领域的关键问题。随着网络安全问题凸显、海量信息检索、计算生物学高速发展，现有串匹配算法已经无法满足应用对匹配性能的需要，急需性能更高的串匹配算法出现。本文对串匹配领域中的精确单模式匹配和精确多模式匹配子领域进行研究。通过对现有算法进行改进，提出了具有更高性能的串匹配算法。在精确单模式匹配领域，本文对Q-Hash、EBOM、TVSBS算法进行了改进，先后提出了SQ-Hash、TQ-Hash、SEBOM、BOMq、BOMq’、SufOMq、Suf_SEBOM、TVSBSq、TVSBSqA、FQ-Hash共十个（系列）算法。实验表明在精确单模式匹配领域，64.3%的匹配条件下，本文所提出的算法性能高于已知算法。在精确多模式匹配领域，本文对AAC、Set BOM算法进行改进，先后提出了AACS、AACF、Set EBOM、Set SEBOM、Set BOMq、Set SufOMq共六个（系列）算法。本文所述算法在多数条件下，性能高于经典算法。在时间复杂度分析领域，本文对Q-Hash系列算法进行分析，证明Q-Hash系列算法能达到精确单模式串匹配算法平均时间复杂度的下界，并基于此结论，本文证明了Wu-Manber算法在选择合适的Hash函数时，能达到多模式匹配平均时间复杂度的下界。本文还提出了后缀匹配类研究中的一种通用方法，图例法。图例法简单清晰，可达到按后缀匹配的最大跳跃距离，并可以直接转换为算法的预处理过程，为今后后缀匹配类算法的研究提供了方便。同时，本文还提出了与AAC自动机一致的Set DFA自动机，该自动机构建时，时间复杂度和AAC一致，但无需借助失败函数，简单易懂，操作更少，而且可以方便的人工实现，Set DFA自动机的构建时间只有AAC自动机构建时间的50%左右。