一种带稀疏间隙约束的并行模式匹配算法

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

作者：周开来,陈红,熊子绎,李翠平,孙辉

单位：周开来，数据工程与知识工程国家教育部重点实验室(中国人民大学), 北京 100872;中国人民大学 信息学院, 北京 100872;郑州轻工业大学 软件学院, 河南 郑州 45000111,陈红，数据工程与知识工程国家教育部重点实验室(中国人民大学), 北京 100872;中国人民大学 信息学院, 北京 10087202,熊子绎，数据工程与知识工程国家教育部重点实验室(中国人民大学), 北京 100872;中国人民大学 信息学院, 北京 10087203,李翠平，数据工程与知识工程国家教育部重点实验室(中国人民大学), 北京 100872;中国人民大学 信息学院, 北京 10087204,孙辉，数据工程与知识工程国家教育部重点实验室(中国人民大学), 北京 100872;中国人民大学 信息学院, 北京 10087205

摘要：带通配符的模式匹配是一个经典的研究问题，带有可变间隙约束的模式匹配是近年来比较热门的研究方向.为适应某些查询精度要求较高的应用领域，提出一种在稀疏间隙约束条件下求解模式匹配完备解的算法SGPM-SAI（pattern matching with sparse gaps constraint based on suffix automaton index）.SGPM-SAI通过对文本串预处理，建立一种称为W-SAM的图索引结构，然后对模式串分段查找EndPos集合，最后以集合归并求交的方法得到模式匹配的完备解.实验结果表明：在不考虑预处理时间的情况下，相比几种最典型的模式匹配算法（KMP，BM，AC，suffix array），SGPM-SAI算法性能优势显著，至少高出3~5倍.通过与SAIL算法的最新优化版本（SAIL-Gen）进行比较，在稀疏间隙约束条件下，SGPM-SAI的性能要显著优于SAIL-Gen算法.此外，为有效利用现代处理器的大规模并行处理单元，提出了并行优化后的算法Parallel SGPM-SAI.实验结果表明：Parallel SGPM-SAI算法的加速效果显著，且具有良好的并行可扩展性，能够充分利用现代众核处理器的高并行计算优势.

关键词：模式匹配;稀疏间隙约束;后缀自动机;并行算法;通配符

基金资助：国家重点研发计划（2016YFB1000702）；国家重点基础研究发展计划（973）（2014CB340402）；国家高技术研究发展计划（863）（2014AA015204）；国家自然科学基金（61272137，61202114，61532021）；国家社会科学基金（12&ZD220）；中国人民大学科学研究基金（中央高校基本科研业务费专项资金资助）项目成果（15XNLQ06）