| 改进的中文近似字符串匹配算法 |
| |
| 引用本文： | 范立新. 改进的中文近似字符串匹配算法[J]. 计算机工程与应用, 2006, 42(34): 172-174,207 |
| |
| 作者姓名： | 范立新 |
| |
| 作者单位： | 绍兴文理学院,计算机系,浙江,绍兴,312000 |
| |
| 摘 要： | BPM-BM算法在针对汉字等大字符集的近似字符串匹配时取得了很好的实际效果,但该算法在最差情况下的总体时间复杂度为O(!+nm)。而提出的IBPM-BM算法由于具有记忆的能力,保证了过滤阶段的无回溯,可以在理论上保证最差情况下的总体时间复杂度为O(!+n),而在最佳情况下的时间复杂度与BPM-BM算法一致。
|
| 关 键 词： | 近似字符串匹配 位并行运算 过滤 编辑距离 中文字符串匹配 |
| 文章编号： | 1002-8331（2006）34-0172-03 |
| 收稿时间： | 2006-02-01 |
| 修稿时间： | 2006-02-01 |
Improved Algorithm of Approximate Chinese String Matching |
| |
| FAN Li-xin. Improved Algorithm of Approximate Chinese String Matching[J]. Computer Engineering and Applications, 2006, 42(34): 172-174,207 |
| |
| Authors: | FAN Li-xin |
| |
| Affiliation: | Computer Science Department of Shaoxing University,Shaoxing,Zhejiang 312000,China |
| |
| Abstract: | Though BPM-BM has achieved good performance especially in matching of Chinese characters,the worst case time is O( 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. |
| |
| Keywords: | approximate string matching bit-parallel filter edit distance chinese string matching |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
