Chapter 6: Horspool’s Algorithm
Introduces Horspool’s right-to-left, mismatch-driven approach to string matching and explains why its precomputed shifts can speed up searches.
After this chapter you will be able to
- Right-to-left mismatch focus. Explain how Horspool differs from the earlier string-matching algorithms described here: it scans from right to left and gains speed by focusing on mismatches rather than matches.
- Bad-character skipping heuristic. Explain why Horspool can move past a text character absent from the pattern, and describe the Bad Character Shift Table’s role in pre-calculating safe jump distances. Relate those jumps to the section’s claim about faster searches in practice.
- Right-to-left matching and shifts. Explain that Horspool checks the rightmost pattern character first and shifts the pattern according to the mismatched text character. Distinguish the full-length shift for a character absent from the pattern from the smaller shift needed when it occurs in the pattern.
- Bad character table construction. Describe how to build and use the bad character shift table: give absent characters a default shift equal to the pattern length, calculate entries as length minus one minus index, overwrite repeated characters with values from later positions, and look up the mismatched text character during search.
- Repeated Character Shift Values. Explain how to build the bad character shift table for “abcdabcy,” including which value to keep when a character repeats and why the final character is skipped.
- Mismatch Driven Search Shifts. Trace how the example searches right to left within each window, looks up the mismatching text character, and shifts the pattern until it reaches a full match.
- Suitable Horspool Search Conditions. Explain why Boyer-Moore-Horspool suits text already in memory with a large alphabet, and contrast that setting with the multiple-pattern and streaming searches described for Rabin-Karp and KMP.
- V8 Pattern Length Choice. Describe how V8 chooses between linear search and Boyer-Moore-Horspool based on pattern length, and explain the cost tradeoff.
- Sublinear Skipping Advantage. Explain how right-to-left comparisons let Horspool use early mismatches to skip chunks of text, yielding the section’s stated average-case time of O(n/m), where n is text length and m is pattern length.
- Alphabet Size Performance Dependence. Distinguish why Horspool tends to make large shifts with a diverse alphabet but small shifts with a tiny alphabet, and state the worst-case time given for the latter situation.
What it builds on
- Fast pattern matching (chapter 5) · Provides the earlier KMP string-matching approach used for contrast.
Section by section
Introduction
Introduces Horspool’s right-to-left, mismatch-driven approach to string matching and explains why its precomputed shifts can speed up searches.
- Right-to-left mismatch focus: Explain how Horspool differs from the earlier string-matching algorithms described here: it scans from right to left and gains speed by focusing on mismatches rather than matches.
Why it matters: This change in perspective explains why Horspool can skip work that a left-to-right search might perform. - Bad-character skipping heuristic: Explain why Horspool can move past a text character absent from the pattern, and describe the Bad Character Shift Table’s role in pre-calculating safe jump distances. Relate those jumps to the section’s claim about faster searches in practice.
Why it matters: The skip is the reason the introduction gives for avoiding large amounts of character-by-character work.
Key terms: Horspool algorithm, right to left, mismatches, Bad Character Shift Table, heuristic, mismatch, sub-linear search times
6.1 The paradigm shift: Right to left scanning
This section explains how Horspool’s algorithm compares a pattern from right to left and uses a precomputed bad character shift table to move the pattern safely after a mismatch.
- Right-to-left matching and shifts: Explain that Horspool checks the rightmost pattern character first and shifts the pattern according to the mismatched text character. Distinguish the full-length shift for a character absent from the pattern from the smaller shift needed when it occurs in the pattern.
Why it matters: The direction of comparison and the safe shift are what let Horspool skip positions rather than advance one at a time. - Bad character table construction: Describe how to build and use the bad character shift table: give absent characters a default shift equal to the pattern length, calculate entries as length minus one minus index, overwrite repeated characters with values from later positions, and look up the mismatched text character during search.
Why it matters: Precomputing the shifts lets the search choose a movement immediately when it encounters a mismatch. - Last-character exclusion rationale: Justify why the last character of the pattern is left out of the shift-table calculation.
Why it matters: A search loop must move forward after a mismatch rather than repeat the same comparison indefinitely.
Key terms: right to left, mismatch, bad character, shift, Bad Character Shift Table, Default Shift, Shift = pattern length - 1 - index, overwrite previous character, last character, shift value of zero
6.2 Handling internal redundancy
This section shows how Horspool’s algorithm builds a shift table for a pattern with repeated characters and uses it to skip text alignments during a search.
- Repeated Character Shift Values: Explain how to build the bad character shift table for “abcdabcy,” including which value to keep when a character repeats and why the final character is skipped.
Why it matters: Keeping the rightmost occurrence prevents a shift from jumping past a possible match. - Mismatch Driven Search Shifts: Trace how the example searches right to left within each window, looks up the mismatching text character, and shifts the pattern until it reaches a full match.
Why it matters: The table turns a mismatching text character into a jump rather than requiring a check at every starting position.
Key terms: bad character shift table, rightmost occurrence, default maximum shift, bad character, text window, right-to-left, shift, alignment
6.3 Real-World applications
This section explains where Boyer-Moore-Horspool is useful in production and why databases and JavaScript engines may choose it for substring searches.
- Suitable Horspool Search Conditions: Explain why Boyer-Moore-Horspool suits text already in memory with a large alphabet, and contrast that setting with the multiple-pattern and streaming searches described for Rabin-Karp and KMP.
Why it matters: The kind of text and search task helps explain why an engine would choose Horspool. - Database Substring Search: Explain why a Boyer-Moore-Horspool variant can help PostgreSQL find a substring in a large natural-language text column.
Why it matters: The database example connects Horspool's skips to lower work during searches of large text columns. - V8 Pattern Length Choice: Describe how V8 chooses between linear search and Boyer-Moore-Horspool based on pattern length, and explain the cost tradeoff.
Why it matters: The V8 example shows why preprocessing is worthwhile for some pattern lengths but not others.
Key terms: Boyer-Moore-Horspool, large alphabets, static text, Rabin-Karp, KMP, PostgreSQL, strpos(), bad character table, natural language, V8
6.4 Key insights
Explains why Horspool can skip much of a text on average and why its speed depends on the alphabet.
- Sublinear Skipping Advantage: Explain how right-to-left comparisons let Horspool use early mismatches to skip chunks of text, yielding the section’s stated average-case time of O(n/m), where n is text length and m is pattern length.
Why it matters: This explains how Horspool can avoid inspecting every text character. - Alphabet Size Performance Dependence: Distinguish why Horspool tends to make large shifts with a diverse alphabet but small shifts with a tiny alphabet, and state the worst-case time given for the latter situation.
Why it matters: Alphabet size helps predict when Horspool’s large skips will—and will not—pay off.
Key terms: right to left, sub-linear, O(n/m), pattern length, alphabet size, bad character, default skip, O(n x m)
6.5 Summary
6.6 References
Lists the original Horspool paper and links to a video, application source code, and an implementation.
Concepts explained in this chapter
- Boyer-Moore-Horspool algorithmThe Boyer-Moore-Horspool algorithm is a string-search procedure that compares pattern characters from right to left and uses character-based skip distances to shift the pattern.
- bad character shift tableA lookup table that maps characters to safe distances for shifting a pattern after a mismatch in string searching.
- bad characterA bad character is a text character that causes a right-to-left pattern comparison to mismatch and determines a pattern shift in Horspool's algorithm.
- right-to-left processingRight-to-left pattern scanning compares a candidate pattern occurrence beginning with its rightmost character and proceeds toward its leftmost character.
- shift valueA shift value is an integer distance specifying how far a search pattern may move after a character mismatch.
- preprocessingPreprocessing is preparatory computation performed on input data before the main algorithmic operation begins.
- rightmost occurrenceA rightmost occurrence is the latest-position occurrence of a character within a pattern or sequence.
- O(nxm)A time bound proportional to the product of text length n and pattern length m.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
