Granted Patent B1

US 7,991,723 · App. 11/778,546 · Granted Aug 2, 2011

Abstract

Claims (30)

1. A computer-implemented method to optimize data pattern analysis, comprising:

determining a number of possible transitions from a current node to one or more subsequent nodes representing one or more sequences of data patterns, each of the current node and subsequent nodes being associated with a deterministic finite automaton (DFA) state;

dynamically allocating a data structure for each of the subsequent nodes for storing information associated with each of the subsequent nodes, wherein data structures for the subsequent nodes are allocated in a logical array maintained by a data structure corresponding to the current node if the number of possible transitions is greater than a predetermined threshold to improve performance; and

determining whether each of the subsequent nodes includes a single child node, wherein the data structures for the subsequent nodes are allocated in an array maintained by a data structure corresponding to the current node if each of the subsequent nodes includes a single child node.

2. The method of claim 1 , wherein each element of the logical array is directly accessible from the data structure corresponding to the current node.

3. The method of claim 1 , wherein if the number of transitions is less than or equal to a predetermined threshold, the data structures for the subsequent nodes are allocated in a chain manner with a reference maintained by the data structure corresponding to the current node to reduce memory usage.

4. The method of claim 3 , wherein the data structures for the subsequent nodes are allocated in a linked-list manner, wherein each of the data structures includes a first reference pointer linked to a previous data structure and a second reference pointer linked to a next data structure.

5. The method of claim 1 , further comprising allocating an array for storing matched data for the subsequent nodes and accessible by the data structure of the current node, each element of the array corresponding to one subsequent node.

6. A machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform a method to optimize data pattern analysis, the method comprises:

determining a number of possible transitions from a current node to one or more subsequent nodes representing one or more sequences of data patterns, each of the current node and subsequent nodes being associated with a deterministic finite automaton (DFA) state;

dynamically allocating a data structure for each of the subsequent nodes for storing information associated with each of the subsequent nodes, wherein data structures for the subsequent nodes are allocated in a logical array maintained by a data structure corresponding to the current node if the number of possible transitions is greater than a predetermined threshold to improve performance; and

determining whether each of the subsequent nodes includes a single child node, wherein the data structures for the subsequent nodes are allocated in an array maintained by a data structure corresponding to the current node if each of the subsequent nodes includes a single child node.

7. The machine-readable medium of claim 6 , wherein each element of the logical array is directly accessible from the data structure corresponding to the current node.

8. The machine-readable medium of claim 6 , wherein if the number of transitions is less than or equal to a predetermined threshold, the data structures for the subsequent nodes are allocated in a chain manner with a reference maintained by the data structure corresponding to the current node to reduce memory usage.

9. The machine-readable medium of claim 8 , wherein the data structures for the subsequent nodes are allocated in a linked-list manner, wherein each of the data structures includes a first reference pointer linked to a previous data structure and a second reference pointer linked to a next data structure.

10. The machine-readable medium of claim 6 , wherein the method further comprises allocating an array for storing matched data for the subsequent nodes and accessible by the data structure of the current node, each element of the array corresponding to one subsequent node.

11. A data processing system, comprising:

a processor;

a memory for storing instructions, which when executed from the memory, cause the processor to

determine a number of possible transitions from a current node to one or more subsequent nodes representing one or more sequences of data patterns, each of the current node and subsequent nodes being associated with a deterministic finite automaton (DFA) state,

dynamically allocate a data structure for each of the subsequent nodes for storing information associated with each of the subsequent nodes, wherein data structures for the subsequent nodes are allocated in a logical array maintained by a data structure corresponding to the current node if the number of possible transitions is greater than a predetermined threshold to improve performance, and

determine whether each of the subsequent nodes includes a single child node, wherein the data structures for the subsequent nodes are allocated in an array maintained by a data structure corresponding to the current node if each of the subsequent nodes includes a single child node.

12. A computer-implemented method to optimize data pattern analysis, comprising:

determining a relationship of each of one or more child nodes transitioned from a root parent node, the relationship including a distance between each of the child nodes and the root parent node, the root parent node and child nodes representing one or more sequences of data patterns, wherein each of the root parent node and child nodes is associated with a deterministic finite automaton (DFA) state; and

dynamically allocating a data structure for each of the child nodes for storing information associated with each of the child nodes, wherein a data structure for a child node is allocated either in an array or in a linked-list manner dependent upon the relationship between the child node and the root parent node, wherein the data structure for the child node is allocated in an array if a distance between the child node and the root parent node is less than a predetermined threshold.

13. The method of claim 12 , wherein the distance between the child node and the root parent node is represented by a number of intermediate nodes between the child node and the root parent node.

14. A machine-readable medium having instructions stored therein which when executed by a machine, cause the machine to perform a method to optimize data pattern analysis, the method comprising:

determining a relationship of each of one or more child nodes transitioned from a root parent node, the relationship including a distance between each of the child nodes and the root parent node, the root parent node and child nodes representing one or more sequences of data patterns, wherein each of the root parent node and child nodes is associated with a deterministic finite automaton (DFA) state; and

dynamically allocating a data structure for each of the child nodes for storing information associated with each of the child nodes, wherein a data structure for a child node is allocated either in an array or in a linked-list manner dependent upon the relationship between the child node and the root parent node, wherein the data structure for the child node is allocated in an array if a distance between the child node and the root parent node is less than a predetermined threshold.

15. The machine-readable medium of claim 14 , wherein the distance between the child node and the root parent node is represented by a number of intermediate nodes between the child node and the root parent node.

Assignments (24)