Abstract

The subject of this disclosure is a Finite State Automaton (FSA) used as part of a term detector employed in a digital pattern search system (searcher). In particular the invention includes various advances in the art of FSA design which make the FSA practical for pattern recognition.Specifically, these advances minimize the amount of memory which is required in each FSA in performing pattern recognition, and allow a speed capability such that the searching can be performed at the rate at which a mass storage medium can supply data. The large amount of memory required and the low speed of processing in the prior state of the art made the use of an FSA impractical for most real applications.The new advances include the following:An adaptation of the indexing means described in reference 4, which allows simple selection of the correct success transition state from a number of possible success states;The partitioning of searchable digital patterns into parts (called nibbles) to reduce the amount of memory used within an FSA;The use of various types of states to allow the detection of specific input patterns in the presence of don't-care patterns;The use of multiple FSA's to reduce the amount of memory needed in these FSA's when handling don't-care patterns;The unique design of an FSA to search for multiple sequential input patterns;The unique features of the FSA design to allow recognition of numerical ranges of values from among numerical data.

Other References

• Communications of the ACM, "A Generalized Technique for Symbol Manipulation . . . ", by Douglas T. Ross, presented 5/20-21/60
• Communications of the ACM; vol. 11, No. 12, Dec. 1968; "Automatic Generation of Efficient Lexical Processors", by Johnson et al