基于BM窗口竞争的高效单模式匹配算法  

Efficient Single Pattern Matching Algorithm Based on BM Window Competition

作　　者：陈伟[1] 滕宏舜 

机构地区：[1]浙江师范大学数理与信息工程学院,浙江金华321004

出　　处：《计算机工程》2015年第12期144-149,共6页Computer Engineering

基　　金：金华市科学技术研究计划基金资助项目(2013-1-023)

摘　　要：对于单模式匹配Boyer-Moore(BM)算法,为提高首字符的不匹配率和失配窗口的最大移动距离,结合BM系列改进算法的设计思想,提出一种高效算法Skii-BM。在Q(x)函数基础上引入窗口竞争思想,以极大化跳跃距离。实验结果表明,改进算法能减少不必要的匹配过程,提高窗口移动速度,从而改善匹配效率。For the single pattern matching algorithm Boyer-Moore（BM）,improvement always starts from increasing the mismatching rate of first character and maximizing the move distance of the mismatched window.Absorbing the design thoughts of BM improving algorithm,this paper presents an efficient algorithm Skii-BM,which introduces an idea of window competition based on Q（x）function to maximize the jump distance.Experimental results show that such improvement can reduce unnecessary comparison,and speed up window moving through above measures,to improve the matching efficiency.

关 键 词：模式匹配 BOYER-MOORE算法 特征字符 窗口竞争 Q函数 

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