Granted Patent B1

US 7,860,849 · App. 11/689,437 · Granted Dec 28, 2010

Assignee: NetLogic Microsystems, Inc.

Abstract

Claims (93)

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 to a fail state and one or more success transitions to next states, the method comprising:

selecting a success size parameter (S), wherein S indicates a maximum number of input characters to be traversed on the success transitions; and

compressing the search tree to create a compressed search tree characterized by the selected success size parameter, wherein the compressing comprises:

combining each sequence of S states beginning at the root node into a single core state;

for each core state, if the fail state of the core state is eliminated in the combining, restoring the fail state and the failure transition from the core state to the restored fail state; and

inserting a new success transition from each restored fail state to a nearest core state;

wherein selecting S comprises:

determining a failure size parameter (F) for the search tree, wherein F indicates a minimum number of characters traversed on the failure transitions;

selecting a minimum processing speed (P); and

calculating S in response to F and P, wherein

S

=

F

*

P

F

-

P

.

2. The method of claim 1 , further comprising:

determining whether the compressed search tree includes one or more redundant failure transitions; and

eliminating the redundant failure transitions.

3. The method of claim 1 , further comprising:

for each core state, if the fail state of the core state includes any success transitions that are not common to the success transitions of the core state, adding the non-common success transitions to the core state;

replacing the failure transition of the core state with the failure transition of the fail state; and

eliminating the fail state from the compressed search tree.

4. The method of claim 3 , further comprising:

for each core state, if the fail state of the core state includes an output code, adding the output code to the core state.

5. A method for modifying a search tree embodying a 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 to a fail state and one or more success transitions to next states, the method comprising:

specifying a worst-case processing speed (P) for search operations between an input string of characters and the plurality of signatures;

determining a failure size parameter (F) for the search tree, wherein F indicates a minimum number of input characters traversed on failure transitions to non-root states;

calculating a success size parameter (S) in response to F and P, wherein S indicates a maximum number of input characters to be traversed on the success transitions; and

compressing the search tree to create a compressed search tree characterized by the calculated success size parameter, wherein

S

=

F

*

P

F

-

P

.

6. The method of claim 5 , wherein F is greater than one and less than infinite.

7. The method of claim 5 , wherein the compressing eliminates one or more states from the search tree to form the compressed search tree.

8. The method of claim 5 , wherein the compressing comprises:

combining each sequence of S states beginning at the root node into a single core state; and, for each core state:

if the fail state of the core state is eliminated in the compressing, restoring the fail state of the core state; and

restoring the failure transition from the core state to the restored fail state.

9. The method of claim 8 , wherein the compressing further comprises:

for each restored fail state, inserting a new success transition from the restored fail state to a nearest core state.

10. The method of claim 5 , further comprising:

determining whether the compressed search tree includes one or more redundant failure transitions; and

eliminating the redundant failure transitions.

11. The method of claim 5 , further comprising:

for each core state, if the fail state of the core state includes any success transitions that are not common to the success transitions of the core state, adding the non-common success transitions to the core state;

replacing the failure transition of the core state with a failure transition of the fail state; and

eliminating the fail state from the compressed search tree.

12. The method of claim 11 , further comprising:

for each core state, if the fail state of the core state includes an output code, adding the output code to the core state.

13. An optimization engine 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 to a fail state and one or more success transitions to next states, the method comprising:

means for selecting a success size parameter (S), wherein S indicates a maximum number of input characters to be traversed on the success transitions; and

means for compressing the search tree to create a compressed search tree characterized by the selected success size parameter, wherein the compressing comprises:

means for combining each sequence of S states beginning at the root node into a single core state;

for each core state, means for restoring the fail state and the failure transition from the core state to the restored fail state if the fail state of the core state is eliminated in the combining; and

means for inserting a new success transition from each restored fail state to a nearest core state;

wherein selecting S comprises:

means for determining a failure size parameter (F) for the search tree, wherein F indicates a minimum number of characters traversed on the failure transitions;

means for selecting a minimum processing speed (P); and

means for calculating S in response to F and P, wherein

S

=

F

*

P

F

-

P

.

14. A optimization engine for modifying a search tree embodying a 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 to a fail state and one or more success transitions to next states, the method comprising:

means for specifying a worst-case processing speed (P) for search operations between an input string of characters and the plurality of signatures;

means for determining a failure size parameter (F) for the search tree, wherein F indicates a minimum number of input characters traversed on failure transitions to non-root states;

means for calculating a success size parameter (S) in response to F and P, wherein S indicates a maximum number of input characters to be traversed on the success transitions; and

means for compressing the search tree to create a compressed search tree characterized by the calculated success size parameter, wherein

S

=

F

*

P

F

-

P

.

15. The optimization engine of claim 14 , wherein the search tree has an F value that is greater than one and less than infinite.

Assignments (8)

Continuity (1)