6 Horspool’s Algorithm
This chapter covers
- Constructing the Bad Character Shift table
- Executing right-to-left pattern scanning to bypassing redundant character evaluation
- Evaluating how the Horspool heuristic allows for sub-linear performance
Every string matching algorithm we covered in the previous chapters, like the Rabin-Karp and Knuth-Morris-Pratt algorithms (KMP), operates on the fundamental assumption of scanning the input text and the pattern from left to right. The Boyer-Moore-Horspool algorithm, commonly known as the Horspool algorithm, removes that assumption. Instead of scanning from left to right, we scan from right to left. And instead of focusing on matching characters, it derives its massive speed advantage from focusing on mismatches.
Horspool operates on a simple heuristic: if you are looking for a word in a massive document, and the character you are currently looking at is nowhere to be found in your search pattern, why slide the pattern forward by just one space? You should skip the pattern past that invalid character entirely.
To achieve this, a table is created called the Bad Character Shift Table, the algorithm mathematically pre-calculates exactly how far it can safely jump whenever a mismatch occurs. In practice, this allows the algorithm to skip analyzing massive chunks of text, resulting in sub-linear search times that easily outpace KMP in standard text processing.