一种改进的模式匹配算法  

Study of An Improved Pattern Matching Algorithm

作　　者：田宏[1] 李君秋[1] 

机构地区：[1]大连交通大学软件学院,辽宁大连116028

出　　处：《大连交通大学学报》2010年第4期76-79,共4页Journal of Dalian Jiaotong University

基　　金：国家自然科学基金资助项目(70471064);辽宁省教育厅高等学校科研计划资助项目(2008093)

摘　　要：针对现有的模式匹配算法的不足,在分析了传统的BF、KMP和BM模式匹配算法的基础上,提出了一种改进的模式匹配算法(NBM),该算法的思想是对BM算法中滑动距离函数d ist右移模式距离大小进行改进,并且定义了两个新的滑动距离函数,在不同的条件下,分别调用不同的滑动距离函数,更好的控制模式匹配过程.实验结果表明,该算法比BF、KMP和BM算法显著减少了字符匹配次数,有效地提高了模式匹配的速度.An improved pattern matching algorithm（NBM） is presented based on analyzing BF,KMP and BM.The idea of NBM algorithm is using different gliding distance functions by modifying the distance of dist function in BM and defining two new gliding distance functions.This algorithm can choose different gliding distances from different cases to control pattern matching process excellently.Experiments show that this NBM algorithm is more efficient,better performance and less time consumption.

关 键 词：模式匹配 BF算法 KMP算法 BM算法 NBM算法 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]