Premium
Fast string searching
Author(s) -
Hume Andrew,
Sunday Daniel
Publication year - 1991
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380211105
Subject(s) - yardstick , computer science , benchmark (surveying) , compiler , set (abstract data type) , string (physics) , theoretical computer science , range (aeronautics) , programming language , algorithm , mathematics , engineering , geometry , geodesy , aerospace engineering , mathematical physics , geography
Abstract Since the Boyer‐Moore algorithm was described in 1977, it has been the standard benchmark for the practical string search literature. Yet this yardstick compares badly with current practice. We describe two algorithms that perform 47% fewer comparisons and are about 4.5 times faster across a wide range of architectures and compilers. These new variants are members of a family of algorithms based on the skip loop structure of the preferred, but often neglected, fast form of Boyer‐Moore. We present a taxonomy for this family, and describe a toolkit of components that can be used to design an algorithm most appropriate for a given set of requirements.