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

摘要

传统的模式匹配算法匹配效率较低,有时无法满足入侵检测、搜索引擎等系统性能需求。为此,在BM算法及其衍生算法的基础上,提出了一种高效的模式匹配算法—BMQ算法。该算法利用模式串末字符对应的文本字符与文本字符下一个字符的独特性和组合性,有效提高了模式串最大右移位数出现的概率,加快了匹配速度。通过实验对比,BMQ算法的效率优于BM匹配算法;为进一步验证其有效性,将改进后的算法引入到入侵检测系统中,实验测试结果表明,BMQ算法提高了入侵检测效率。