Content Search Mechanism That Uses A Deterministic Finite Automata (DFA) Graph, A DFA State Machine, And A Walker Process
First Claim
1. A network services processor comprising:
- at least one processor configured to search for a match of at least one pattern in an input stream by traversing a data structure generated from one or more regular expressions describing patterns for the search; and
at least one memory operatively coupled to the at least one processor and configured to store the generated data structure, the generated data structure including at least one node having an intelligent node structure providing information on a next node to traverse and enabling the at least one processor to perform at least one task upon reaching the at least one node.
8 Assignments
0 Petitions
Accused Products
Abstract
An improved content search mechanism uses a graph that includes intelligent nodes avoids the overhead of post processing and improves the overall performance of a content processing application. An intelligent node is similar to a node in a DFA graph but includes a command. The command in the intelligent node allows additional state for the node to be generated and checked. This additional state allows the content search mechanism to traverse the same node with two different interpretations. By generating state for the node, the graph of nodes does not become exponential. It also allows a user function to be called upon reaching a node, which can perform any desired user tasks, including modifying the input data or position.
8 Citations
32 Claims
-
1. A network services processor comprising:
-
at least one processor configured to search for a match of at least one pattern in an input stream by traversing a data structure generated from one or more regular expressions describing patterns for the search; and at least one memory operatively coupled to the at least one processor and configured to store the generated data structure, the generated data structure including at least one node having an intelligent node structure providing information on a next node to traverse and enabling the at least one processor to perform at least one task upon reaching the at least one node. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A method comprising:
-
parsing one or more regular expressions describing patterns for searching an input stream for at least one pattern; generating a data structure, from the one or more regular expressions parsed, to enable a search, by at least one processor, for a match of the at least one pattern in the input stream, by traversing, with characters from the input stream, the data structure generated; including at least one node having an intelligent node structure in the data structure generated, the intelligent node structure providing information on a next node to traverse and enabling the at least one processor to perform at least one task upon reaching the at least one node; and storing the data structure generated in at least one memory operatively coupled to the at least one processor. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)
-
-
31. A non-transitory computer-readable medium having stored thereon a sequence of instructions which, when loaded and executed by a processor, causes the processor to:
search for a match of at least one pattern in an input stream by traversing a data structure generated from one or more regular expressions including at least one pattern, the generated data structure including at least one node having an intelligent node structure including information to direct the at least one processor, based on a match result of a given character of the input stream at the at least one node, to traverse to a next node and to perform at least one task upon reaching the at least one node.
-
32. A non-transitory computer-readable medium having stored thereon a sequence of instructions which, when loaded and executed by a processor, causes the processor to:
-
parse one or more regular expressions describing patterns for searching an input stream for at least one pattern; generate a data structure, from the one or more regular expressions parsed, to enable a search, by at least one processor, for a match of the at least one pattern in the input stream, by traversing, with characters from the input stream, the data structure generated; include at least one node having an intelligent node structure in the data structure generated, the intelligent node structure providing information on a next node to traverse and enabling the at least one processor to perform at least one task upon reaching the at least one node; and store the data structure generated in at least one memory operatively coupled to the at least one processor.
-
Specification