主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第9期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
周开来,陈红,熊子绎,李翠平,孙辉.一种带稀疏间隙约束的并行模式匹配算法.软件学报,2018,29(12):3799-3819
一种带稀疏间隙约束的并行模式匹配算法
Parallel Pattern Matching Algorithm with Sparse Gap Constraint
投稿时间:2017-02-13  修订日期:2017-05-25
DOI:10.13328/j.cnki.jos.005326
中文关键词:  模式匹配  稀疏间隙约束  后缀自动机  并行算法  通配符
英文关键词:pattern matching  sparse gaps constraint  suffix automaton  parallel algorithm  wildcards
基金项目:国家重点研发计划(2016YFB1000702);国家重点基础研究发展计划(973)(2014CB340402);国家高技术研究发展计划(863)(2014AA015204);国家自然科学基金(61272137,61202114,61532021);国家社会科学基金(12&ZD220);中国人民大学科学研究基金(中央高校基本科研业务费专项资金资助)项目成果(15XNLQ06)
作者单位E-mail
周开来 数据工程与知识工程国家教育部重点实验室(中国人民大学), 北京 100872
中国人民大学 信息学院, 北京 100872
郑州轻工业大学 软件学院, 河南 郑州 450001 
 
陈红 数据工程与知识工程国家教育部重点实验室(中国人民大学), 北京 100872
中国人民大学 信息学院, 北京 100872 
chong@ruc.edu.cn 
熊子绎 数据工程与知识工程国家教育部重点实验室(中国人民大学), 北京 100872
中国人民大学 信息学院, 北京 100872 
 
李翠平 数据工程与知识工程国家教育部重点实验室(中国人民大学), 北京 100872
中国人民大学 信息学院, 北京 100872 
 
孙辉 数据工程与知识工程国家教育部重点实验室(中国人民大学), 北京 100872
中国人民大学 信息学院, 北京 100872 
 
摘要点击次数: 962
全文下载次数: 548
中文摘要:
      带通配符的模式匹配是一个经典的研究问题,带有可变间隙约束的模式匹配是近年来比较热门的研究方向.为适应某些查询精度要求较高的应用领域,提出一种在稀疏间隙约束条件下求解模式匹配完备解的算法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算法的加速效果显著,且具有良好的并行可扩展性,能够充分利用现代众核处理器的高并行计算优势.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利