Traversal With Arc Configuration Information

摘要

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.

主权项

1. A computer implemented method comprising:
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; constructing arc configuration information associated with the next node, the arc configuration information representing the valid arcs pointing from the next node; and storing the arc configuration information associated with the next node, enabling the arc configuration information to be evaluated and 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.