Generating a non-deterministic finite automata (NFA) graph for regular expression patterns with advanced features
First Claim
1. A method of compiling a pattern into a non-deterministic finite automata (NFA) graph, the method comprising:
- examining the pattern for a plurality of elements and a plurality of node types, each node type corresponding with an element, each element of the pattern to be matched at least zero times, the element representing a character, character class or string;
generating a plurality of nodes of the NFA graph, each node of the plurality of nodes configured to match with one of the plurality of elements and store the node type corresponding to the element, a next node address in the NFA graph, a count value, and the element, wherein the next node address and the count value are applicable as a function of the node type stored and wherein the plurality of nodes generated enable a graph walk engine to identify the pattern in a payload with less nodes relative to another NFA graph representing the pattern and employed by the graph walk engine to identify the pattern in the payload.
6 Assignments
0 Petitions
Accused Products
Abstract
In an embodiment, a method of compiling a pattern into a non-deterministic finite automata (NFA) graph includes examining the pattern for a plurality of elements and a plurality of node types. Each node type can correspond with an element. Each element of the pattern can be matched at least zero times. The method further includes generating a plurality of nodes of the NFA graph. Each of the plurality of nodes can be configured to match for one of the plurality of elements. The node can indicate the next node address in the NFA graph, a count value, and/or node type corresponding to the element. The node can also indicate the element representing a character, character class or string. The character can also be a value or a letter.
-
Citations
60 Claims
-
1. A method of compiling a pattern into a non-deterministic finite automata (NFA) graph, the method comprising:
-
examining the pattern for a plurality of elements and a plurality of node types, each node type corresponding with an element, each element of the pattern to be matched at least zero times, the element representing a character, character class or string; generating a plurality of nodes of the NFA graph, each node of the plurality of nodes configured to match with one of the plurality of elements and store the node type corresponding to the element, a next node address in the NFA graph, a count value, and the element, wherein the next node address and the count value are applicable as a function of the node type stored and wherein the plurality of nodes generated enable a graph walk engine to identify the pattern in a payload with less nodes relative to another NFA graph representing the pattern and employed by the graph walk engine to identify the pattern in the payload. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)
-
-
31. A computer system for compiling a pattern into a non-deterministic finite automata (NFA) graph, the system comprising:
-
a memory; and a processor, the processor coupled to the memory and configured to examine the pattern for a plurality of elements and a plurality of node types, each node type corresponding with an element, each element of the pattern to be matched at least zero times, the element representing a character, character class or string; and wherein the processor is further configured to generate a plurality of nodes of the NFA graph, each node of the plurality of nodes configured to match with one of the plurality of elements and store the node type corresponding to the element, a next node address in the NFA graph, a count value, and the element, wherein the next node address and the count value are applicable as a function of the node type stored and wherein the plurality of nodes generated enable a graph walk engine to identify the pattern in a payload with less nodes relative to another NFA graph representing the pattern and employed by the graph walk engine to identify the pattern in the payload. - View Dependent Claims (32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60)
-
Specification