Generating a tunable finite automaton for regular expression matching

A computer-implemented method for generating a tunable finite automaton (“TFA”) from 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 computer-implemented method comprising:

• a) receiving, as input, with a computer system including at least one processor, both
• (1) a deterministic finite automaton (“DFA”) representation of the NFA, and
• (2) a parameter, b, defining a maximum number of concurrent active states of the TFA;
• b) regrouping, with the computer system, an NFA active state combination associated with each state of the DFA into up to b subsets, with the objective of minimizing the number of total distinct subsets;
• c) generating, with the computer system, a TFA including one TFA state for each of the distinct subsets, wherein the generated TFA has, at most, b concurrent active TFA states;
• and
• d) storing, with the computer system, the generated TFA,
• wherein the parameter b is at least 2.

A non-transitory computer-readable storage medium storing a data structure for emulating, with, at most, b 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:

• a) a plurality of tunable finite automaton (“TFA”) states, up to a number b of 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
• b) a table including a plurality of entries, each of the plurality of entries (1) including up to b pointers to up to b TFA states, a union of the up to b TFA states corresponding to one of the NFA active state combination, and (2) being indexed by an NFA active state combination corresponding to a state of a deterministic finite automaton (“DFA”) representation of the NFA,
• wherein the number b is a specified parameter and is at least 2.

An apparatus comprising:

• a) at least one processor;
• and
• b) at least one storage device storing processor executable instructions which, when executed by the at least one processor, cause the at least one processor to perform a method for generating a tunable finite automaton (“TFA”) from 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 TFA having, at most, a number b of concurrent active states, the computer-implemented method including
• 1) receiving a deterministic finite automaton (“DFA”) representation of the NFA,
• 2) regrouping the NFA active state combination associated with each state of the DFA into up to b subsets, with the objective of minimizing the number of total distinct subsets,
• 3) generating one TFA state for each of the distinct subsets,
• 4) for each of the DFA states, storing pointers to the up to b TFA states in a table entry associated with the NFA active state combination of the DFA state,
• 5) associating each of the TFA states with appropriate transition representations using the transition functions of the NFA states corresponding to the TFA state,
• 6) storing each of the TFA states, and
• 7) storing for each of the TFA states, each of the appropriate transition representations in association with the TFA state and a corresponding input symbol,
• wherein the number b is a specified parameter and is at least 2.

An apparatus comprising:

• a) at least one processor;
• and
• b) at least one storage device storing processor executable instructions which, when executed by the at least one processor, cause the at least one processor to perform a method for generating a tunable finite automaton (“TFA”) from 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 computer-implemented method including
• 1) receiving, as input, with the computer system, both
• (A) a deterministic finite automaton (“DFA”) representation of the NFA, and
• (B) a parameter, b, defining a maximum number of concurrent active states of the TFA;
• 2) regrouping, with the computer system, an NFA active state combination associated with each state of the DFA into up to b subsets, with the objective of minimizing the number of total distinct subsets;
• 3) generating, with the computer system, a TFA including one TFA state for each of the distinct subsets, wherein the generated TFA has, at most, b concurrent active TFA states;
• and
• 4) storing, with the computer system, the generated TFA, wherein the parameter b is at least 2.