APPARATUS AND METHOD FOR SELECTING FINITE SUCCESS STATES BY INDEXING

A finite state automaton (FSA) may be used to search a stream of input digital code data representing patterns such as text characters, for example, to identify a plurality of designated query words. When a particular one of the sought values of a character or other code element is identified in the input stream, the proper next state for the FSA is typically selected with the aid of a control table memory with multiple entries for each state. According to the invention, the portion of that memory associated with each multiple exit decision state typically consists of only a single word which contains a base state number and a group of indexing bits, one bit for each possible input code element configuration, with set bits corresponding to the multiple values being sought when the FSA is in that particular state. In response to an input code element value that represents a success, an index number is generated from that value and the set indexing bits. That index number is then combined with the base state number to produce the identity of the next success state. The number of indexing bits is reduced for certain codes, such as those representing text characters, by separating the normal elements of the input code into smaller elements, called "nibbles," thereby limiting the number of different input code configurations that must be processed by the FSA in any one state.