Design of high performance pattern matching engine through compact deterministic finite automata
Piti Piyachon, Yan Luo · 2008
Pattern matching relies on deterministic finite automata (DFA) to search for predefined patterns. While a bit-DFA method is recently proposed to exploit the parallelism in pattern matching, we identify its limitations and present two schemes, Label Translation Table (LTT) and CAM-based Lookup Table (CLT), to reduce the DFA memory size by 85%, and simplify the design by requiring only four processing elements of bit-DFA instead of thousands.