Method and apparatus for constructing a failure tree from a search tree
View Patent ↗A method for representing a search tree embodying a plurality of signatures to be searched for in an input string of characters constructs a failure tree in which the states are re-organized in levels according to the number of failure transitions between each state and the root node of the search tree.
1. A method for representing a state diagram embodying a plurality of signatures to be searched for in an input string of characters, comprising:
selecting a goto-failure tree embodying the signatures and including a plurality of branches of sequential states extending from a root node and connected by a number of goto transitions, wherein each non-root state in the goto-failure tree has a failure transition to a corresponding fail state;
identifying each sequence of states in the selected goto-failure tree that are connected by a chain of failure transitions; and
constructing a failure tree in response to the identifying, wherein the failure tree includes all the states of the goto-failure tree organized in a plurality of depth levels according to a number of failure transitions between each state and the root node.
2. The method of claim 1 , wherein the states of the failure tree are organized without regard to the goto transitions of the selected goto-failure tree.
3. The method of claim 1 , wherein the failure tree does not include any goto transitions.
4. The method of claim 1 , wherein all the states in any one level of the failure tree fail directly to the states in an adjacent lower level of the failure tree.
5. The method of claim 1 , wherein a root level of the failure tree consists of the root node, a first level of the failure tree consists of all states that fail directly to the root node, and a second level of the failure tree consists of all states that fail directly to the states in the first level.
6. The method of claim 1 , wherein the constructing comprises:
placing the root node in a root level of the failure tree;
placing all states that fail directly to the root node in a first level of the failure tree; and
placing all states that fail directly to states in the first level of the failure tree in a second level of the failure tree.
7. The method of claim 1 , further comprising:
assigning a unique state code to each of the states according to the chains of failure transitions.
8. The method of claim 7 , wherein the unique state codes are assigned without regard to the goto transitions of the goto-failure tree.
9. The method of claim 7 , further comprising:
storing the unique state codes in a ternary content addressable memory, wherein a portion of at least one state code includes ternary don't care bits.
10. The method of claim 1 , further comprising:
selecting a maximum chain length (MCL) value; and
limiting the number of states in the failure chains of the failure tree to the selected MCL value.
11. The method of claim 1 , wherein the states of the goto-failure tree are organized in depth levels according to the number of goto transitions between the root node and each state in the goto-failure tree.
12. The method of claim 11 , wherein a root level of the goto-failure tree consists of the root node, a first level of the goto-failure tree consists of all states having direct goto transitions from the root node, and a second level of the goto-failure tree consists of all states having direct goto transitions from the states in the first level.
13. The method of claim 11 , wherein each fail state represents an accumulated prefix of the non-root state that is connected to the fail state by the corresponding failure transition.
14. The method of claim 11 , wherein the selected goto-failure tree does not include any goto transitions between states in different branches.
15. A method for representing a state diagram embodying a plurality of signatures to be searched for in an input string of characters, comprising:
selecting a goto-failure tree embodying the signatures and including a plurality of branches of sequential states extending from a root node and connected by a number of goto transitions, wherein each non-root state in the goto-failure tree has a failure transition to a corresponding fail state;
identifying each sequence of states in the selected goto-failure tree that are connected by a chain of failure transitions; and
re-organizing the states of the goto-failure tree in a plurality of depth levels according to the chains of failure transitions.
16. The method of claim 15 , wherein the re-organizing comprises:
constructing a failure tree including all the states of the goto-failure tree and embodying the failure transitions, wherein the failure tree does not include any of the goto transitions.
17. The method of claim 16 , wherein the states of the failure tree are organized without regard to the goto transitions of the selected goto-failure tree.
18. The method of claim 16 , wherein all the states in any one level of the failure tree fail directly to the states in an adjacent lower level of the failure tree.
19. The method of claim 16 , wherein a root level of the failure tree consists of the root node, a first level of the failure tree consists of all states that fail directly to the root node, and a second level of the failure tree consists of all states that fail directly to the states in the first level.
20. The method of claim 16 , wherein the constructing comprises:
placing the root node in a root level of the failure tree;
placing all states that fail directly to the root node in a first level of the failure tree; and
placing all states that fail directly to states in the first level of the failure tree in a second level of the failure tree.
21. The method of claim 16 , further comprising:
selecting a maximum chain length (MCL) value; and
limiting the number of states in the failure chains of the failure tree to the selected MCL value.
22. The method of claim 15 , further comprising:
assigning a unique state code to each of the states according to the chains of failure transitions.
23. The method of claim 22 , wherein the unique state codes are assigned without regard to the goto transitions of the goto-failure tree.
24. A search tree optimization engine for re-organizing a state diagram representative of a plurality of signatures to be searched for in an input string of characters, comprising:
means for selecting a goto-failure tree embodying the signatures and including a plurality of branches of sequential states extending from a root node and connected by a number of goto transitions, wherein each non-root state in the goto-failure tree has a failure transition to a corresponding fail state;
means for identifying each sequence of states in the selected goto-failure tree that are connected by a chain of failure transitions; and
means for constructing a failure tree including all the states of the goto-failure tree organized in depth levels according to a number of failure transitions between each state and the root node.
25. The engine of claim 24 , wherein the states of the failure tree are organized without regard to the goto transitions of the selected goto-failure tree.
26. The engine of claim 24 , wherein the failure tree does not include any goto transitions.
27. The engine of claim 24 , wherein all the states in any one level of the failure tree fail directly to the states in an adjacent lower level of the failure tree.
28. The engine of claim 24 , wherein a root level of the failure tree consists of the root node, a first level of the failure tree consists of all states that fail directly to the root node, and a second level of the failure tree consists of all states that fail directly to the states in the first level.
29. The engine of claim 24 , wherein the means for constructing comprises:
means for placing the root node in a root level of the failure tree;
means for placing all states that fail directly to the root node in a first level of the failure tree; and
means for placing all states that fail directly to states in the first level of the failure tree in a second level of the failure tree.
30. The engine of claim 24 , further comprising:
means for assigning a unique state code to each of the states according to the chains of failure transitions.
31. The engine of claim 30 , wherein the unique state codes are assigned without regard to the goto transitions of the goto-failure tree.
32. The engine of claim 30 , further comprising:
means for storing the unique state codes in a ternary content addressable memory.
33. The engine of claim 24 , further comprising:
means for selecting a maximum chain length (MCL) value; and
means for limiting the number of states in the failure chains of the failure tree to the selected MCL value.