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

Improved Algorithm of Approximate Chinese String Matching

作　　者：范立新[1] 

机构地区：[1]绍兴文理学院计算机系,浙江绍兴312000

出　　处：《计算机工程与应用》2006年第34期172-174,207,共4页Computer Engineering and Applications

摘　　要：BPM-BM算法在针对汉字等大字符集的近似字符串匹配时取得了很好的实际效果,但该算法在最差情况下的总体时间复杂度为O(!+nm)。而提出的IBPM-BM算法由于具有记忆的能力,保证了过滤阶段的无回溯,可以在理论上保证最差情况下的总体时间复杂度为O(!+n),而在最佳情况下的时间复杂度与BPM-BM算法一致。Though BPM-BM has achieved good performance especially in matching of Chinese characters,the worst case time is 0 （σ＋nm）.In this paper,we present a improved algorithm IBPM-BM,which can achieve good performance closed to BPM-BM in practice,and obtain O（σ＋n） worst case time.

关 键 词：近似字符串匹配 位并行运算 过滤 编辑距离 中文字符串匹配 

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