一种改进的BMH模式匹配算法  

Improved Pattern Matching Algorithm of BMH

作　　者：刘胜飞[1] 张云泉[1,2] 

机构地区：[1]中国科学院软件研究所并行计算实验室,北京100080 [2]中国科学院软件研究所计算机科学国家重点实验室,北京100080

出　　处：《计算机科学》2008年第11期164-165,173,共3页Computer Science

基　　金：国家自然科学基金(No.60303020);国家自然基金重点项目(No.60533020);国家重点基础研究发展计划(No.2005CB321702);国家863(No.2006AA01A102;No.2006AA01A125);北邮网络与交换国家重点实验室开放基金的部分资助

摘　　要：分析了目前网络上最流行的BM算法及其改进算法BMH,在此基础上提出了BMH算法的改进算法BMH2。考虑了模式串自身的特征,在原有移动距离数组的基础上增加一个新的移动数组,从而充分利用模式串特征进行更大距离的移动,使算法获得更高的效率。实验证明,改进后的算法能够增加"坏字符"方法的右移量,有效地提高匹配速率。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.

关 键 词：模式匹配 BM算法 BMH算法 时间复杂度 

分 类 号：TP311.56[自动化与计算机技术—计算机软件与理论] TQ455.1[自动化与计算机技术—计算机科学与技术]