Data pattern analysis using optimized deterministic finite automation
View Patent ↗Techniques for data pattern analysis using deterministic finite automaton are described herein. In one embodiment, a number of transitions from a current node to one or more subsequent nodes representing one or more sequences of data patterns is determined, where each of the current node and subsequent nodes is associated with a deterministic finite automaton (DFA) state. A data structure is dynamically allocated for each of the subsequent nodes for storing information associated with each of the subsequent nodes, where data structures for the subsequent nodes are allocated in an array maintained by a data structure corresponding to the current node if the number of transitions is greater than a predetermined threshold. Other methods and apparatuses are also described.
1. A method for data pattern analysis, the method comprising:
a processor executing instructions residing in memory, the processor determining a number of 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; and
the processor dynamically allocating a data structure for each of the subsequent nodes for storing information associated with each of the subsequent nodes in memory, wherein data structures for the subsequent nodes are dynamically allocated a first type of data structure to optimize performance when the number of transitions is greater than a predetermined threshold, and wherein data structures for the subsequent nodes are dynamically allocated a second type of data structure to optimize memory utilization when the number of transitions is less than or equal to the predetermined threshold.
2. The method of claim 1 , wherein the data structures for the subsequent nodes corresponding to the first type of data structure is an array maintained by a data structure corresponding to the current node, and wherein the data structures for the subsequent nodes corresponding to the second type of data structure are dynamically allocated in a chain manner with a reference maintained by the data structure corresponding to the current node.
3. The method of claim 2 , wherein each element of the array is directly accessible from the data structure corresponding to the current node.
4. The method of claim 1 , wherein the data structures for the subsequent nodes corresponding to the first type of data structure is an array maintained by a data structure corresponding to the current node, and wherein the data structures for the subsequent nodes corresponding to the second type of data structure are dynamically allocated in a linked-list manner, wherein each of the data structures dynamically allocated in a linked-list manner 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 determining whether each of the subsequent nodes includes a single child node, wherein the data structures for the subsequent nodes corresponding to the first type of data structure are allocated in an array maintained by a data structure corresponding to the current node when each of the subsequent nodes includes a single child node.
6. The method of claim 5 , 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.
7. A non-transitory computer readable storage medium having embodied thereon a program executable by a processor to perform a method for data pattern analysis, the method comprising:
determining a number of 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; and
dynamically allocating a data structure for each of the subsequent nodes for storing information associated with each of the subsequent nodes in memory, wherein data structures for the subsequent nodes are dynamically allocated a first type of data structure to optimize performance when the number of transitions is greater than a predetermined threshold and wherein data structures for the subsequent nodes are dynamically allocated a second type of data structure to optimize memory utilization when the number of transitions is less than or equal to the predetermined threshold.
8. The non-transitory computer readable storage medium of claim 7 , wherein the data structures for the subsequent nodes corresponding to the first type of data structure is an array maintained by a data structure corresponding to the current node, and wherein the data structures for the subsequent nodes corresponding to the second type of data structure are dynamically allocated in a chain manner with a reference maintained by the data structure corresponding to the current node.
9. The non-transitory computer readable storage medium of claim 8 , wherein each element of the array is directly accessible from the data structure corresponding to the current node.
10. The non-transitory computer readable storage medium of claim 7 , wherein the data structures for the subsequent nodes corresponding to the first type of data structure is an array maintained by a data structure corresponding to the current node, and wherein the data structures for the subsequent nodes corresponding to the second type of data structure are dynamically allocated in a linked-list manner, wherein each of the data structures dynamically allocated in a linked-list manner includes a first reference pointer linked to a previous data structure and a second reference pointer linked to a next data structure.
11. The non-transitory computer readable storage medium of claim 7 , wherein the method further comprising determining whether each of the subsequent nodes includes a single child node, wherein the data structures for the subsequent nodes corresponding to the first type of data structure are allocated in an array maintained by a data structure corresponding to the current node when each of the subsequent nodes includes a single child node.
12. The non-transitory computer readable storage medium of claim 11 , wherein the method 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.
13. A data processing system, the system comprising:
a processor; and
a memory for storing instructions, which when executed from the memory, cause the processor to determine a number of 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, and the processor dynamically allocating a first type of data structure to optimize performance or a second type of data structure to optimize memory utilization for each of the subsequent nodes for storing information associated with each of the subsequent nodes, wherein data structures for the subsequent nodes corresponding to the first data structure are dynamically allocated in an array maintained by a data structure corresponding to the current node when the number of transitions is greater than a predetermined threshold, and wherein data structures for the subsequent nodes corresponding to the second data structure are dynamically allocated in a chain manner or in a linked-list manner when the number of transitions is less than or equal to the predetermined threshold.
14. A method for data pattern analysis, the method comprising:
a processor executing instructions residing in memory, the processor determining whether each of one or more subsequent nodes transitioned from a current node includes a single child node, the current node and subsequent nodes representing one or more sequences of data patterns, wherein each of the current node and subsequent nodes is associated with a deterministic finite automaton (DFA) state; and
the processor dynamically allocating a data structure for each of the subsequent nodes for storing information associated with each of the subsequent nodes in memory, wherein data structures for the subsequent nodes are dynamically allocated in an array to optimize performance wherein the data structures in the array are maintained by a data structure corresponding to the current node when each of the subsequent nodes includes a single child node, and wherein data structures for the subsequent nodes are dynamically allocated a second type of data structure to optimize memory utilization when the number of transitions is less than or equal to the predetermined threshold.
15. The method of claim 14 , wherein the data structures for the subsequent nodes corresponding to the second type of data structure are dynamically allocated in a chain manner with a reference maintained by the data structure corresponding to the current node.
16. The method of claim 14 , wherein the data structures for the subsequent nodes corresponding to the second type of data structure are dynamically 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.
17. The method of claim 14 , wherein each element of the array is directly accessible from the data structure corresponding to the current node.
18. A non-transitory computer readable storage medium for storing instructions embodied thereon a program executed by a processor to perform a method for data pattern analysis, the method comprising:
determining whether each of one or more subsequent nodes transitioned from a current node includes a single child node, the current node and subsequent nodes representing one or more sequences of data patterns, wherein each of the current node and subsequent nodes is associated with a deterministic finite automaton (DFA) state;
determining a number of transitions from the current node to the one or more subsequent nodes representing one or more sequences of data patterns; and
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 dynamically allocated in an array to optimize performance, the data structures for the subsequent nodes maintained by a data structure corresponding to the current node when each of the subsequent nodes includes a single child node, and when the number of transitions is greater than a predetermined threshold and wherein data structures for the subsequent nodes are dynamically allocated a second type of data structure to optimize memory utilization when the number of transitions is less than or equal to the predetermined threshold.
19. The non-transitory computer readable storage medium of claim 18 , wherein the data structures for the subsequent nodes corresponding to the second type of data structure are dynamically allocated in a chain manner with a reference maintained by the data structure corresponding to the current node.
20. The non-transitory computer readable storage medium of claim 19 , wherein the data structures for the subsequent nodes corresponding to the second type of data structure are dynamically 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.
21. A method for data pattern analysis, the method comprising:
a processor executing instruction residing in memory, the processor determining a relationship of each of one or more child nodes transitioned from a root parent node include 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
the processor dynamically allocating a data structure for each of the child nodes for storing information associated with each of the child nodes in memory, wherein a data structure for a child node is dynamically allocated in an array to optimize performance when the distance between the child node and the root parent node is less than a predetermined threshold or in a linked-list manner to optimize memory utilization when the distance between the child node and the root parent node is greater than or equal to a predetermined threshold.
22. The method of claim 21 , 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.
23. A non-transitory computer readable storage medium having embodied thereon a program executable cause the to perform a method for data pattern analysis, the method comprising:
determining a relationship of each of one or more child nodes transitioned from a root parent node include 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 to optimize performance when the distance between the child node and the root parent node is less than a predetermined threshold or in a linked-list manner to optimize memory utilization when the distance between the child node and the root parent node is greater than or equal to a predetermined threshold.
24. The non-transitory computer readable storage medium of claim 23 , 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.