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

A Filter Optimized Bit-parallel Approximate String Matching Algorithm

作　　者：石永革[1] 张毫[1] 

机构地区：[1]南昌大学信息工程学院,江西南昌330031

出　　处：《青岛科技大学学报（自然科学版）》2016年第1期108-112,共5页Journal of Qingdao University of Science and Technology:Natural Science Edition

基　　金：国家自然科学基金项目(61163005)

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]