Deterministic finite automata (DFA) graph compression

• US 20090138494A1
• Filed: 11/27/2007
• Published: 05/28/2009
• 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
• Granted Patent: US 8,180,803 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 interconnected by arcs; and

pruning the arcs in a manner allowing the plurality of nodes to be interconnected solely by one or more valid arcs, where a current valid arc interconnects a current node to a next node, the current valid arc representing a character match in an expression of a character associated with the current node.

2. The method of claim 1 further comprising:

identifying at least one node, of the plurality of nodes, as a designated node.

3. The method of claim 2 further comprising:

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

4. The method of claim 2 wherein pruning includes:

pruning the valid arcs associated with respective nodes, of the plurality of nodes, that interconnect to a same next node as the designated node for a same character.

5. The method of claim 2 wherein pruning includes:

pruning arcs that point to the designated node.

6. The method of claim 1 further comprising:

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

7. The method of claim 1 further comprising:

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

8. The method of claim 1 further comprising:

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

9. The method of claim 1 wherein a valid arc of the current node comprises a next node pointer to the next node.

10. The method of claim 1 wherein a valid arc of the current node comprises a copy of the character associated with the current node.

11. An apparatus comprising:

a memory unit configured to store a graph of expressions including a plurality of nodes interconnected by arcs; and

a processor configured to prune the arcs in a manner allowing the plurality of nodes to be interconnected solely by one or more valid arcs, where a current valid arc interconnects a current node to a next node, the current valid arc representing a character match in an expression of a character associated with the current node.

12. The apparatus of claim 11 wherein the processor is configured to identify at least one node, of the plurality of nodes, as a designated node.

13. The apparatus of claim 12 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.

14. The apparatus of claim 12 wherein the processor is configured to prune the valid arcs associated with respective nodes, of the plurality of nodes, that interconnect to a same next node as the designated node for a same character.

15. The apparatus of claim 12 wherein the processor is configured to prune valid arcs that point to the designated node.

16. The apparatus of claim 11 further comprising:

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

17. The apparatus of claim 11 further comprising:

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

18. The apparatus of claim 11 further comprising:

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

19. The apparatus of claim 11 wherein a valid arc of the current node comprises a next node pointer to the next node.

20. The apparatus of claim 11 wherein a valid arc of the current node comprises a copy of the character associated with the current node.

21. An apparatus comprising:

means for storing a graph of expressions including a plurality of nodes interconnected by arcs;

means for pruning the arcs in a manner allowing the plurality of nodes to be interconnected solely by one or more valid arcs, where a current valid arc interconnects a current node to a next node, the current valid arc representing a character match in an expression of a character associated with the current node; and

means for traversing the graph.