Method and apparatus for traversing a compressed deterministic finite automata (DFA) graph
First Claim
1. A method for traversing a compressed deterministic finite automata-based graph comprising:
- in a processor;
traversing nodes in the compressed graph, the nodes being interconnected through valid arcs, by traveling node to node through a valid arc, where a current valid arc of a current node leads to a next node with a walker process to search for an expression in an input stream, the compressed graph having no redundant arcs, and each valid arc of the compressed graph representing a character match in the expression; and
using a hash value generated from an input character to index in the current node and to read the current valid arc associated with the input character;
using a hash function associated with the current valid arc to generate a hash value from a next input character; and
indexing in the next node using the hash value generated from the next input character to read a next valid arc 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.
115 Citations
13 Claims
-
1. A method for traversing a compressed deterministic finite automata-based graph comprising:
-
in a processor; traversing nodes in the compressed graph, the nodes being interconnected through valid arcs, by traveling node to node through a valid arc, where a current valid arc of a current node leads to a next node with a walker process to search for an expression in an input stream, the compressed graph having no redundant arcs, and each valid arc of the compressed graph representing a character match in the expression; and using a hash value generated from an input character to index in the current node and to read the current valid arc associated with the input character; using a hash function associated with the current valid arc to generate a hash value from a next input character; and indexing in the next node using the hash value generated from the next input character to read a next valid arc to manage the walker process. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A processor comprising:
-
a memory unit configured to store a compressed graph having a plurality of nodes interconnected through valid arcs and no redundant arcs, each valid arc of the compressed graph representing a character match in an expression; and a walker configured to walk the plurality of nodes in the compressed graph by traveling node to node through a valid arc, where a current valid arc of a current node leads to a next node, to search for an expression in an input stream by i) using a hash value generated from the input character to index in the current node and to read the current valid arc associated with the input character, ii) using a hash function associated with the current valid arc to generate a hash value from a next input character, and iii) indexing in the next node using the hash value generated from the next input character to read a next valid arc to manage a retrieval function of the walker. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A processor comprising:
-
means for storing a compressed graph having a plurality of nodes interconnected through valid arcs and no redundant arcs, each valid arc of the compressed graph representing a character match in an expression; and means for walking the plurality of nodes in the compressed graph by traveling node to node through a valid arc, where a current valid arc of a current node leads to a next node, to search for the expression in an input stream by i) using a hash value generated from the input character to index in the current node and to read the current valid arc associated with the input character, ii) using a hash function associated with the current valid arc to generate a hash value from a next input character, and iii) indexing in the next node using the hash value generated from the next input character to read a next valid arc.
-
Specification