| 本文已被：浏览 2450次 下载 4585次 |
码上扫一扫！ |
|
|
| 一种带稀疏间隙约束的并行模式匹配算法 |
|
周开来1,2,3, 陈红1,2, 熊子绎1,2, 李翠平1,2, 孙辉1,2
|
|
1.数据工程与知识工程国家教育部重点实验室(中国人民大学), 北京 100872;2.中国人民大学 信息学院, 北京 100872;3.郑州轻工业大学 软件学院, 河南 郑州 450001
|
|
| 摘要: |
| 带通配符的模式匹配是一个经典的研究问题，带有可变间隙约束的模式匹配是近年来比较热门的研究方向.为适应某些查询精度要求较高的应用领域，提出一种在稀疏间隙约束条件下求解模式匹配完备解的算法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算法的加速效果显著，且具有良好的并行可扩展性，能够充分利用现代众核处理器的高并行计算优势. |
| 关键词: 模式匹配 稀疏间隙约束 后缀自动机 并行算法 通配符 |
| DOI：10.13328/j.cnki.jos.005326 |
| 分类号: |
| 基金项目:国家重点研发计划（2016YFB1000702）；国家重点基础研究发展计划（973）（2014CB340402）；国家高技术研究发展计划（863）（2014AA015204）；国家自然科学基金（61272137，61202114，61532021）；国家社会科学基金（12&ZD220）；中国人民大学科学研究基金（中央高校基本科研业务费专项资金资助）项目成果（15XNLQ06） |
|
| Parallel Pattern Matching Algorithm with Sparse Gap Constraint |
|
ZHOU Kai-Lai1,2,3, CHEN Hong1,2, XIONG Zi-Yi1,2, LI Cui-Ping1,2, SUN Hui1,2
|
|
1.Key Laboratory of Data Engineering and Knowledge Engineering of the Ministry of Education(Renmin University of China), Beijing 100872, China;2.School of Information, Renmin University of China, Beijing 100872, China;3.School of Software, Zhengzhou University of Light Industry, Zhengzhou 450001, China
|
| 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. |
| Key words: pattern matching sparse gaps constraint suffix automaton parallel algorithm wildcards |
