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

An Improved Pattern Matching Algorithm Based on BM

作　　者：蒋亚平[1] 田月霞[1] 赵军伟[1] 

机构地区：[1]郑州轻工业学院计算机与通信工程学院,郑州450000

出　　处：《科技通报》2015年第9期178-182,共5页Bulletin of Science and Technology

基　　金：国家自然科学基金资助项目((No.61272038);河南省科技厅科技攻关资助项目(No.0624220084)

摘　　要：传统的模式匹配算法匹配效率较低,有时无法满足入侵检测、搜索引擎等系统性能需求。为此,在BM算法及其衍生算法的基础上,提出了一种高效的模式匹配算法—BMQ算法。该算法利用模式串末字符对应的文本字符与文本字符下一个字符的独特性和组合性,有效提高了模式串最大右移位数出现的概率,加快了匹配速度。通过实验对比,BMQ算法的效率优于BM匹配算法;为进一步验证其有效性,将改进后的算法引入到入侵检测系统中,实验测试结果表明,BMQ算法提高了入侵检测效率。The traditional pattern matching algorithm to match the lower efficiency, and sometimes can not meet the needs of the system performance of intrusion detection, search engines. For this purpose, on the basis of BM algorithm and its derivative algorithm, proposed a efficient algorithm for pattern matching algorithm-BMQ. Unique combination of this algorithm and use patterns corresponding to the last character string of text characters and text character by character, and effectively improve the probability of the largest model train digits that appear to the right to accelerate the matching speed. Experiments comparing the efficiency of the algorithm is better than BM BMQ matching algorithm; To further verify the validity of the improved algorithm is introduced into the intrusion detection system, the experimental results show that, BMQ algorithm improves the efficiency of intrusion detection.

关 键 词：BMQ算法 模式匹配 BM算法 入侵检测 

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