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

来源：软件学报杂志2018年第2期北京时间：

作者：刘慧婷,刘志中,黄厚柱,吴信东

单位：刘慧婷，计算智能与信号处理教育部重点实验室(安徽大学), 安徽 合肥 230039;安徽大学 计算机科学与技术学院, 安徽 合肥 23060111,刘志中，计算智能与信号处理教育部重点实验室(安徽大学), 安徽 合肥 230039;安徽大学 计算机科学与技术学院, 安徽 合肥 23060102,黄厚柱，计算智能与信号处理教育部重点实验室(安徽大学), 安徽 合肥 230039;安徽大学 计算机科学与技术学院, 安徽 合肥 23060103,吴信东，合肥工业大学 计算机科学与信息工程学院, 安徽 合肥 230009;School of Computing and Informatics, University of Louisiana at Lafayette, Lafayette 70503, USA04

摘要：带有间隙约束的模式匹配问题是序列模式挖掘的关键问题之一.目前，大多数的研究都为非负间隙，对字符串中每个字符的出现顺序有着严格的要求.为了增加匹配的灵活性，并且考虑到在序列模式挖掘中采用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条件;模式匹配;线性表

基金资助：国家重点研发计划（2016YFB1000901）；国家自然科学基金（61202227）