Boyer–Moore–Horspool algorithm

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.
Find sources: "Boyer–Moore–Horspool algorithm" – news · newspapers · books · scholar · JSTOR (October 2015)

Boyer–Moore–Horspool algorithm
Class	Substring searching
Data structure	String
Worst-case performance	$O(nm)$
Average performance	$\Theta (n)$

In computer science, the Boyer–Moore–Horspool algorithm or Horspool's algorithm is an algorithm for finding substrings in strings. It was published by Nigel Horspool in 1980 as SBM.

It is a simplification of the Boyer–Moore string-search algorithm which is related to the Knuth–Morris–Pratt algorithm. The algorithm trades space for time in order to obtain an average-case complexity of O(n) on random text, although it has O(nm) in the worst case, where the length of the pattern is m and the length of the search string is n.

Description

Like Boyer–Moore, Boyer–Moore–Horspool preprocesses the pattern to produce a table containing, for each symbol in the alphabet, the number of characters that can safely be skipped. The preprocessing phase, in pseudocode, is as follows (for an alphabet of 256 symbols, i.e., bytes):

 // Unlike the original, we use zero-based indices here.
 function preprocess(pattern)
     T := new table of 256 integers
     for i from 0 to 256 exclusive
         T := length(pattern)
     for i from 0 to length(pattern) - 1 exclusive
         T] := length(pattern) - 1 - i
     return T

Pattern search proceeds as follows. The procedure search reports the index of the first occurrence of needle in haystack.

// Compares two strings, up to the first len characters.
// Note: this is equivalent to !memcmp(str1, str2, len).
function same(str1, str2, len)
    i := len - 1
    // The original algorithm tries to play smart here: it checks for the
    // last character, then second-last, etc.
    while str1 == str2
        if i == 0
            return true
        i := i - 1
    return false
function search(needle, haystack)
    T := preprocess(needle)
    skip := 0
    // haystack means substring starting at index `skip`. Would be &haystack in C.
    while length(haystack) - skip >= length(needle)
        if same(haystack, needle, length(needle))
            return skip
        skip := skip + T]
    return -1

Performance

The algorithm performs best with long needle strings, when it consistently hits a non-matching character at or near the final byte of the current position in the haystack and the final byte of the needle does not occur elsewhere within the needle. For instance a 32 byte needle ending in "z" searching through a 255 byte haystack which does not have a 'z' byte in it would take up to 224 byte comparisons.

The best case is the same as for the Boyer–Moore string-search algorithm in big O notation, although the constant overhead of initialization and for each loop is less.

The worst case behavior happens when the bad character skip is consistently low (with the lower limit of 1 byte movement) and a large portion of the needle matches the haystack. The bad character skip is only low, on a partial match, when the final character of the needle also occurs elsewhere within the needle, with 1 byte movement happening when the same byte is in both of the last two positions.

The canonical degenerate case similar to the above "best" case is a needle of an 'a' byte followed by 31 'z' bytes in a haystack consisting of 255 'z' bytes. This will do 31 successful byte comparisons, a 1 byte comparison that fails and then move forward 1 byte. This process will repeat 223 more times (255 − 32), bringing the total byte comparisons to 7,168 (32 × 224). (A different byte-comparison loop will have a different behavior.)

The worst case is significantly higher than for the Boyer–Moore string-search algorithm, although obviously this is hard to achieve in normal use cases. It is also worth noting that this worst case is also the worst case for the naive (but usual) memcmp() algorithm, although the implementation of that tends to be significantly optimized (and is more cache friendly).

Tuning the comparison loop

The original algorithm had a more sophisticated same() loop. It uses an extra pre-check before proceeding in the positive direction:

function same_orig(str1, str2, len)
    i ← 0
    if str1 = str2
        while str1 = str2
            if i = len - 2
                return true
            i ← i + 1
    return false

A tuned version of the BMH algorithm is the Raita algorithm. It adds an additional precheck for the middle character, in the order of last-first-middle. The algorithm enters the full loop only when the check passes:

function same_raita(str1, str2, len)
    i ← 0
    mid ← len / 2
    Three prechecks.
    if len ≥ 3
        if str != str2
            return false
    if len ≥ 1
        if str != str2
            return false
    if len ≥ 2
        if str != str2
            return false
    Any old comparison loop.
    return len < 3 or SAME(&str1, &str2, len - 2)

It is unclear whether this 1992 tuning still holds its performance advantage on modern machines. The rationale by the authors is that actual text usually contains some patterns which can be effectively prefiltered by these three characters. It appears that Raita is not aware of the old last-character precheck (he believed that the backward-only same routine is the Horspool implementation), so readers are advised to take the results with a grain of salt.

On modern machines, library functions like memcmp tends to provide better throughput than any of the hand-written comparison loops. The behavior of an "SFC" loop (Horspool's terminology) both in libstdc++ and libc++ seems to suggest that a modern Raita implementation should not include any of the one-character shifts, since they have detrimental effects on data alignment. Also see String-searching algorithm which has detailed analysis of other string searching algorithms.

References

^ Horspool, R. N. (1980). "Practical fast searching in strings". Software: Practice and Experience. 10 (6): 501–506. CiteSeerX 10.1.1.63.3421. doi:10.1002/spe.4380100608. S2CID 6618295.
^ Raita, Timo (1992). "Tuning the boyer-moore-horspool string searching algorithm". Software: Practice and Experience. 22 (10): 879–884. doi:10.1002/spe.4380221006. S2CID 14193323.
"⚙ D27068 Improve string::find". LLVM Code Review.
"[PATCH] improve string find algorithm". GCC.

External links

v t e Strings
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt pattern matching Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm
String-searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp algorithm Raita algorithm Trigram search Two-way string-matching algorithm Zhu–Takaoka string matching algorithm
Multiple string searching	Aho–Corasick Commentz-Walter algorithm
Regular expression	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Sequence alignment	BLAST Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Substring index Suffix array Suffix automaton Suffix tree Compressed suffix array LCP array FM-index Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting String rewriting systems String operations

Category:

String matching algorithms