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

• 作者: 范立新
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 近似字符串匹配 位并行运算 过滤 编辑距离 中文字符串匹配
• 年，卷（期）: 2006,（34）
• 所属期刊栏目: 数据库与信息处理
• 页码范围: 172-174,207
• 页数: 4页
• 分类号: TP391
• 字数: 3726字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2006.34.053

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	范立新	绍兴文理学院计算机系	13	67	5.0	8.0