一种时间复杂度最优的精确串匹配算法

现有的串匹配算法通常以模式长度作为滑动窗口大小.在窗口移动后,往往会丢弃掉一些已扫描正文的信息.提出了LDM(linear DAWG matching)串匹配算法,该算法将正文分为[n/m]个相互重叠、大小为2m?1的扫描窗口.在每个扫描窗口内,算法批量地尝试m个可能位置,首先使用反向后缀自动机从窗口中间位置向前扫描模式前缀;若成功,则再使用正向有限状态自动机从中间位置向后扫描剩余的模式后缀.分析证明,LDM算法的最差、最好、平均时间复杂度分别达到了理论最好结果:O(n),O(n/m),O(n(logσm)/m).实际性能测试也验证了平均时间复杂度最优这一理论结果.而且,对于在较大字母表下查找短模式的情况,LDM算法速度在被测试算法中最快.总之,LDM算法不但适合进行离线模式匹配,而且还特别适合需要进行在线高速匹配的应用.

基于混合策略的单模式匹配算法

结合后缀有限自动机和正向有限自动机的优点,提出了两个单模式匹配算法.算法中,无论是后缀自动机还是正向有限自动机,只要扫描到的模式前缀长度R>0或者超过模式长度的1/2时,使用正向有限自动机继续向右进行扫描;否则都滑动m-R个字符,使用后缀自动机反向扫描模式串的前缀.两个算法的最差、最好时间复杂度分别为O(n)和O(n/m).结果表明,在短模式的情况下,两个算法的平均时间复杂度均好于RF和LDM,在小字符集长模式或大字符集短模式的情况下它们的平均性能好于BM.

基于组合策略的单模式串精确匹配算法

以仅使用后缀有限自动机的RF算法作为参照对象,对采用组合策略的LDM、ILDM1、ILDM2等算法时间复杂度进行了比较研究。实验表明,LDM和ILDM1算法的时间复杂度要差于RF算法,即组合策略是失效的。实验还发现,ILDM2算法中把模式前缀长度R是否超过模式长度m的1/2作为正向有限自动机暂停匹配的条件,对于中小字母表的模式串的匹配也不是最佳策略。