一种高效的多模式字符串匹配算法  

An Efficient Multiple Patterns String Matching Algorithm

作　　者：许家铭[1,2,3] 李晓东[2] 金键[1,2] 马盈[4] 

机构地区：[1]中国互联网络信息中心,北京100190 [2]中国科学院计算机网络信息中心,北京100190 [3]中国科学院大学,北京100190 [4]东北师范大学理想信息技术研究院,长春130117

出　　处：《计算机工程》2014年第3期315-320,F0003,共7页Computer Engineering

基　　金：国家自然科学基金资助项目"多模态Web作弊间的统计机器学习方法研究"(61005029)

摘　　要：在Fan-Su（FS）多模式字符串匹配算法基础上，结合BM—Horspool（BMH）算法和QuickSearch（QS）算法的优点，提出一种高效的多模式字符串匹配算法。该算法能够充分利用本次匹配失败和部分匹配成功的信息，一方面增加模式树根节点失配的概率，提高匹配过程中失配时的跳跃距离。另一方面避免不必要的状态转移，实现不匹配时的连续跳转。分析指出，在最好情况和平均情况下，时间复杂度均优于ACBM算法和FS算法。实验结果表明，一般情况下该算法的查找时间仅为AC算法的10％-35％，ACBM算法的50％-60％，FS算法的70％左右，FSQB算法的65％左右。Combined with the advantages of BM-Horspool（BMH） algorithm and Quick-Search（QS） algorithm, an effective algorithm to perform multiple patterns matching in a string is proposed on the concept of Fan-Su（FS） algorithm. To reduce the number of comparisons, and improve the efficiency of matching, the proposed algorithm skips as many characters as possible and avoids useless state transitions, by making full use of the successful and failing information during the matching. Experimental results show that the proposed algorithm can achieve more excellent performance than the ACBM algorithm and FS algorithm. The time it takes for the proposed algorithm to search a string is only 10%-35% of the AC algorithm, 50%-60% of the ACBM algorithm, 70% of the FS algorithm, and 65% of the FSQB algorithm.

关 键 词：字符串匹配 多模式匹配 有限自动状态机 算法复杂度 网络安全 信息检索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]