基于BPMBM过滤优化的近似字符串匹配算法

PDF全文下载：20160100108

石永革， 张毫

（南昌大学 信息工程学院，江西 南昌 330031）

 摘要： BPMBM算法结合位并行和过滤技术，是当前近似字符串匹配算法中效率最高的算法之一。算法中过滤机制容易导致位并行计算连续性中断，使位并行计算回溯导致性能大幅降低。针对此问题提出了基于过滤优化的BPMBM算法。实验结果表明：优化算法在大字符集环境下继承了BPMBM算法的运行高效性，在非大字符集环境下较BPMBM算法提升显著，且随着编辑距离的增长，其时间开销增长的稳定性大幅优于BPMBM算法。

关键词： 近似字符串匹配；BPMBM算法；位并行；过滤

中图分类号： TP 391            文献标志码： A

 A Filter Optimized Bitparallel Approximate String Matching Algorithm

 SHI Yongge， ZHANG Hao

 (Information  Engineering School， Nanchang University, Nanchang 330031, China)

 Abstract: BPMBM, combined with filter and bitparallel mechanism, has become one of the most effective solutions for approximate string matching problem. Bitparallelism's continuity contradicts with filter as its continuity is always interrupted by filter easily, which brings serious backtracking for the bit parallel calculation and result in a significant decrease in performance. To solve this problem, an optimized BPMBM algorithm is proposes based on filter optimization. The experimental results show that the optimized BPMBM algorithm inherits BPMBM′s high performance when dealing with large character sets, and its performance is significantly enhanced when dealing with non large character sets. Besides, its time cost growth is more stable with the edit distance growth comparing with BPMBM.

 Key words: approximate string match; BPMBM algorithm; bitparallel; filter

收稿日期： 20150328

基金项目： 国家自然科学基金项目（61163005）.

作者简介： 石永革（1953—），男，教授.

 文章编号： 16726987（2016）01010805； DOI： 10.16351/j.16726987.2016.01.022