Hierarchical tree of deterministic finite automata

• US 20060242123A1
• Filed: 04/23/2005
• Published: 10/26/2006
• Est. Priority Date: 04/23/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Williams, John J. Jr.
• Granted Patent: US 7,765,183 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques

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.

Claims

1. 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.

2. The apparatus of claim 1, wherein each of said leaf DFAs includes a terminating state or arc;

wherein said means for traversing the hierarchical DFA includes means for terminating the traversing of a particular one of said leaf DFAs in response to reaching or traversing a corresponding terminating state or arc in said particular one of said leaf DFAs.

3. The apparatus of claim 2, wherein the root DFA is always active and each of said leaf DFAs is intermittently active.

4. The apparatus of claim 1, wherein the hierarchical DFA includes one or more branch DFAs;

wherein each of said one or more branch DFAs includes an activation state or arc for causing activation of at least one of said leaf DFAs.

5. The apparatus of claim 4, wherein each of said leaf DFAs and said branch DFAs includes a terminating state or arc;

wherein said means for traversing the hierarchical DFA includes means for terminating the traversing of a particular one of said leaf DFAs and said branch DFAs in response to a corresponding terminating state or arc being reached or traversed in said particular one of said leaf DFAs and said branch DFAs.

6. The apparatus of claim 5, wherein the root DFA is always active and each of said branch DFAs and leaf DFAs is intermittently active.

7. 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.

8. The method of claim 7, wherein said activating the particular one of said leaf DFAs is performed only if the particular one is currently inactive.

9. The method of claim 7, including generating the hierarchical DFA, wherein said generating the hierarchical DFA includes:

determining the root DFA based on at least one character from the beginning of each of said regular expressions; and

determining said leaf DFAs corresponding to portions of said regular expressions following said at least one character and linking each of said leaf DFAs to the root DFA in a manner to identify when to activate said each of said leaf DFAs, said each of said leaf DFAs including at least one final state or arc and at least one termination state or arc.

10. The method of claim 9, wherein within at least one of said leaf DFAs, the final state and the termination state are the same state or the final arc and the terminating arc are the same arc.

11. The method of claim 9, wherein within at least one of said leaf DFAs, the final state and the termination state are different states or the final and terminating arcs are different arcs.

12. 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.

13. The method of claim 12, wherein said activating one of said branch or leaf DFAs is performed only if said one of said branch or leaf DFAs is currently inactive.

14. The method of claim 12, including generating the hierarchical DFA, wherein said generating the hierarchical DFA includes:

determining a root DFA based on at least one beginning character from each of said regular expressions; and

determining said branch DFAs and said leaf DFAs corresponding to portions of said regular expressions following said at least one beginning character and linking each of said branch DFAs and said leaf DFAs to the root DFA in a manner to identify when to activate said each of said branch DFAs and said leaf DFAs, said each of said branch DFAs and said leaf DFAs including at least one final state or arc, and at least one termination state or arc.

15. The method of claim 14, wherein within at least one of said branch DFAs and said leaf DFAs, the final state and the termination state are the same state, or the final arc and the termination arc are the same arc.

16. The method of claim 14, wherein within at least one of said branch DFAs and said leaf DFAs, the final state and the termination state are different states, or the final arc and the termination arc are different arcs.

17. A method for producing a hierarchical deterministic finite automata (DFA) from a plurality of regular expressions, the method comprising:

determining a root DFA based on at least one beginning character from each of said regular expressions; and

determining one or more leaf DFAs corresponding to one or more characters immediately following said at least one beginning character of at least one of said regular expressions and linking each of said leaf DFAs to the root DFA in a manner to identify when to activate said each of said leaf DFAs, said each of said leaf DFAs including at least one final state and at least one termination state.

18. A method for producing a hierarchical deterministic finite automata (DFA) from a plurality of regular expressions, the method comprising:

determining a root DFA based on at least one beginning character from each of said regular expressions; and

determining one or more branch DFAs and one or more leaf DFAs corresponding to one or more characters immediately following said at least one beginning character of at least one of said regular expressions and linking each of said branch DFAs and said leaf DFAs to the root DFA in a manner to identify when to activate said each of said branch DFAs and said leaf DFAs, said each of said branch DFAs and said leaf DFAs including at least one final state and at least one termination state.

19. A method for producing a hierarchical deterministic finite automata (DFA) from a plurality of regular expressions, the method comprising:

determining a root DFA based on at least one beginning character from each of said regular expressions; and

determining one or more leaf DFAs corresponding to portions of said regular expressions following said at least one beginning character and linking each of said leaf DFAs to the root DFA in a manner to identify when to activate said each of said leaf DFAs, said each of said leaf DFAs including at least one final state and at least one termination state.

20. A method for producing a hierarchical deterministic finite automata (DFA) from a plurality of regular expressions, the method comprising:

determining a root DFA based on at least one beginning character from each of said regular expressions; and

determining one or more branch DFAs and one or more leaf DFAs corresponding to portions of said regular expressions following said at least one beginning character from each of said regular expressions and linking each of said branch DFAs and said leaf DFAs to the root DFA in a manner to identify when to activate said each of said branch DFAs and said leaf DFAs, said each of said branch DFAs and said leaf DFAs including at least one final state and at least one termination state.