Boyer–Moore string-search algorithm


In computer science, the Boyer–Moore string-search algorithm is an efficient string-searching algorithm that is the standard benchmark for practical string-search literature. It was developed by Robert S. Boyer and J Strother Moore in 1977. The original paper contained static tables for computing the pattern shifts without an explanation of how to produce them. The algorithm for producing the tables was published in a follow-on paper; this paper contained errors which were later corrected by Wojciech Rytter in 1980. The algorithm preprocesses the string being searched for, but not the string being searched in. It is thus well-suited for applications in which the pattern is much shorter than the text or where it persists across multiple searches. The Boyer–Moore algorithm uses information gathered during the preprocess step to skip sections of the text, resulting in a lower constant factor than many other string search algorithms. In general, the algorithm runs faster as the pattern length increases. The key features of the algorithm are to match on the tail of the pattern rather than the head, and to skip along the text in jumps of multiple characters rather than searching every single character in the text.

Definitions



Alignments of pattern PAN to text ANPANMAN, from k=3 to k=8. A match occurs at k=5.



The Boyer–Moore algorithm searches for occurrences of in by performing explicit character comparisons at different alignments. Instead of a brute-force search of all alignments, Boyer–Moore uses information gained by preprocessing to skip as many alignments as possible.
Previous to the introduction of this algorithm, the usual way to search within text was to examine each character of the text for the first character of the pattern. Once that was found the subsequent characters of the text would be compared to the characters of the pattern. If no match occurred then the text would again be checked character by character in an effort to find a match. Thus almost every character in the text needs to be examined.
The key insight in this algorithm is that if the end of the pattern is compared to the text, then jumps along the text can be made rather than checking every character of the text. The reason that this works is that in lining up the pattern against the text, the last character of the pattern is compared to the character in the text. If the characters do not match, there is no need to continue searching backwards along the text. If the character in the text does not match any of the characters in the pattern, then the next character in the text to check is located characters farther along the text, where is the length of the pattern. If the character in the text is in the pattern, then a partial shift of the pattern along the text is done to line up along the matching character and the process is repeated. Jumping along the text to make comparisons rather than checking every character in the text decreases the number of comparisons that have to be made, which is the key to the efficiency of the algorithm.
More formally, the algorithm begins at alignment, so the start of is aligned with the start of. Characters in and are then compared starting at index in and in, moving backward. The strings are matched from the end of to the start of. The comparisons continue until either the beginning of is reached or a mismatch occurs upon which the alignment is shifted forward according to the maximum value permitted by a number of rules. The comparisons are performed again at the new alignment, and the process repeats until the alignment is shifted past the end of, which means no further matches will be found.
The shift rules are implemented as constant-time table lookups, using tables generated during the preprocessing of.

Shift rules

A shift is calculated by applying two rules: the bad character rule and the good suffix rule. The actual shifting offset is the maximum of the shifts calculated by these rules.

The bad character rule

Description



Demonstration of bad character rule with pattern NNAAMAN.



The bad-character rule considers the character in at which the comparison process failed. The next occurrence of that character to the left in is found, and a shift which brings that occurrence in line with the mismatched occurrence in is proposed. If the mismatched character does not occur to the left in, a shift is proposed that moves the entirety of past the point of mismatch.

Preprocessing

Methods vary on the exact form the table for the bad character rule should take, but a simple constant-time lookup solution is as follows: create a 2D table which is indexed first by the index of the character in the alphabet and second by the index in the pattern. This lookup will return the occurrence of in with the next-highest index or -1 if there is no such occurrence. The proposed shift will then be, with lookup time and space, assuming a finite alphabet of length.
The C and Java implementations below have a space complexity. This is the same as the original delta1 and the BMH bad character table. This table maps a character at position to shift by, with the last instance -- the least shift amount -- taking precedence. All unused characters are set as as a sentinel value.

The good suffix rule

Description



Demonstration of good suffix rule with pattern ANAMPNAM.



The good suffix rule is markedly more complex in both concept and implementation than the bad character rule. It is the reason comparisons begin at the end of the pattern rather than the start, and is formally stated thus:

Suppose for a given alignment of P and T, a substring t of T matches a suffix of P, but a mismatch occurs at the next comparison to the left. Then find, if it exists, the right-most copy t' of t in P such that t' is not a suffix of P and the character to the left of t' in P differs from the character to the left of t in P. Shift P to the right so that substring t' in P aligns with substring t in T. If t' does not exist, then shift the left end of P past the left end of t in T by the least amount so that a prefix of the shifted pattern matches a suffix of t in T. If no such shift is possible, then shift P by n places to the right. If an occurrence of P is found, then shift P by the least amount so that a proper prefix of the shifted P matches a suffix of the occurrence of P in T. If no such shift is possible, then shift P by n places, that is, shift P past t.

Preprocessing

The good suffix rule requires two tables: one for use in the general case, and another for use when either the general case returns no meaningful result or a match occurs. These tables will be designated and respectively. Their definitions are as follows:

For each, is the largest position less than such that string matches a suffix of and such that the character preceding that suffix is not equal to. is defined to be zero if there is no position satisfying the condition.


Let denote the length of the largest suffix of that is also a prefix of, if one exists. If none exists, let be zero.

Both of these tables are constructible in time and use space. The alignment shift for index in is given by or. should only be used if is zero or a match has been found.

The Galil rule

A simple but important optimization of Boyer–Moore was put forth by Galil in 1979.
As opposed to shifting, the Galil rule deals with speeding up the actual comparisons done at each alignment by skipping sections that are known to match. Suppose that at an alignment, is compared with down to character of. Then if is shifted to such that its left end is between and, in the next comparison phase a prefix of must match the substring. Thus if the comparisons get down to position of, an occurrence of can be recorded without explicitly comparing past. In addition to increasing the efficiency of Boyer–Moore, the Galil rule is required for proving linear-time execution in the worst case.
The Galil rule, in its original version, is only effective for versions that output multiple matches. It updates the substring range only on, i.e. a full match. A generalized version for dealing with submatches was reported in 1985 as the Apostolico–Giancarlo algorithm.

Performance

The Boyer–Moore algorithm as presented in the original paper has worst-case running time of only if the pattern does not appear in the text. This was first proved by Knuth, Morris, and Pratt in 1977,
followed by Guibas and Odlyzko in 1980 with an upper bound of comparisons in the worst case. Richard Cole gave a proof with an upper bound of comparisons in the worst case in 1991.
When the pattern does occur in the text, running time of the original algorithm is in the worst case. This is easy to see when both pattern and text consist solely of the same repeated character. However, inclusion of the Galil rule results in linear runtime across all cases.

Implementations

Various implementations exist in different programming languages. In C++ it is part of the Standard Library since C++17, also Boost provides the implementation under the Algorithm library. In Go there is an implementation in . D uses a for predicate based matching within ranges as a part of the Phobos Runtime Library.
The Boyer–Moore algorithm is also used in GNU's grep.
Below are a few simple implementations.





from typing import *
  1. This version is sensitive to the English alphabet in ASCII for case-insensitive matching.
  2. To remove this feature, define alphabet_index as ord, and replace instances of "26"
  3. with "256" or any maximum code-point you want. For Unicode you may want to match in UTF-8
  4. bytes instead of creating a 0x10FFFF-sized table.
ALPHABET_SIZE = 26
def alphabet_index -> int:
"""Return the index of the given character in the English alphabet, counting from 0."""
val = ord) - ord
assert val >= 0 and val < ALPHABET_SIZE
return val
def match_length -> int:
"""Return the length of the match of the substrings of S beginning at idx1 and idx2."""
if idx1 idx2:
return len - idx1
match_count = 0
while idx1 < len and idx2 < len and S S:
match_count += 1
idx1 += 1
idx2 += 1
return match_count
def fundamental_preprocess -> List:
"""Return Z, the Fundamental Preprocessing of S.
Z is the length of the substring beginning at i which is also a prefix of S.
This pre-processing is done in O time, where n is the length of S.
"""
if len 0: # Handles case of empty string
return
if len 1: # Handles case of single-character string
return
z =
z = len
z = match_length
for i in range: # Optimization from exercise 1-5
z = z-i+1
# Defines lower and upper limits of z-box
l = 0
r = 0
for i in range:
if i <= r: # i falls within existing z-box
k = i-l
b = z
a = r-i+1
if b < a: # b ends within existing z-box
z = b
else: # b ends at or after the end of the z-box, we need to do an explicit match to the right of the z-box
z = a+match_length
l = i
r = i+z-1
else: # i does not reside within existing z-box
z = match_length
if z > 0:
l = i
r = i+z-1
return z
def bad_character_table -> List for a in range]
R = -1] for a in range]
alpha =
for i, c in enumerate:
alpha = i
for j, a in enumerate:
R.append
return R
def good_suffix_table -> List:
"""
Generates L for S, an array used in the implementation of the strong good suffix rule.
L = k, the largest position in S such that S matches
a suffix of S. Used in Boyer-Moore, L gives an amount to
shift P relative to T such that no instances of P in T are skipped and a suffix of P. In the case that L = -1, the full shift table is used.
Since only proper suffixes matter, L = -1.
"""
L =
N = fundamental_preprocess # S reverses S
N.reverse
for j in range:
i = len - N
if i != len:
L = j
return L
def full_shift_table -> List:
"""
Generates F for S, an array used in a special case of the good suffix rule in the Boyer-Moore
string search algorithm. F is the length of the longest suffix of S that is also a
prefix of S. In the cases it is used, the shift magnitude of the pattern P relative to the
text T is len - F for a mismatch occurring at i-1.
"""
F =
Z = fundamental_preprocess
longest = 0
for i, zv in enumerate:
longest = max if zv i + 1 else longest
F = longest
return F
def string_search -> List:
"""
Implementation of the Boyer-Moore string search algorithm. This finds all occurrences of P
in T, and incorporates numerous ways of pre-processing the pattern to determine the optimal
amount to shift the string and skip comparisons. In practice it runs in O time, where m is the length of T. This implementation performs a case-insensitive
search on ASCII alphabetic characters, spaces not included.
"""
if len 0 or len 0 or len < len:
return
matches =
# Preprocessing
R = bad_character_table
L = good_suffix_table
F = full_shift_table
k = len - 1 # Represents alignment of end of P relative to T
previous_k = -1 # Represents alignment in previous phase
while k < len:
i = len - 1 # Character to compare in P
h = k # Character to compare in T
while i >= 0 and h > previous_k and P T: # Matches starting from end of P
i -= 1
h -= 1
if i -1 or h previous_k: # Match has been found
matches.append
k += len-F if len > 1 else 1
else: # No match, shift by max of bad character and good suffix rules
char_shift = i - R
if i+1 len: # Mismatch happened on first attempt
suffix_shift = 1
elif L -1: # Matched suffix does not appear anywhere in P
suffix_shift = len - F
else: # Matched suffix appears in P
suffix_shift = len - 1 - L
shift = max
previous_k = k if shift >= i+1 else previous_k # Galil's rule
k += shift
return matches









  1. include
  2. include
  3. include
  4. include
  5. define ALPHABET_LEN 256
  6. define max
// BAD CHARACTER RULE.
// delta1 table: delta1 contains the distance between the last
// character of pat and the rightmost occurrence of c in pat.
//
// If c does not occur in pat, then delta1 = patlen.
// If c is at string and c != pat, we can safely shift i
// over by delta1, which is the minimum distance needed to shift
// pat forward to get string lined up with some character in pat.
// c pat returning zero is only a concern for BMH, which
// does not have delta2. BMH makes the value patlen in such a case.
// We follow this choice instead of the original 0 because it skips
// more.
//
// This algorithm runs in alphabet_len+patlen time.
void make_delta1
// true if the suffix of word starting from word is a prefix
// of word
bool is_prefix
// length of the longest suffix of word ending on word.
// suffix_length = 2
size_t suffix_length
// GOOD SUFFIX RULE.
// delta2 table: given a mismatch at pat, we want to align
// with the next possible full match could be based on what we
// know about pat to pat.
//
// In case 1:
// pat to pat does not occur elsewhere in pat,
// the next plausible match starts at or after the mismatch.
// If, within the substring pat, lies a prefix
// of pat, the next plausible match is here. Otherwise, the
// next plausible match starts past the character aligned with
// pat.
//
// In case 2:
// pat to pat does occur elsewhere in pat. The
// mismatch tells us that we are not looking at the end of a match.
// We may, however, be looking at the middle of a match.
//
// The first loop, which takes care of case 1, is analogous to
// the KMP table, adapted for a 'backwards' scan order with the
// additional restriction that the substrings it considers as
// potential prefixes are all suffixes. In the worst case scenario
// pat consists of the same letter repeated, so every suffix is
// a prefix. This loop alone is not sufficient, however:
// Suppose that pat is "ABYXCDBYX", and text is ".....ABYXCDEYX".
// We will match X, Y, and find B != E. There is no prefix of pat
// in the suffix "YX", so the first loop tells us to skip forward
// by 9 characters.
// Although superficially similar to the KMP table, the KMP table
// relies on information about the beginning of the partial match
// that the BM algorithm does not have.
//
// The second loop addresses case 2. Since suffix_length may not be
// unique, we want to take the minimum value, which will tell us
// how far away the closest potential match is.
void make_delta2
// Returns pointer to first match.
// See also glibc memmem and std::boyer_moore_searcher.
uint8_t* boyer_moore









/**
* Returns the index within this string of the first occurrence of the
* specified substring. If it is not a substring, return -1.
*
* There is no Galil because it only generates one match.
*
* @param haystack The string to be scanned
* @param needle The target string to search
* @return The start index of the substring
*/
public static int indexOf
/**
* Makes the jump table based on the mismatched character information.
*/
private static int makeCharTable
/**
* Makes the jump table based on the scan offset which mismatch occurs.
*.
*/
private static int makeOffsetTable
/**
* Is needle a prefix of needle?
*/
private static boolean isPrefix
/**
* Returns the maximum length of the substring ends at p and is a suffix.
*
*/
private static int suffixLength



Variants

The Boyer–Moore–Horspool algorithm is a simplification of the Boyer–Moore algorithm using only the bad character rule.
The Apostolico–Giancarlo algorithm speeds up the process of checking whether a match has occurred at the given alignment by skipping explicit character comparisons. This uses information gleaned during the pre-processing of the pattern in conjunction with suffix match lengths recorded at each match attempt. Storing suffix match lengths requires an additional table equal in size to the text being searched.
The Raita algorithm improves the performance of Boyer-Moore-Horspool algorithm. The searching pattern of particular sub-string in a given string is different from Boyer-Moore-Horspool algorithm.