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

• 作者: 周开来 孙辉 李翠平 熊子绎 陈红
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 模式匹配 稀疏间隙约束 后缀自动机 并行算法 通配符
• 年，卷（期）: 2018,（12）
• 所属期刊栏目: 数据库技术
• 页码范围: 3799-3819
• 页数: 21页
• 分类号: TP311
• 字数: 16138字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005326

摘要

带通配符的模式匹配是一个经典的研究问题,带有可变间隙约束的模式匹配是近年来比较热门的研究方向.为适应某些查询精度要求较高的应用领域,提出一种在稀疏间隙约束条件下求解模式匹配完备解的算法SGPM-SAI(pattem 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算法的加速效果显著,且具有良好的并行可扩展性,能够充分利用现代众核处理器的高并行计算优势.