TU/e Research Portal · 1992 · 24 citations · 9 references
Open access
ComputingComputer ScienceAlgorithmsData MiningData StructuresPattern RecognitionSearching AlgorithmsString AlgorithmsMatching AlgorithmsPattern MatchingPattern Matching AlgorithmsPattern Searching
This paper presents a taxonomy of keyword pattern matching algorithms, including the well known Knuth-Morris-Pratt, Aho-Corasick, Boyer-Moore, and Commentz-Walter algorithms and a number of their variants. The taxonomy is based on the idea of ordering algorithms according to their essential problem and algorithm details, and deriving all algorithms from a common starting point by adding these details in a correctness preserving way. This way of presentation not only provides a complete correctness argument of each algorithm, but also makes very clear what algorithms have in common (the details of their nearest common ancestor) and where they differ (the details added after their nearest common ancestor). Moreover, the paper provides complete derivations of the intricate precomputation algorithms, some of which either can not be found in the literature (Commentz-Walter) or are given in several different versions (Boyer-Moore).
9
Fast Pattern Matching in Strings
Donald E. Knuth, James H. Morris, Vaughan Pratt · SIAM Journal on Computing · 1977 · 2.9K citations
Alfred V. Aho, Margaret J. Corasick · Communications of the ACM · 1975 · 2.9K citations · Full text
A fast string searching algorithm
Robert S. Boyer, J Strother Moore · Communications of the ACM · 1977 · 2.3K citations · Full text
Finite Automata and Their Decision Problems
M. O. Rabin, D. Scott · IBM Journal of Research and Development · 1959 · 1.9K citations