Boyer-Moore Algorithm
Practically fast string matching algorithm
The Boyer-Moore algorithm is a string-matching algorithm that searches for a pattern in a text by comparing characters from right to left within each alignment and using precomputed heuristics to skip large portions of the text on…
Definition
The Boyer-Moore algorithm is a string-matching algorithm that searches for a pattern in a text by comparing characters from right to left within each alignment and using precomputed heuristics to skip large portions of the text on mismatches.
Overview
Developed by Robert Boyer and J Strother Moore in 1977, the Boyer-Moore algorithm departs from left-to-right character comparison used by most string-matching algorithms, instead comparing the pattern against the text starting from the pattern's rightmost character. This ordering enables two powerful heuristics that let the algorithm skip ahead by more than one position on a mismatch, rather than shifting just one character at a time: the bad character rule, which shifts the pattern so that the mismatched text character aligns with its rightmost occurrence in the pattern (or past the pattern entirely if the character doesn't appear), and the good suffix rule, which uses the portion of the pattern that did match to determine a shift that preserves any partial alignment that could still lead to a match elsewhere in the pattern. Both heuristics are precomputed from the pattern before scanning begins, so the per-character skip decisions during the actual text scan are constant-time table lookups. In the best case (e.g., searching for a pattern with distinctive characters in a large alphabet like natural-language text), Boyer-Moore can achieve sublinear behavior, examining far fewer than n characters of the text, which is why it tends to outperform algorithms like KMP in practice on typical text search workloads, even though its formal worst-case complexity (without the additional Galil rule enhancement) can be O(n*m) in pathological cases. Because of its strong practical performance, particularly on long patterns and large alphabets, Boyer-Moore and its variants (such as Boyer-Moore-Horspool, a simplified version using only the bad character rule) are the default string-search algorithms in many real-world tools, including the Unix `grep` command's historical implementations, text editors' find functionality, and antivirus and intrusion-detection systems scanning for byte-pattern signatures in large files or network streams.
Key Concepts
- Compares pattern characters from right to left within each alignment
- Uses the bad character rule to skip ahead on mismatches
- Uses the good suffix rule to preserve useful partial-match information
- Achieves sublinear behavior in the best case on many real texts
- Precomputed heuristic tables enable constant-time skip decisions
- Developed by Robert Boyer and J Strother Moore in 1977
- Boyer-Moore-Horspool variant simplifies to just the bad character rule
- Historically used as the default search algorithm in tools like grep