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

摘要

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