Optimizing search trees by increasing failure size parameter
View Patent ↗A search tree embodying a plurality of signatures to be compared with an input string of characters and including a number of branches of sequential states originating at a root node, wherein each state comprises a state entry including a failure transition and one or more success transitions, is optimized by selecting a failure size parameter indicating a minimum number of characters to be traversed on the failure transitions and selectively modifying the search tree to create a modified search tree for which all failure transitions to non-root states are characterized by the selected failure size parameter.
1. A method for modifying a search tree embodying a plurality of signatures to be compared with an input string of characters, the search tree including a number of branches of sequential states originating at a root node, wherein each state comprises a state entry including a failure transition and one or more success transitions, the method comprising:
selecting a failure size parameter indicating a minimum number of characters to be traversed on the failure transitions; and
selectively modifying the search tree to create a modified search tree for which all failure transitions to non-root states are characterized by the selected failure size parameter, wherein selecting the failure size parameter (F) comprises:
determining a success size parameter (S) for the search tree, wherein S indicates a maximum number of characters traversed on the success transitions;
specifying a worst-case character processing speed (P) for a finite state machine (FSM) configured to implement the modified search tree; and
calculating F in response to S and P, wherein
F
=
S
*
P
S
P
.
2. The method of claim 1 , wherein the failure size parameter is selected to achieve a specified worst-case character processing speed for a finite state machine (FSM) configured to implement the modified search tree.
3. The method of claim 1 , wherein the selectively modifying comprises:
calculating a removed prefix length (RPL) value for each failure transition;
designating each state for which its failure transition points to a non-root state and has an RPL value that is less than the selected failure size parameter as a violating state; and
modifying the state entries of the violating states.
4. The method of claim 3 , wherein each RPL value indicates a number of characters that are removed from a potentially matching portion of an input string upon traversing the corresponding failure transition.
5. The method of claim 3 , wherein modifying the state entry comprises, for each violating state:
identifying a fail state of the violating state; and
replacing the failure transition of the violating state with the failure transition of the identified fail state.
6. The method of claim 5 , wherein modifying the state entry further comprises, for each violating state:
determining whether the identified fail state includes any success transitions that are not common to the success transitions of the violating state; and
adding the non-common success transitions of the identified fail state to the violating state.
7. The method of claim 5 , wherein modifying the state entry further comprises, for each violating state:
determining whether the identified fail state includes an output code; and
adding the output code to the state entry of the violating state.
8. The method of claim 1 , further comprising:
configuring a finite state machine (FSM) to implement the modified search tree.
9. A method for constructing a finite state machine (FSM) to compare a plurality of signatures with an input string, comprising:
creating a search tree embodying the plurality of signatures, the search tree including a number of branches of sequential states originating at a root node, wherein each state comprises a state entry including a failure transition and one or more success transitions:
selecting a failure size parameter (F) indicating a minimum number of characters to be traversed on the failure transitions, wherein the failure size parameter is selected to achieve a specified worst-case character processing speed (P) for the FSM;
calculating a removed prefix length (RPL) value for each failure transition to a non-root fail state;
comparing the RPL values of the failure transitions with F;
designating each state for which the RPL value of its failure transition is less than F as a violating state; and
modifying the state entries of the violating states so that the RPL value of the failure transition of each violating state becomes greater than or equal to F, wherein selecting F comprises:
determining a success size parameter (S) for the search tree, wherein S indicates a maximum number of characters traversed on the success transitions;
and
calculating F in response to S and P, and wherein
F
=
S
*
P
S
P
.
10. The method of claim 9 , wherein each RPL value indicates a number of characters that are removed from a potentially matching portion of the input string upon traversing the corresponding failure transition.
11. The method of claim 9 , wherein modifying the state entry comprises, for each violating state:
identifying the fail state of the violating state;
if the identified fail state includes any success transitions that are not common to the success transitions of the violating state, adding the non-common success transitions to the state entry of the violating state; and
replacing the failure transition of the violating state with a failure transition of the identified fail state.
12. An optimization engine for modifying a search tree embodying a plurality of signatures to be compared with an input string of characters, the search tree including a number of branches of sequential states originating at a root node, wherein each state comprises a state entry including a failure transition and one or more success transitions, the optimization engine comprising:
means for selecting a failure size parameter indicating a minimum number of characters to be traversed on the failure transitions; and
means for modifying the search tree to create a modified search tree for which all failure transitions to non-root states are characterized by the failure size parameter, wherein the means for selecting the failure size parameter (F) comprises:
means for determining a success size parameter (S) indicating a maximum number of characters traversed on the success transitions;
means for specifying a worst-case character processing speed (P) for a finite state machine (FSM) configured to implement the modified search tree; and
means for calculating F in response to S and P, wherein
F
=
S
*
P
S
P
.
13. The optimization engine of claim 12 , wherein the failure size parameter is selected to achieve a specified worst-case character processing speed for a finite state machine (FSM) configured to implement the modified search tree.