Patent ID: 7636717
Filing Date: 2009-12-22
Classification: G06F,H04L,Y10S

Abstract:
1. A method for achieving a desired balance between processing speed and storage area requirements in search operations by selectively 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 success transitions characterized by a success size parameter (S) and including a number of failure transitions characterized by a failure size parameter (F), the method comprising: selecting a minimum processing speed (Pmin) for a finite state machine (FSM) configured to implement the search tree; identifying a number of pairs of F and S values that result in a worst-case processing speed (P) greater than Pmin, wherein S indicates a maximum number of input characters traversed by a cursor on the success transitions, F indicates a minimum number of input characters traversed by a back pointer on the failure transitions, and modifying the search tree to create a number of modified search trees, each characterized by a corresponding one of the identified pairs of F and S values, and selecting the modified search tree that requires the least amount of storage area.