Disclosed herein is an improved architecture for regular expression
pattern matching. Improvements to pattern matching deterministic finite
automatons (DFAs) that are described by the inventors include a
pipelining strategy that pushes state-dependent feedback to a final
pipeline stage to thereby enhance parallelism and throughput, augmented
state transitions that track whether a transition is indicative of a
pattern match occurring thereby reducing the number of necessary states
for the DFA, augmented state transition that track whether a transition
is indicative of a restart to the matching process, compression of the
DFA's transition table, alphabet encoding for input symbols to
equivalence class identifiers, the use of an indirection table to allow
for optimized transition table memory, and enhanced scalability to
facilitate the ability of the improved DFA to process multiple input
symbols per cycle.