Deterministic finite automata graph traversal with nodal bit mapping
First Claim
Patent Images
1. A computer implemented method for generating a bit map for a deterministic finite automata based graph, the method comprising:
- given a current node and an arc pointing from the current node to a next node, analyzing valid arcs in the graph to determine which of the valid arcs are valid arcs pointing from the next node;
constructing a bit map associated with the arc pointing from the current node to the next node, the bit map representing the valid arcs pointing from the next node; and
storing the bit map representing the valid arcs pointing from the next node in the arc pointing from the current node to the next node to enable the bit map to be evaluated and the valid arcs pointing from the next node to be identified from the evaluation of the bit map without the next node being read.
7 Assignments
0 Petitions
Accused Products
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 may also include a nodal bit map including structural information of a node to which the valid arc points to. A walker process may utilize the nodal bit map to determine if a memory access is necessary. The nodal bit map reduces the number of external memory access and therefore reduces system run time.
117 Citations
41 Claims
-
1. A computer implemented method for generating a bit map for a deterministic finite automata based graph, the method comprising:
-
given a current node and an arc pointing from the current node to a next node, analyzing valid arcs in the graph to determine which of the valid arcs are valid arcs pointing from the next node; constructing a bit map associated with the arc pointing from the current node to the next node, the bit map representing the valid arcs pointing from the next node; and storing the bit map representing the valid arcs pointing from the next node in the arc pointing from the current node to the next node to enable the bit map to be evaluated and the valid arcs pointing from the next node to be identified from the evaluation of the bit map without the next node being read. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A system for locating an expression in a searchable deterministic finite automata based graph, the system comprising:
-
a processor executing a walker process configured to traverse the searchable graph, the graph including a plurality of interconnected nodes, where at least one node includes at least one valid arc; and a bit map stored in an arc, the arc associated with a current node and pointing from the current node to a next node, the bit map representing valid arcs pointing from the next node. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40)
-
-
41. A computer implemented method for traversing a deterministic finite automata-based graph comprising:
-
traversing nodes in the graph, with a walker process, to search for an expression in an input stream; retrieving an arc associated with a current character of the input stream, the arc pointing from a current node to a next node; reading a bit map associated with the arc pointing from the current node to the next node and stored in the arc, the bit map representing valid arcs pointing from the next node; determining if a next valid arc associated with a next character of the input stream exists in the next node based on a search indication provided by the reading; and accessing in memory the next valid arc associated with the next character if the search indication is positive.
-
Specification