Traversal with arc configuration information
First Claim
Patent Images
1. A computer implemented method comprising:
- by a processor, given a current node and an arc pointing from the current node to a next node, analyzing arcs in a data structure to determine which of the arcs are valid arcs pointing from the next node;
by the processor, constructing arc configuration information associated with the next node, the arc configuration information limited to only arc configuration information of the next node and representing each valid arc pointing from the next node; and
by the processor, storing the arc configuration information associated with the next node, enabling the arc configuration information to be evaluated and each of the valid arcs pointing from the next node to be identified from the evaluation of the arc configuration information without the next node being read to reduce memory accesses and processing time of the processor.
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.
-
Citations
30 Claims
-
1. A computer implemented method comprising:
-
by a processor, given a current node and an arc pointing from the current node to a next node, analyzing arcs in a data structure to determine which of the arcs are valid arcs pointing from the next node; by the processor, constructing arc configuration information associated with the next node, the arc configuration information limited to only arc configuration information of the next node and representing each valid arc pointing from the next node; and by the processor, storing the arc configuration information associated with the next node, enabling the arc configuration information to be evaluated and each of the valid arcs pointing from the next node to be identified from the evaluation of the arc configuration information without the next node being read to reduce memory accesses and processing time of the processor. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A system for locating an expression in a data structure, the system comprising:
-
a processor executing a walker process configured to traverse the data structure, the data structure including a plurality of interconnected nodes, wherein at least one node includes at least one valid arc; and stored arc configuration information associated with a next node, the at least one valid arc associated with a current node and pointing from the current node to the next node, the arc configuration information limited to only arc configuration information of the next node and representing each valid arc pointing from the next node, the stored arc configuration information enabling each of the valid arcs pointing from the next node to be identified by the processor without the next node being read to reduce memory accesses and processing time of the processor. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. A computer implemented method for traversing a data structure comprising:
-
traversing nodes in the data structure, 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 arc configuration information associated with the next node, the arc configuration information limited to only arc configuration information of the next node and representing each valid arc 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.
-
-
26. A computer implemented method for traversing a data structure comprising:
traversing nodes in the data structure with a processor coupled to a memory and configured to traverse the nodes based on arc configuration information associated with a next node and stored in the memory, the arc configuration information limited to only arc configuration information of the next node and representing each valid arc pointing from the next node, to search for an expression in an input stream, each valid arc associated with a current character of the input stream. - View Dependent Claims (27, 28, 29, 30)
Specification