计算机工程Issue(3)：315-321,7.DOI:10.3969/j.issn.1000-3428.2014.03.067
一种高效的多模式字符串匹配算法
An Efficient Multiple Patterns String Matching Algorithm
摘要
Abstract
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.关键词
字符串匹配/多模式匹配/有限自动状态机/算法复杂度/网络安全/雷息检索Key words
string matching/multiple patterns matching/finite state automata/algorithm complexity/network security/information retrieval分类
信息技术与安全科学引用本文复制引用
霟家铭,李陰东,金键,马盈..一种高效的多模式字符串匹配算法[J].计算机工程,2014,(3):315-321,7.基金项目
陠目国家自然科学基金资助陠目“多模态Web作弊间的统计机器学习方法研究”(61005029)。 （61005029）
