Patent ID: 7860849

Claim:
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 .