Content search pattern matching using deterministic finite automata (DFA) graphs
First Claim
1. A device comprising:
- at least one network interface;
at least one processor, the at least one processor matching at least one pattern in an input stream of data by traversing a data structure generated from one or more regular expressions for a content processing application, the input stream received via the at least one network interface; and
at least one memory operatively coupled to the at least one processor, the at least one memory storing the generated data structure, the generated data structure including at least one node providing information to perform at least one task based on traversing the at least one node, enabling the at least one processor to generate and check state information at the at least one node for the matching to obviate a post-processing overhead of the at least one pattern matched, improving performance of the at least one processor relative to performing post-processing of results for the content processing application.
7 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.
98 Citations
20 Claims
-
1. A device comprising:
-
at least one network interface; at least one processor, the at least one processor matching at least one pattern in an input stream of data by traversing a data structure generated from one or more regular expressions for a content processing application, the input stream received via the at least one network interface; and at least one memory operatively coupled to the at least one processor, the at least one memory storing the generated data structure, the generated data structure including at least one node providing information to perform at least one task based on traversing the at least one node, enabling the at least one processor to generate and check state information at the at least one node for the matching to obviate a post-processing overhead of the at least one pattern matched, improving performance of the at least one processor relative to performing post-processing of results for the content processing application. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method comprising:
-
matching, by at least one processor operatively coupled to at least one network interface, at least one pattern in an input stream of data by traversing a data structure generated from one or more regular expressions for a content processing application, the input stream received via the at least one network interface; and storing the generated data structure in at least one memory operatively coupled to the at least one processor, the generated data structure including at least one node providing information to perform at least one task based on traversing the at least one node, enabling the at least one processor to generate and check state information at the at least one node for the matching to obviate post-processing overhead of the at least one pattern matched, improving performance of the at least one processor relative to performing post-processing of results for the content processing application. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. 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:
-
match at least one pattern in an input stream of data by traversing the data structure generated from one or more regular expressions for a content processing application, the input stream received via at least one network interface; and store the generated data structure in at least one memory operatively coupled to the processor, the generated data structure including at least one node in the data structure generated, the at least one node providing information to perform at least one task based on traversing the at least one node, enabling the processor to generate and check state information at the at least one node for the matching to obviate post-processing overhead of the at least one pattern matched, improving performance of the processor relative to performing post-processing of results for the content processing application.
-
Specification