计算机工程 ›› 2010, Vol. 36 ›› Issue (1): 208-210.doi: 10.3969/j.issn.1000-3428.2010.01.072

• 人工智能及识别技术 • 上一篇    下一篇

一种基于反向有限自动机的多模式匹配算法

关 超,蒋建中,郭军利   

  1. (解放军信息工程大学信息工程学院,郑州 450002)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-01-05 发布日期:2010-01-05

Multiple Patterns Match Algorithm Based on Reverse Finite State Automata

GUAN Chao, JIANG Jian-zhong, GUO Jun-li   

  1. (Information Engineering College, PLA Information Engineering University, Zhengzhou 450002)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-01-05 Published:2010-01-05

摘要: 在基于有限自动机的多模式匹配算法DFSA的基础上,结合改进的BM单模式匹配算法的优点,提出一种快速的多模式字符串匹配算法。在一般情况下,该算法不需要匹配目标文本串的每个字符,能充分利用匹配过程中本次匹配不成功的信息和已成功的信息,跳过尽可能多的字符。实验表明,模式串较短时,该算法需要的时间约为DFSA的1/2,模式串较长时,所需时间约为DFSA算法的1/3。

关键词: 多模式匹配, 有限自动机, 匹配算法

Abstract: A fast algorithm to perform multiple patterns match in a string is described. The proposed match algorithm is based on the concept of Deterministic Finite State Automata(DFSA), combining the advantages of Boyer Moore’s algorithm, the fast algorithms for single pattern matching. In general, it does not need inspect each character of the string. It skips as many characters as possible by making full use of the succeeded match information and failure information during the matching. The proposed algorithm achieves excellent performance in the cases of both short patterns and long patterns. Experimental results show that in the case of short patterns, the time it takes to search a string is 1/2 of the time DFSA method takes, and in the case of long patterns, the time is only 1/3 of the time by DFSA method.

Key words: multiple patterns match, finite state automata, match algorithm

中图分类号: