Method and apparatus for traversing a deterministic finite automata (DFA) graph compression

• US 20090138440A1
• 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 7,949,683 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 traversing a compressed graph used in performing a search for a match of at least one expression in an input stream is presented. The compressed 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. Each valid arc may comprise a next node pointer, a hash function, and a copy of an associated character. The hash function may be used to manage a retrieval process used by a walker traversing the compressed node. The walker may also use a comparison function to verify the correct arc has been retrieved.

Claims

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

traversing nodes in the graph, the nodes being interconnected through valid arcs, with a walker process to search for an expression in an input stream; and

upon reaching a valid arc, generating a hash value to manage the walker process.

2. The method of claim 1 wherein the graph is a compressed graph including no redundant arcs.

3. The method of claim 1 wherein traversing comprises:

traveling node to node through a valid arc, where a current valid arc of a current node leads to a next node, the current valid arc representing a character match in the expression.

4. The method of claim 3 further comprising:

using a hash function to generate a hash value associated with a next input character; and

indexing with the hash value in the next node to read a next valid arc, the next valid arc including a copy of a next character.

5. The method of claim 4 wherein each valid arc comprises a hash function associated with a next node.

6. The method of claim 4 wherein the hash function is common to all nodes in the graph and is stored in graph metadata.

7. The method of claim 4 further comprising:

comparing the next input character with the copy of the next character in the next valid arc, where the next input character matches a next character of the expression when a comparison match is detected.

8. The method of claim 7 further comprising:

traversing the graph to a designated node when a comparison match is not detected.

9. The method of claim 7 wherein further comprising:

traversing the graph to a designated node associated with a current sub-section of the graph when a comparison match is not detected.

10. A processor comprising:

a memory unit configured to store a graph having a plurality of nodes interconnected through valid arcs; and

a walker configured to walk the plurality of nodes in the graph to search for an expression in an input stream by utilizing a hash value to manage a retrieval function of the walker.

11. The processor of claim 10 wherein the graph is a compressed graph including no redundant arcs.

12. The processor of claim 10 wherein the walker is configured to travel node to node through a valid arc, where a current valid arc of a current node leads to a next node, the current valid arc representing a character match in the expression.

13. The processor of claim 12 wherein the walker is further configured to employ a hash function to generate a hash value associated with a next input character, the walker process configured to index into the next node with the generated hash value, to read a next valid arc, the next valid arc including a copy of a next character.

14. The method of claim 13 wherein each valid arc comprises a hash function associated with a next node.

15. The processor of claim 13 wherein the hash function is to all nodes in the graph and is stored in graph metadata.

16. The processor of claim 10 wherein the walker is configured to compare the next input character with the copy of the next character, where the next input character matches a next character of the expression when a comparison match is detected.

17. The processor of claim 16 wherein the walker is configured to traverse the graph to a designated node when a comparison match is not detected.

18. The processor of claim 16 wherein the walker is configured to traverse the graph to a designated node associated with a current sub-graph when a comparison match is not detected.

19. A processor comprising:

means for storing a compressed graph having a plurality of nodes interconnected through valid arcs; and

means for walking the plurality of nodes in the compressed graph to search for an expression in an input stream.