String pattern matching algorithms: An empirical analysis
Edward J. Smith · The Mathematics Enthusiast · 1991
The problem of searching through text to find a specified substring, "pattern", is empirically examined.Several existing pattern matching algorithms are surveyed including the Knuth-Morris-Pratt and the Boyer-Moore algorithms as well as Daniel M. Sunday's algorithms.A technique of Boyer and Moore's, the fast loop, is extended to other algorithms with a dramatic improvement in performance.A short and simplified version of the Boyer-Moore algorithm is presented which is easy to understand and is very fast.Combining ideas from several different algorithms, a hybrid algorithm has been developed which maximizes the efficiency of the Boyer-Moore fast loop.This algorithm has excellent run time performance.Algorithms which search strings of binary and quaternary alphabets are also presented.These algorithms process four and eight characters at a time by expanding a small sized alphabet into what ostensibly is a much larger alphabet.I would also like to dedicate the paper to Dr. Alden Wright whose help and inspiration was invaluable during all phases of my graduate studies.Special thanks are due to my colleagues and friends Yu Shi and Jeff Heng who showed me more computer tricks than T can remember.Finally, and most importantly, gratitude is due my father, Jack Smith, who taught me how to read.Without that, none of this would have been possible.vi