Journal of Systems Engineering and Electronics ›› 2006, Vol. 17 ›› Issue (2): 437-442.doi: 10.1016/S1004-4132(06)60074-1

• SOFTWARE ALGORITHM AND SIMULATION • Previous Articles     Next Articles

New multi-pattern matching algorithm

Liu Gongshen, Lz Jianhua & Lz Shenghong   

  1. School of Information Security Engineering, Shanghai Jiaotong University, Shanghai 200030, P. R. China
  • Online:2006-06-26 Published:2019-12-20

Abstract:

The traditional multiple pattern matching algorithm, deterministic finite state automata, is implemented by tree structure. A new algorithm is proposed by substituting sequential binary tree for traditional tree. It is proved by experiment that the algorithm has three features; its construction process is quick, its cost of memory is small. At the same time, its searching process is as quick as the traditional algorithm. The algorithm is suitable for the application which requires preprocessing the patterns dynamically.

Key words: multiple pattern matching, finite state automata, sequential binary tree