Patent ID: 8938454
Filing Date: 2015-01-20
Classification: G06F

Abstract:
1. For use in a system including a non-transitory computer-readable storage medium storing a data structure for emulating, with, at most, a number b of concurrent active states, a nondeterministic finite automaton (NFA) having a finite set of states, a finite set of input symbols and a transition function covering each state and input symbol, the data structure including (1) a plurality of tunable finite automaton (TFA) states, up to b TFA states representing any NFA active state combination, each of the plurality of states having at least one associated state label covering the finite set of input symbols, and (2) a table including a plurality of entries, each of the plurality of entries (i) including up to b pointers to up to b TFA states, the union of the up to b TFA states corresponding to one of the NFA active state combination, and (ii) being indexed by an NFA active state combination corresponding to a state of a deterministic finite automaton representation of the NFA, a computer-implemented method for determining whether an arbitrary sequence of input symbols matches a set of regular expressions represented by the NFA, the computer-implemented method comprising: a) defining, with a computer system including at least one processor, each of up to b of the plurality of TFA states as an initial state; b) receiving, with the computer system, a next symbol of the arbitrary sequence of input symbols; c) using the next symbol to determine, with the computer system, a state label associated with each of the up to b initial TFA states; d) using a union of the up to b state labels to determine, with the computer system, one of the plurality of entries of the table; e) deactivating, with the computer system, each of the up to b initial TFA states; f) activating, with the computer system, a next set of up to b TFA states using pointers stored in the entry; g) determining, with the computer system, if the next set of up to b active TFA states includes at least one match TFA state; h) if it was determined that the next set of up to b active TFA states include at least one match TFA state, then indicating, with the computer system, a match corresponding the at least one match TFA state; i) if there are no unprocessed symbols of the arbitrary sequence of input symbols, ending the method, otherwise, if there are any unprocessed symbols, wherein the number b is a specified parameter and is at least 2.