一种快速的基于BM模式匹配的改进算法  

A fast improved pattern matching algorithm based on BM

作　　者：马占飞[1] 杨树英 郭广丰[1] 

机构地区：[1]内蒙古科技大学包头师范学院计算机系,内蒙古包头014030 [2]包头服务管理职业学校信息技术系,内蒙古包头014030

出　　处：《控制与决策》2013年第12期1855-1858,1863,共5页Control and Decision

基　　金：国家自然科学基金项目(61163025);内蒙古自治区自然科学基金项目(2010BS0904);内蒙古自治区高等学校科学研究基金重点项目(NJ10162);内蒙古自治区高等学校科学研究基金项目(NJZY07116)

摘　　要：模式匹配算法是入侵检测系统(IDS)中非常重要的一种算法.在研究和分析几种常用模式匹配算法的基础上,提出一种快速的基于BM(Boyer-Moore)模式匹配的改进算法—–IBM算法.该算法充分利用模式串的末字符和末字符所对应的文本串的后两字符的唯一性,同时参考文本串本身的信息来提高模式串的移动量,使得每次失配后,在保证不丢失匹配成功可能性的前提下尽可能多地向后跳跃.实验结果表明,该算法相比其他模式匹配算法,在检测性能和匹配效率上均具有很大优势,并且能够有效地提高IDS的检测效率和性能.The pattern matching algorithm is a very important method in the intrusion detection system（IDS）. Through analyzing and studying the characteristics of the BM（Boyer-Moore） algorithm and BMHS algorithm, an improved algorithm based on BM（IBM） algorithm is proposed. IBM algorithm integrates the merits of other patternmatching algorithms. The IBM algorithm takes full advantage of the uniqueness of the last character of the pattern string and its corresponding to the next two characters of text string to determine the moving distance of the pattern string. Meanwhile, it also takes into account the information of text string itself to increase the amount of move of the pattern string as much as possible, when the text string and pattern string are mismatch. Theoretical analysis and experimental results show that the IBM algorithm can significantly decrease the moving time and shorten the pattern matching time than other pattern matching algorithms, and can effectively improve the detection efficiency and performance of the IDS.

关 键 词：模式匹配算法 入侵检测系统 IBM算法 模式串 文本串 

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