一种带稀疏间隙约束的并行模式匹配算法
作者:
作者单位:

作者简介:

周开来(1978-),男,湖北南漳人,博士,副教授,主要研究领域为数据库,数据挖掘,并行计算;陈红(1965-),女,博士,教授,博士生导师,CCF杰出会员,主要研究领域为数据仓库与数据挖掘,物联网中的数据管理;熊子绎(1995-),男,硕士生,主要研究领域为数据库,并行计算;李翠平(1972-),女,博士,教授,博士生导师,CCF杰出会员,主要研究领域为社会网络分析,社会推荐,大数据分析和挖掘;孙辉(1977-),女,博士,讲师,CCF专业会员,主要研究领域为数据库与数据挖掘,并行计算.

通讯作者:

陈红,E-mail:chong@ruc.edu.cn

中图分类号:

基金项目:

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


Parallel Pattern Matching Algorithm with Sparse Gap Constraint
Author:
Affiliation:

Fund Project:

National Key Research & Develop Plan (2016YFB1000702); National Basic Research Program of China (973)(2014CB340402); National High Technology Research and Development Program of China (863) (2014AA015204); National NaturalScience Foundation of China (61272137, 61202114, 61532021); NSSFC (12&ZD220); Fundamental Research Funds for the CentralUniversities, and the Research Funds of Renmin University of China (15XNLQ06)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    带通配符的模式匹配是一个经典的研究问题,带有可变间隙约束的模式匹配是近年来比较热门的研究方向.为适应某些查询精度要求较高的应用领域,提出一种在稀疏间隙约束条件下求解模式匹配完备解的算法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.

    参考文献
    相似文献
    引证文献
引用本文

周开来,陈红,熊子绎,李翠平,孙辉.一种带稀疏间隙约束的并行模式匹配算法.软件学报,2018,29(12):3799-3819

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2017-02-13
  • 最后修改日期:2017-05-25
  • 录用日期:
  • 在线发布日期: 2018-12-05
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号