Suppose you are searching a long document for a word. If a character at the end of the current search window cannot occur in that word, checking the next nearby window would be wasted work. The Boyer-Moore-Horspool algorithm, or Horspool algorithm, uses that mismatch to move the pattern several positions at once. section 6.0
The search has two parts:
- Prepare a bad character shift table. For a pattern of length m, give each character except the last a shift of m − 1 − its index. Later occurrences overwrite earlier ones; a character absent from the table gets the default shift m. section 6.1 section 6.2
- Align the pattern with a text window and compare characters from right to left. On a mismatch, use the shift table to advance the window; on a complete match, record its starting position and advance to continue searching. section 6.1 section 6.2
Why the last occurrence wins
For the pattern “abcdabcy,” m is 8. The first “a,” at index 0, suggests a shift of 7; the later “a,” at index 4, replaces that with 3. Likewise, the final table gives “b” 2, “c” 1, and “d” 4. Other characters get 8. Keeping the smaller shift avoids jumping past a possible match. The final “y” is excluded: its calculated shift would be zero, so the search could stop moving. section 6.2 section 6.5
Table 6.3 Step-by-step bad character table construction for ‘abcdabcy’
|
Index (i)
|
character (pattern[i])
|
Shift = Length - 1 - index
|
Action taken
|
Current table state
|
|
initial
|
-
|
-
|
Default shift
|
[Default: 8]
|
|
0
|
a
|
8-1-0=7
|
Add new character
|
[a: 7]
|
|
1
|
b
|
8-1-1=6
|
Add new character
|
[a: 7, b: 6]
|
|
2
|
c
|
8-1-2=5
|
Add new character
|
[a: 7, b: 6, c: 5]
|
|
3
|
d
|
8-1-3=4
|
Add new character
|
[a: 7, b: 6, c: 5, d: 4]
|
|
4
|
a
|
8-1-4=3
|
Overwrite previous ‘a’
|
[a: 3, b: 6, c: 5, d: 4]
|
|
5
|
b
|
8-1-5=2
|
Overwrite previous ‘b’
|
[a: 3, b: 2, c: 5, d: 4]
|
|
6
|
c
|
8-1-6=1
|
Overwrite previous ‘c’
|
[a: 3, b: 2, c: 1, d: 4]
|
|
7
|
y
|
-
|
Ignore final character
|
[a: 3, b: 2, c: 1, d: 4]
|
Follow the table row by row to see later occurrences replace earlier shift values. section 6.2
Horspool can be fast when a pattern is searched in text already in memory, especially when the text has many different characters: characters absent from the pattern permit full-length jumps. The tradeoff is preprocessing the table. Short patterns may not repay that cost, while repetitive text or a small alphabet can force tiny shifts. Its worst-case search time is O(n × m), where n is text length; the favorable skipping behavior is described as approximately O(n/m). Unlike KMP’s approach to continuous streams, Horspool relies on access to the current text window. section 6.3 section 6.4
