| 一种改进的BMH模式匹配算法 |
| |
| 引用本文： | 刘胜飞,张云泉.一种改进的BMH模式匹配算法[J].计算机科学,2008,35(11):164-165. |
| |
| 作者姓名： | 刘胜飞 张云泉 |
| |
| 作者单位： | 1. 中国科学院软件研究所并行计算实验室,北京,100080
2. 中国科学院软件研究所并行计算实验室,北京,100080;中国科学院软件研究所计算机科学国家重点实验室,北京,100080 |
| |
| 基金项目： | 国家自然科学基金(No.60303020); 国家自然基金重点项目(No.60533020); 国家重点基础研究发展计划(No.2005CB321702); 国家863(No.2006AA01A102,No.2006AA01A125); 北邮网络与交换国家重点实验室开放基金的部分资助 |
| |
| 摘 要： | 分析了目前网络上最流行的BM算法及其改进算法BMH，在此基础上提出了BMH算法的改进算法BMH2。考虑了模式串自身的特征，在原有移动距离数组的基础上增加一个新的移动数组，从而充分利用模式串特征进行更大距离的移动，使算法获得更高的效率。实验证明，改进后的算法能够增加“坏字符”方法的右移量，有效地提高匹配速率。
|
| 关 键 词： | 模式匹配 BM算法 BMH算法 时间复杂度 |
Improved Pattern Matching Algorithm of BMH |
| |
| LIU Sheng-fei,ZHANG Yun-quan.Improved Pattern Matching Algorithm of BMH[J].Computer Science,2008,35(11):164-165. |
| |
| Authors: | LIU Sheng-fei ZHANG Yun-quan |
| |
| Abstract: | Based on the discussion of the most popular BM and BMH algorithms for pattern matching on the network,an improved algorithm BMH2 was presented.Considering the feature of pattern itself,a new skip distance array was added based on the old one.It can increase the skip distance by known information.Experimental data shows that the improved algorithm can increase the right shift of bad characters and enhance the matching speed effectively. |
| |
| Keywords: | Pattern matching BM algorithm BMH algorithm Time complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机科学》浏览原始摘要信息 |
|
点击此处可从《计算机科学》下载全文 |
