DFA-based and SIMD NFA-based regular expression matching on cell BE for fast network traffic filtering
Feodor Kulishov · 2009
Regular expression matching is the heart of many data processing routines, such as string search, network traffic filtering, etc. The traditional way of regexp matching is building and execution of a deterministic finite automaton (DFA), that provides O(1) processing time per 1 input symbol for any regular expression. But this technique almost always forces many modern SIMD-processors to perform regexp search in scalar mode, thus it doesn't use the most part of their computational power.