Method and apparatus for traversing a deterministic finite automata (DFA) graph compression
First Claim
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.
7 Assignments
0 Petitions
Accused Products
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.
-
Citations
19 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
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.
-
Specification