ALTEP - a cellular processor for high-speed pattern matching (Q1821568)

The design of a high-speed cellular pattern matcher, called the Associative Linear Text Processor (ALTEP), is presented. ALTEP was originally designed for systems which use signature files as an access method. However, it is also suitable for systems which store the database in fixed length blocks. ALTEP is a linear array of logic cells which respond to commands sent from a central controller over a bus. A text block is loaded into the cells and pattern characters are broadcast to the cells for comparison. ALTEP has the capability of recognizing full regular expressions and is the only cellular logic array which has this capability. It requires O(p) steps for patterns which do not contain closures and O(len(max(T(P)))) steps for closures, where p is the the length of the pattern and len(max(T(P))) is the length of the longest substring in the text which matched the closure.