Method and apparatus for constructing a failure tree from a search tree
AssigneeNetLogic Microsystems, Inc.
InventorsPankaj Gupta, Srinivasan Venkatachary
Life of this patent
Estimating the term…
Abstract
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.
Claims33
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.
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.
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.
Dependencies are inferred from the claim text.