The performance of single-keyword and multiple-keyword pattern matching algorithms
Bruce W. Watson · TU/e Research Portal · 1994
This paper presents a toolkit of pattern matching algorithms, performance data on the algorithms, and recommendations for the selection of an algorithm (given a particular application) . The pattern matching problem is: given a finite non-empty set of keywords and an input string, find all occurrences of any of the keywords in the input string. The pattern matching toolkit (written in the C programming language, and freely available) contains implementations of the Knuth-Morris-Pratt, Boyer-Moore, Aho-Corasick, and Commentz-Walter algorithms. The algorithms are implemented directly from the abstract algorithms derived and presented in the taxonomy of Watson and Zwaan [WZ92]. The toolkit provides one of the few known correct implementations of the Commentz-Walter precomputation algorithm. The performance of all of the algorithms (running on a variety of workstation hardware) was measured on two types of input: English text and genetic sequences. The input data, which is the same as that...