Method and apparatus for traversing a compressed deterministic finite automata (DFA) graph
View Patent ↗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.
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.
2. The method of claim 1 wherein each valid arc comprises a hash function associated with a next node.
3. The method of claim 1 wherein the hash function is common to all nodes in the graph and is stored in graph metadata.
4. The method of claim 1 further comprising:
comparing the next input character with a character copy in the next valid arc, where the next input character matches a next character of the expression when a comparison match is detected.
5. The method of claim 4 further comprising:
traversing the graph to a designated node when a comparison match is not detected.
6. The method of claim 4 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.
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.
8. The processor of claim 7 wherein each valid arc comprises a hash function associated with a next node.
9. The processor of claim 7 wherein the hash function is common to all nodes in the graph and is stored in graph metadata.
10. The processor of claim 7 wherein the walker is configured to compare the next input character with a character copy in the next valid arc, where the next input character matches a next character of the expression when a comparison match is detected.
11. The processor of claim 10 wherein the walker is configured to traverse the graph to a designated node when a comparison match is not detected.
12. The processor of claim 10 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.
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.