Multi-Pattern Matching Algorithms and Hardware Based Implementation

This paper surveys the algorithms and hardware implementations of the multi-pattern matching. Firstly, two commonly used multi-pattern algorithms, Aho-Corasick's automata based algorithm and Wu-Manber's hash based suffix matching with skipping algorithm are introduced. And then, some improving ways are referred. Next, time and space complexity of these algorithms are analyzed, and the experimental results show their performances. Further, several hardware based implementations are taken as examples to demonstrate the general methods and strategies for the implementation on hardware. The developing trend is predicted in the end.