基于AC_QS多模式匹配算法的优化研究

摘要：

随着互联网的日益强大,互联网上数据急剧增多,如何在海量的数据中快速准确地找到所需信息,就显得尤为重要,这就需要多模式串匹配算法.多模式串匹配算法在越来越多的领域里都有应用,比如:信息安全领域中,入侵检测系统、防火墙等,在医学领域、数据挖掘、信息检索等等领域中均有广泛的应用.AC算法在多模式串匹配算法中是一个能达到线性时间的算法,其算法效率较高,AC QS算法是在AC算法基础上增加坏字符规则,进一步增加了AC算法的匹配效率,但其空间复杂度较高.本文在AC QS算法的基础上,对算法预处理和匹配过程中继续优化,并对字典树存储时进行了优化,使算法在空间和时间复杂度上得到进一步优化,提高了算法性能.实验结果也验证了该算法的高效性.

关键词：多模式、模式匹配、AC算法、QS算法

所属期刊栏目：7

分类号：TP301(计算技术、计算机技术)

在线出版日期：2017-11-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：100-103