Patent ID: 7917486

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