一般间隙与One-Off条件的序列模式匹配

摘要：

带有间隙约束的模式匹配问题是序列模式挖掘的关键问题之一.目前,大多数的研究都为非负间隙,对字符串中每个字符的出现顺序有着严格的要求.为了增加匹配的灵活性,并且考虑到在序列模式挖掘中采用one-off条件更加合理,研究一般间隙与one-off条件下的模式匹配问题.该问题为NP-Hard问题.为了有效地求解该问题,提出了MSAING(maximum sequential pattern matching with one-off and general gaps condition)算法:首先,利用Reverse策略使模式与序列达到最佳的匹配状态;然后,使用线性表的结构使匹配过程中消耗的时间和空间大幅度地降低,同时,利用回溯机制提高匹配的成功率;最后,根据inside_Checking机制判断模式串是否会产生内部重复现象,以进一步提高算法的执行效率.理论证明了MSAING算法的完备性,实验结果验证了MSAING算法匹配结果的准确性以及在时间和空间方面的高效性.

关键词：一般间隙、one-off条件、模式匹配、线性表

所属期刊栏目：29

分类号：TP181(自动化基础理论)

资助基金：国家重点研发计划2016YFB1000901;国家自然科学基金61202227National Key Research and Development Program of China2016YFB1000901;National Natural Science Foundation of China61202227

在线出版日期：2018-03-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共20页

页码：363-382