文献类型：期刊文献

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

英文题名：Improved Algorithm of Approximate Chinese String Matching

作者：范立新[1]

机构：[1]绍兴文理学院计算机系

年份：2006

卷号：42

期号：34

起止页码：172

中文期刊名：计算机工程与应用

外文期刊名：Computer Engineering and Applications

收录：CSTPCD、、北大核心2004、CSCD2011_2012、北大核心、CSCD

语种：中文

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

外文关键词：approximate string matching; bit-parallel; filter; edit distance; chinese string matching

中文摘要：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.