计算机工程

• 开发研究与工程应用 • 上一篇    

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

许家铭1,2,3,李晓东2,金 键1,2,马 盈4   

  1. (1. 中国互联网络信息中心,北京 100190;2. 中国科学院计算机网络信息中心,北京 100190;3. 中国科学院大学,北京 100190;4. 东北师范大学理想信息技术研究院,长春 130117)
  • 收稿日期:2013-01-15 出版日期:2014-03-15 发布日期:2014-03-13
  • 作者简介:许家铭(1987-),男,硕士研究生,主研方向:网络安全,下一代互联网技术;李晓东,研究员;金 键,高级工程师;马 盈,硕士研究生。
  • 基金项目:
    国家自然科学基金资助项目“多模态Web作弊间的统计机器学习方法研究”(61005029)。

An Efficient Multiple Patterns String Matching Algorithm

XU Jia-ming 1,2,3, LI Xiao-dong 2, JIN Jian 1,2, MA Ying 4   

  1. (1. China Internet Network Information Center, Beijing 100190, China; 2. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China;3. University of Chinese Academy of Sciences, Beijing 100190, China; 4. Ideal Research Institute of Information Technology, Northeast Normal University, Changchun 130117, China)
  • Received:2013-01-15 Online:2014-03-15 Published:2014-03-13

摘要: 在Fan-Su(FS)多模式字符串匹配算法基础上,结合BM-Horspool(BMH)算法和Quick Search(QS)算法的优点,提出一种高效的多模式字符串匹配算法。该算法能够充分利用本次匹配失败和部分匹配成功的信息,一方面增加模式树根节点失配的概率,提高匹配过程中失配时的跳跃距离。另一方面避免不必要的状态转移,实现不匹配时的连续跳转。分析指出,在最好情况和平均情况下,时间复杂度均优于ACBM算法和FS算法。实验结果表明,一般情况下该算法的查找时间仅为AC算法的10%~35%, ACBM算法的50%~60%,FS算法的70%左右,FSQB算法的65%左右。

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

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

中图分类号: