| 改进的近似模式匹配算法 |
| |
| 引用本文： | 张丽霞,宋鸿陟. 改进的近似模式匹配算法[J]. 计算机工程与设计, 2011, 32(5): 1820-1823 |
| |
| 作者姓名： | 张丽霞 宋鸿陟 |
| |
| 作者单位： | 华南农业大学,信息学院人机交互研究中心,广东,广州,510642 |
| |
| 摘 要： | 为了提高近似模式匹配算法在多次匹配情况下的效率,借鉴了文本快速过滤算法的思想,分析了平均情况下改进的动态规划算法(DP算法),并在此基础上设计实现了一种改进的DP算法,称为IMP-DP。该算法在匹配过程中,将上一次运算的结果存储起来,与上次相同的匹配可在原有成功匹配结果的基础上进行运算,忽略将不可能产生成功匹配的区域,只关注剩余的区域。由算法时间复杂性和实验对比分析结果表明,该算法在多次匹配情况下,效率远远高于其它算法,从而验证了该算法改进的有效性。
|
| 关 键 词： | 模式匹配 近似模式匹配 动态规划 文本快速过滤 IMP-DP |
Improved approximate pattern matching algorithm |
| |
| ZHANG Li-xia,SONG Hong-zhi. Improved approximate pattern matching algorithm[J]. Computer Engineering and Design, 2011, 32(5): 1820-1823 |
| |
| Authors: | ZHANG Li-xia SONG Hong-zhi |
| |
| Affiliation: | (Research Center of Human Computer Interaction,College of Information,South China Agricultural University,Guangzhou 510642,China) |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
