Patent ID: 8199644

Claim:
A method of storing a state machine, the method comprising: storing a state machine in a memory, the state machine comprising a plurality of states and transitions therebetween, the state machine comprising a plurality of branches, each having a terminal state, that are associated with the matches of an input string to respective regular expressions; selecting a predetermined number of states in each branch of the state machine for storage in a cache memory that has faster access and read times than the memory; before receiving packets in a packet stream, selecting one or more additional states of at least a first branch of the state machine in response to determining that the first branch comprises unselected states that are associated with each of a plurality of branches; before receiving packets in the packet stream, deselecting one or more states of at least a second branch of the state machine in response to determining that the second branch comprises selected states that are only associated with the second branch; before receiving packets in the packet stream, storing the selected states of the state machine in the cache memory; in response to accessing a state of at least a third branch of the state machine, determining a number of third branch terminal states associated with the third branch; and if the number of third branch terminal states is less than a predetermined threshold, prefetching state transition instructions associated with each of the third branch terminal states for storage in a buffer memory.