US 2006/0242123 A1 · Hierarchical tree of deterministic finite automata

Abstract

A hierarchical tree of deterministic finite automata (DFA) is traversed and/or generated based on a set of regular expressions. The hierarchical DFA includes a root DFA linked together with a set of leaf DFAs, and possibly a set of branch DFAs. The root DFA is always active and is responsive to an input string, as are any currently active branch and leaf DFAs. When a final state or arc is reached or traversed in any active DFA, a regular expression has been matched. The branch and leaf DFAs are activated in response to the root DFA or a branch DFA reaching or traversing an activation state or arc corresponding to the branch or leaf DFA. Active branch and leaf DFAs will become inactive when a termination state or arc is reached or traversed within the branch or leaf DFA. State explosion in the hierarchical DFA can typically be avoided by selectively grouping similar portions of the regular expressions together in branch and leaf DFAs.

Claims20

Dependent claims

An apparatus for processing a hierarchical deterministic finite automata (DFA) produced from a plurality of regular expressions, the hierarchical DFA including a root DFA and one or more leaf DFAs, the apparatus comprising:

means for traversing the hierarchical DFA in response to a sequence of characters and for identifying matches to one or more of said regular expressions;
wherein said means for traversing the hierarchical DFA includes means for traversing the root DFA and for activating said leaf DFAs in response to reaching or traversing corresponding one or more activation states or arcs within the root DFA.

A method for processing a hierarchical deterministic finite automata (DFA) produced from a plurality of regular expressions, the hierarchical DFA including a root DFA and one or more leaf DFAs, the method comprising:

processing each character of a string of characters on which to perform matching in the root DFA and in each particular active leaf DFA of said leaf DFAs, said processing including:
determining a next state;
and in response to the next state being a final state or traversing a final arc, indicating a match for the corresponding regular expression of said regular expressions;
wherein said processing of said each active particular leaf DFA further includes in response to the next state being a terminating state or traversing a terminating arc in said particular leaf DFA, making said particular leaf DFA inactive;
and
wherein said processing of the root DFA further includes in response to the next state being an activation state or traversing an activation arc, activating a particular one of said leaf DFAs.

3 more elements

A method for processing a hierarchical deterministic finite automata (DFA) produced from a plurality of regular expressions, the hierarchical DFA including a root DFA, one or more branch DFAs, and one or more leaf DFAs, the method comprising:

processing each character of a string of characters on which to perform matching in the root DFA, in each particular active branch DFA of said branch DFAs, and in each particular active leaf DFA of said leaf DFAs, said processing including:
determining a next state;
and in response to the next state being a final state or traversing a final arc, indicating a match for the corresponding regular expression of said regular expressions;
wherein said processing of said each active particular leaf DFA further includes in response to the next state being a terminating state or traversing a terminating arc in said particular leaf DFA, making said particular leaf DFA inactive;
wherein said processing of said each active particular branch DFA further includes in response to the next state being a terminating state or traversing a terminating arc in said particular branch DFA, making said particular branch DFA inactive;
wherein said processing of said each active particular branch DFA further includes in response to the next state being an activation state or traversing an activation arc, activating one of said branch or leaf DFAs;
and
wherein said processing of the root DFA further includes in response to the next state being an activation state or traversing an activation arc, activating one of said branch or leaf DFAs.

5 more elements

Dependencies are inferred from the claim text.

Hierarchical tree of deterministic finite automata

Life of this patent

Hierarchical tree of deterministic finite automata

Life of this patent

Abstract

Claims20