Patent ID: 7899904
Filing Date: 2011-03-01
Classification: G06F

Abstract:
1. A method of tracking active states of a nondeterministic state machine during a process of traversing states of the state machine in response to characters of an input data stream, the method comprising: (a) loading state information associated with one or more states of the state machine into a register bank and marking as active the state information of at least one state, the state information for each state comprising one or more transition conditions associated with the state and one or more next states associated with respective transition conditions; (b) determining a next character of the input stream; (c) accessing the transition conditions of only the currently active states in order to determine one or more transition conditions that are satisfied by the next character; (d) marking as active in the register bank state information associated with one or more next states associated with the satisfied transition conditions; (e) marking as inactive in the register bank state information associated with any next states that are not associated with one or more satisfied transition conditions; (f) repeating steps (b)-(e) for each character of the input stream.