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



Abstract:Pattern matching with wildcards is a classic problem, and matching with variable gap constraints is a popular direction in this field in recent years. In order to meet the requirement of high accuracy in some query applications, this paper proposes an algorithm (referred to as SGPM-SAI) to obtain a complete solution of pattern matching under the condition of sparse gaps constraint. SGPM-SAI firstly creates an index structure called W-SAM (wildcard suffix automation) for the preprocessed text, and then get EndPos collection for each pattern segmentation by searching string from W-SAM, and finally get the complete solution of pattern matching by means of EndPos sets intersection. Experimental results show that, regardless of pretreatment time, the performance of SGPM-SAI algorithm is at least 3~5 times higher than other competitive algorithms, such as KMP, BM, AC, suffix array. Compared with the latest version (SAIL-Gen) of SAIL algorithm, the performance of SGPM-SAI is significantly better under the condition of sparse gaps constraint. In addition, this paper introduces parallel process methods for SGPM-SAI algorithm so as to effectively utilize the massive parallel processing units of modern processors. Experimental results show that the acceleration of Parallel SGPM-SAI algorithm has significant effect, as well as good parallel scalability. This indicates that the presented method can take full advantage of the high parallel computation capability of modern many-core processors.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/5326