A Performance Evaluation of the Preprocessing Phase of Multiple Keyword Matching Algorithms

Multiple keyword matching is an important problem in text processing that involves the location of all the positions of an input string where one or more keywords from a finite set occur. Modern multiple keyword matching algorithms can scan the input string in a single pass by preprocessing the keyword set, an essential phase that affects the overall performance of each algorithm. This paper presents a performance evaluation in terms of preprocessing of the well known Commentz-Walter, Wu-Manber, Set Backward Oracle Matching and Salmela-Tarhio-Kyt"{o}joki multiple keyword matching algorithms for different types of keywords and for several problem parameters.