PARALLEL PATTERN-MATCHING AND FGREP

Algorithms are considered that recognize patterns while searching for them in a set of data. Among them the Aho-Corasick is described as a simple and efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text. Without modification to the algorithm, 'keyword' can be taken to mean any pattern and 'a string of text' to mean any sequence of symbols, be it ASCII text, digitized data obtained from a video camera, or whatever. Various uses and applications of this algorithm are illustrated. An application of a Unix utility based on the algorithm Fgrep is used to illustrate the speed of the Aho-Corasick algorithm. Typically, fgrep is five to ten times faster than grep in searching files for fixed string patterns.