改进的中文近似字符串匹配算法

摘要

BPM-BM算法在针对汉字等大字符集的近似字符串匹配时取得了很好的实际效果,但该算法在最差情况下的总体时间复杂度为O(σ+nm).而提出的IBPM-BM算法由于具有记忆的能力,保证了过滤阶段的无回溯,可以在理论上保证最差情况下的总体时间复杂度为O(σ+n),而在最佳情况下的时间复杂度与BPM-BM算法一致.