Patent ID: 7725510

Claim:
A method of detecting each occurrence of a plurality of patterns in an input stream, comprising: receiving, by a computer, an input stream; generating a compressed deterministic finite state automaton (DFA) based on the plurality of patterns; and transitioning between states of said compressed DFA, at least some transitions based on multiple characters of the input stream, such that said generating step includes, constructing an original DFA based on the plurality of patterns, and compressing the original DFA such that each state of the compressed DFA represents multiple consecutive states of the original DFA, and each transition between consecutive states of the compressed DFA is a combination of all transitions between the multiple consecutive states of the original DFA, such that said compressing step includes, determining core states of the original DFA to be states having a depth of a multiple of K and pattern ending states, generating a state of the compressed DFA corresponding to each core node of the original DFA, generating goto transitions between each of the states of the compressed DFA by combining multiple transitions between the core states in the original DFA, generating next transitions between states of the compressed DFA based on next transitions between states of the original DFA, and generating shallow states of the compressed DFA and corresponding transitions based on shallow states of the original DFA.