BM模式匹配算法剖析  

Anatomy of BM pattern matching algorithm

作　　者：巫喜红[1] 凌捷[2] 

机构地区：[1]嘉应学院计算机科学与技术系,广东梅州514015 [2]广东工业大学计算机学院,广东广州510090

出　　处：《计算机工程与设计》2007年第1期29-31,共3页Computer Engineering and Design

基　　金：广东省科技攻关基金项目(2005B10101067);广州市科技攻关基金项目(2005Z3D0291)

摘　　要：在对典型的BF、KMP模式匹配算法进行比较分析的基础上,详细分析了BM算法。为了进一步加快算法的速度,对BM算法中已经部分匹配的移动位置情况进行改进。在原有的移动距离函数基础上增加一个新的移动距离函数,从而尽量利用已有信息进行更大的尝试位置移动,使算法具有更高的效率。通过引用具体实例,比较分析了改进前后的BM算法,结果证明改进后的BM算法的速度更快,效率更高。On the study of BF algorithm and KMP algorithm, BM algorithm is analyzed. To increase the speed ofalgorithrn, the shift position that had matched partially in BM algorithm is improved. A new shift distance function is added based on the old one, and maked the most of known information to increase the shift distance so that it is more efficient. In the end, by citing specific examples, the analysis of the BM algorithm that is modified is carried out. The results show the BM algorithm that is modified is more quickly and more efficient.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]