Deterministic finite automata (DFA) graph compression

• US 8,180,803 B2
• Filed: 11/27/2007
• Issued: 05/15/2012
• Est. Priority Date: 11/27/2007
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan
• Primary Examiner(s): LY, CHEYNE D
• Application Number:
  US11/986,970
• Publication Number:
  US 20090138494A1
• Time in Patent Office: 1,631 Days
• Field of Search: 707/798, 709/224, 709/227, 709/228, 709/231
• US Class Current: 707/798
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

An apparatus, and corresponding method, for generating a graph used in performing a search for a match of at least one expression in an input stream is presented. The graph includes a number of interconnected nodes connected solely by valid arcs. A valid arc of a current node represents a character match in an expression of a character associated with the current node. Arcs which are not valid may be pruned. Non-valid arcs may include arcs which point back to a designated node(s), or arcs that point to the same next node as the designated node(s) for the same character. Typically, the majority of arcs associated with a node are non-valid. Therefore, pruning the non-valid arcs may greatly reduce graph storage requirements.

Claims

1. A computer implemented method for generating a deterministic finite automata-based graph comprising:

storing a graph of expressions in memory, the graph including a plurality of nodes, each node having arcs, each arc being for a character and connecting a node to a next node;

during compilation of the graph;

identifying at least one node of the plurality of nodes in the graph as a designated node;

for each node of the plurality of nodes, except the designated node, comparing each arc of a subject node having a plurality of arcs with each arc of the designated node to find an arc of the subject node that is for an identical character and that connects the subject node to an identical next node in the graph as an arc of the designated node, the arc found being called a non-unique arc; and

removing the non-unique arc from the subject node without reducing the number of nodes in the plurality of nodes.

2. The method of claim 1 further comprising:

assigning the at least one designated node to be associated with at least one sub-section of the graph.

3. The method of claim 1 wherein removing includes:

removing arcs that point to the designated node.

4. The method of claim 1 further comprising:

traversing the graph with a walker process managed by a hash function.

5. The method of claim 1 further comprising:

traversing the graph with a walker process configured to obtain at least two arcs from memory during a single access.

6. The method of claim 1 further comprising:

traversing the graph with a walker process configured to obtain an arc based on a location table.

7. The method of claim 1 wherein an arc of a node comprises a next node pointer to the next node.

8. The method of claim 1 wherein an arc of a node comprises a copy of the character associated with the node.

9. An apparatus comprising:

a memory unit configured to store a graph of expressions including a plurality of nodes, each node having arcs, each arc being for a character and connecting a node to a next node; and

a processor configured to;

during compilation of the graph;

identify at least one node of the plurality of nodes in the graph as a designated node;

for each node of the plurality of nodes, except the designated node, compare each arc of a subject node having a plurality of arcs with each arc of the designated node to find an arc of the subject node that is for an identical character and that connects the subject node to an identical next node in the graph as an arc of the designated node, the arc found being called a non-unique arc; and

remove the non-unique arc from the subject node without reducing the number of nodes in the plurality of nodes.

10. The apparatus of claim 9 wherein the processor is further configured to assign the at least one designated node to be associated with at least one sub-section of the graph.

11. The apparatus of claim 9 wherein the processor is configured to remove arcs that point to the designated node.

12. The apparatus of claim 9 further comprising:

a walking unit configured to traverse the graph, the walking unit managed by a hash function.

13. The apparatus of claim 9 further comprising:

a walking unit configured to traverse the graph by obtaining at least two arcs from memory during a single access.

14. The apparatus of claim 9 further comprising:

a walking unit configured to traverse the graph by obtaining an arc based on a location table.

15. The apparatus of claim 9 wherein an arc of a node comprises a next node pointer to the next node.

16. The apparatus of claim 9 wherein an arc of a node comprises a copy of the character associated with the node.

17. A non-transitory computer usable medium storing instructions for generating a deterministic finite automata-based graph that, when executed by a computer, cause the computer to:

store a graph of expressions in memory, the graph including a plurality of nodes, each node having arcs, each arc being for a character and connecting a node to a next node;

during compilation of the graph;

identify at least one node of the plurality of nodes in the graph as a designated node;

for each node of the plurality of nodes, except the designated node, compare each arc of a subject node having a plurality of arcs with each arc of the designated node to find an arc among the plurality of arcs of the subject node that is for an identical character and that connects the subject node to an identical next node in the graph as an arc of the designated node, the arc found being called a non-unique arc; and

remove the non-unique arc from the subject node without reducing the number of nodes in the plurality of nodes.