A TAXONOMY OF SUBLINEAR MULTIPLE KEYWORD PATTERN-MATCHING ALGORITHMS

This article presents a taxonomy of sublinear keyword pattern matching algorithms related to the Boyer-Moore algorithm [3] and the Commentz- Walter algorithm [5,6]. The taxonomy includes, amongst others, the mul tiple keyword generalization of the single keyword Boyer-Moore algorit hm and an algorithm by Fan and Su [9,10]. The corresponding precomputa tion algorithms are presented as well. The taxonomy is based on the id ea of ordering algorithms according to their essential problem and alg orithm details, and deriving all algorithms from a common starting poi nt by successively adding these details in a correctness preserving wa y. This way of presentation not only provides a complete correctness a rgument of each algorithm, but also makes very clear what algorithms h ave in common (the details of their nearest common ancestor) and where they differ (the details added after their nearest common ancestor). Introduction of the notion of safe shift distances proves to be essent ial in the derivation and classification of the algorithms. Moreover, the article provides a common derivation for and a uniform presentatio n of the precomputation algorithms, not yet found in the literature.