10.3969/j.issn.1000-3428.2014.03.067
一种高效的多模式字符串匹配算法
在Fan-Su(FS)多模式字符串匹配算法基础上,结合BM-Horspool(BMH)算法和Quick Search(QS)算法的优点,提出一种高雙的多模式字符串匹配算法。该算法能够充分利用本次匹配失败和部分匹配成功的雷息,一方面增加模式树根节点失配的概率,提高匹配过程中失配时的跳跃距离。另一方面避免不必要的状态转移,实现不匹配时的连霪跳转。分析指出,在最好情况和平均情况下,时间复杂度均优于 ACBM 算法和 FS 算法。实验结果表明,一般情况下该算法的查找时间仅为 AC 算法的10%~35%, ACBM算法的50%~60%,FS算法的70%左右,FSQB算法的65%左右。
字符串匹配、多模式匹配、有限自动状态机、算法复杂度、网络安全、雷息检索
TP301.6(计算技术、计算机技术)
陠目国家自然科学基金资助陠目“多模态Web作弊间的统计机器学习方法研究”61005029。
2014-04-15(万方平台首次上网日期,不代表论文的发表时间)
共7页
315-321