Boyer–Moore Algorithm

Prerequisites: Prefix Function and KMP Algorithm.

The KMP algorithm makes full use of prefix matching information,

while the basic idea behind the BM algorithm is to achieve faster character skipping by leveraging suffix matching to obtain more information than prefix matching.

Introduction

Imagine our pattern string \(pat\) is placed at the leftmost head of the text string \(string\), with their first characters aligned.

\[ \begin{aligned} \textit{pat}:\qquad\qquad &\texttt{EXAMPLE} \\ \textit{string}:\qquad\quad &\texttt{HERE IS A SIMPLE EXAMPLE} \dots \\ &\qquad\ \ \ \, \, \Uparrow \end{aligned} \]

Definitions are made here and will not be repeated later:

The length of \(pat\) is \(patlen\), and specifically for strings starting from index 0, we define \(patlastpos=patlen-1\) as the position of the last character in \(pat\);

The length of \(string\) is \(stringlen\), and \(stringlastpos = stringlen-1\).

Suppose we know the \(patlen\)-th character \(char\) of \(string\) (aligned with the last character of \(pat\)). Consider what information we can obtain:

Observation 1

If we know that the character \(char\) is not in \(pat\), we do not need to consider occurrences of \(pat\) starting from the \(1\)st, \(2\)nd, ..., \(patlen\)-th characters of \(string\), and can directly slide \(pat\) down by \(patlen\) characters.

Observation 2

More generally, if the position of the rightmost occurrence of \(char\) in \(pat\) is \(delta_1\) characters away from the end,

then we can directly slide \(pat\) backward by \(delta_1\) characters without matching: if the sliding distance is less than \(delta_1\), then the character \(char\) alone cannot be matched, and of course the pattern string \(pat\) will not be matched.

Therefore, unless the character \(char\) can match the last character of \(pat\), \(string\) should skip \(delta_1\) characters (equivalent to sliding \(pat\) backward by \(delta_1\) characters). And we can define a function \(delta_1(char)\) to compute \(delta_1\):

\[ \begin{array}{ll} \textbf{int}\ delta1(\textbf{char}\ char) \\ \qquad \textbf{if}\ \text{char is not in pat || char is the last character of pat} \\ \qquad\qquad\textbf{return}\ patlen \\ \qquad \textbf{else} \\ \qquad\qquad\textbf{return}\ patlastpos-i\quad\textbf{//}\ \text{i is the position of the rightmost occurrence of char in pat, i.e., pat[i]=char} \end{array} \]

Note that this table only needs to be computed up to position \(patlastpos-1\).

Now suppose \(char\) matches the last character of \(pat\). Then we check whether the previous character of \(char\) matches the second-to-last character of \(pat\):

If yes, continue backtracking until the entire pattern \(pat\) is matched (then we have successfully found a match of \(pat\) in \(string\));

Or, we might mismatch at the \((m+1)\)-th character from the end after matching the last \(m\) characters of \(pat\). In this case, we want to slide \(pat\) to the next possible matching position, and of course we want to slide as far as possible.

Observation 3(a)

As mentioned in Observation 2, after matching the last \(m\) characters of \(pat\), if a mismatch occurs at the \((m+1)\)-th character from the end, to align the mismatched character in \(string\) with the corresponding character in \(pat\),

we need to slide \(pat\) backward by \(k\) characters, meaning we should focus on the next \(k+m\) characters (i.e., look at the character in \(string\) aligned with the end of \(pat\) after sliding \(k\) characters).

And \(k=delta_1-m\),

so our attention should jump backward along \(string\) by \(delta_1-m+m = delta_1\) characters.

However, we have the opportunity to skip more characters. Please continue reading.

Observation 3(b)

If we know that the next \(m\) characters of \(string\) match the last \(m\) characters of \(pat\), let this substring be \(subpat\),

and we also know that after the mismatched character \(char\) in \(string\) there is a substring matching \(subpat\), and if there is a \(subpat\) in \(pat\) before the character corresponding to \(char\), we can slide \(pat\) down a distance,

so that the \(subpat\) appearing before the character in \(pat\) corresponding to \(char\) (plausible reoccurrence, hereinafter also abbreviated as pr) aligns with the \(subpat\) in \(string\). If there are multiple \(subpat\)s in \(pat\), take the first one in right-to-left suffix matching order (rightmost plausible reoccurrence, hereinafter also abbreviated as rpr).

Suppose \(pat\) slides down by \(k\) characters (i.e., the distance between the \(subpat\) at the end of \(pat\) and its rightmost plausible reoccurrence). Then our attention should slide backward along \(string\) by \(k+m\) characters. This distance is called \(delta_2(j)\):

Let \(rpr(j)\) be the position of the rightmost plausible reoccurrence of \(subpat=pat[j+1\dots patlastpos]\) when mismatching at \(pat[j]\), with \(rpr(j) < j\) (here we only give a simple definition; a more precise discussion will be in the algorithm design section). Then clearly \(k=j-rpr(j),\ m=patlastpos-j\).

Thus:

\[ \begin{array}{ll} \textbf{int}\ delta2(\textbf{int}\ j) \quad\textbf{//}\ \text{j is the position of the character in pat corresponding to the mismatched character} \\ \qquad\qquad\textbf{return}\ patlastpos-rpr(j) \\ \end{array} \]

Therefore, when a mismatch occurs, we can skip \(\max(delta_1,delta_2)\) characters forward in \(string\).

Process

The arrow points to the mismatched character \(char\):

\[ \begin{aligned} \textit{pat}:\qquad\qquad &\texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \, \, \Uparrow \end{aligned} \]

\(\texttt{F}\) does not appear in \(pat\). According to Observation 1, \(pat\) directly moves down \(patlen\) characters, i.e., 7 characters:

\[ \begin{aligned} \textit{pat}:\qquad\qquad &\qquad\quad\ \ \, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \, \, \qquad\quad\ \ \ \Uparrow \end{aligned} \]

According to Observation 2, we need to move \(pat\) down 4 characters to align the hyphen character:

\[ \begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\quad\ \ \, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\qquad \Uparrow \end{aligned} \]

Now char:\(\texttt{T}\) matches. Move the pointer on \(string\) left one step to continue matching:

\[ \begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\quad\ \ \, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\quad\ \, \Uparrow \end{aligned} \]

According to Observation 3(a), \(\texttt{L}\) mismatches. Since \(\texttt{L}\) is not in \(pat\), \(pat\) moves down \(k=delta_1-m=7-1=6\) characters, and the pointer on \(string\) moves down \(delta_1=7\) characters:

\[ \begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\qquad\qquad\ \ \,\, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\qquad\qquad\ \ \ \, \, \Uparrow \end{aligned} \]

Now \(char\) matches the last character \(\texttt{T}\) of \(pat\) again. The pointer on \(string\) moves left to match, matches \(\texttt{A}\), continues left, and finds a mismatch at character \(\texttt{-}\):

\[ \begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\qquad\qquad\ \ \,\, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\qquad\quad\ \ \ \,\, \Uparrow \end{aligned} \]

Intuitively, according to Observation 3(b), sliding \(pat\) down \(k=5\) characters to align the suffix \(\texttt{AT}\) yields the maximum sliding distance for the \(string\) pointer. Here \(delta_2=k+patlastpos-j=5+6-4=7\), meaning the pointer on \(string\) slides down 7 characters.

Formally, at this point, \(delta_1=7-1-2=4,\ delta_2=7, \max(delta_1,delta_2)= 7\), which formally supports the jump of Observation 3(b):

\[ \begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\qquad\qquad\qquad\quad \;\, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\qquad\qquad\qquad\quad \ \ \; \Uparrow \end{aligned} \]

Now we find that every character of \(pat\) equals the corresponding character in \(string\). We have found a match of \(pat\) in \(string\). Only 14 references to \(string\) were made, of which 7 were necessary comparisons for a successful match (\(patlen=7\)), and the other 7 allowed us to skip 22 characters.

Algorithm Design

The Initial Matching Algorithm

Explanation

Now consider an algorithm that uses \(delta_1\) and \(delta_2\) for string matching:

\[ \begin{array}{ll} i \gets patlastpos. \\ j \gets patlastpos. \\ \textbf{loop}\\ \qquad \textbf{if}\ j < 0 \\ \qquad \qquad \textbf{return}\ i+1 \\ \\ \qquad \textbf{if}\ string[i]=pat[j] \\ \qquad \qquad j \gets j-1 \\ \qquad \qquad i \gets i-1 \\ \qquad \qquad \textbf{continue} \\ \\ \qquad i \gets i+max(delta_1(string[i]), delta_2(j)) \\ \\ \qquad \textbf{if}\ i > stringlastpos \\ \qquad \qquad \textbf{return}\ false \\ \qquad j \gets patlastpos \\ \end{array} \]

If the above algorithm \(\textbf{return}\ false\), it indicates \(pat\) is not in \(string\); if it returns a number, it indicates the leftmost first occurrence position of \(pat\) in \(string\).

Now let's describe the \(rpr(j)\) function, which \(delta_2\) relies on, more precisely.

According to the previous definition, \(rpr(j)\) denotes the position of the rightmost plausible reoccurrence of substring \(subpat=pat[j+1\dots patlastpos]\) when mismatching at \(pat[j]\).

That is, we need to find the best \(k\) such that \(pat[k\dots k+patlastpos-j-1]=pat[j+1\dots patlastpos]\), with two special cases to consider:

When \(k<0\), it is equivalent to prepending a virtual prefix to \(pat\), which actually also conforms to the principle of \(delta_2\) jumps.
When \(k>0\), if \(pat[k-1]=pat[j]\), then this \(pat[k\dots k+patlastpos-j-1]\) cannot be a plausible reoccurrence of \(subpat\). The reason is that \(pat[j]\) itself is the mismatched character, so after sliding \(pat\) down \(k\) characters, we will still mismatch at \(pat[k-1]\) during suffix matching.

Also note two constraints:

\(k < j\). Because when \(k=j\), we have \(pat[k]=pat[j]\), and the character that mismatched at \(pat[j]\) will also mismatch at \(pat[k]\).
Considering \(delta_2(patlastpos)= 0\), we stipulate \(rpr(patlastpos) = patlastpos\).

Process

Since understanding \(rpr(j)\) is core to implementing the BoyerMoore algorithm, we use the following two examples for detailed explanation:

\[ \begin{aligned} \textit{j}:\qquad\qquad\quad\ \ &\texttt{0 1 2 3 4 5 6 7 8} \\ \textit{pat}:\qquad\qquad\ \ &\texttt{A B C X X X A B C} \\ \textit{rpr(j)}:\qquad\quad\ \ &\texttt{5 4 3 2 1 0 2 1 8} \\ \textit{sgn}:\qquad\qquad\ \ &\texttt{- - - - - - - - +} \end{aligned} \]

For \(rpr(0)\), \(subpat\) is \(\texttt{BCXXXABC}\). The rightmost plausible reoccurrence before \(pat[0]\) can only be \(\texttt{[(BCXXX)ABC]XXXABC}\), i.e., the rightmost plausible reoccurrence position is -5, so \(rpr(j)=-5\);

For \(rpr(1)\), \(subpat\) is \(\texttt{CXXXABC}\). The rightmost plausible reoccurrence before \(pat[1]\) is \(\texttt{[(CXXX)ABC]XXXABC}\), so \(rpr(j)=-4\);

For \(rpr(2)\), \(subpat\) is \(\texttt{XXXABC}\). The rightmost plausible reoccurrence before \(pat[2]\) is \(\texttt{[(XXX)ABC]XXXABC}\), so \(rpr(j)=-3\);

For \(rpr(3)\), \(subpat\) is \(\texttt{XXABC}\). The rightmost plausible reoccurrence before \(pat[3]\) is \(\texttt{[(XX)ABC]XXXABC}\), so \(rpr(j)=-2\);

For \(rpr(4)\), \(subpat\) is \(\texttt{XABC}\). The rightmost plausible reoccurrence before \(pat[4]\) is \(\texttt{[(X)ABC]XXXABC}\), so \(rpr(j)=-1\);

For \(rpr(5)\), \(subpat\) is \(\texttt{ABC}\). The rightmost plausible reoccurrence before \(pat[5]\) is \(\texttt{[ABC]XXXABC}\), so \(rpr(j)=0\);

For \(rpr(6)\), \(subpat\) is \(\texttt{BC}\). Since \(string[0]=string[6]\), i.e., \(string[0]\) equals the mismatched character \(string[6]\), \(string[0\dots 2]\) is not a plausible reoccurrence of \(subpat\) that meets the conditions. So the rightmost plausible reoccurrence is \(\texttt{[(BC)]ABCXXXABC}\), so \(rpr(j)=-2\);

For \(rpr(7)\), \(subpat\) is \(\texttt{C}\). Similarly, since \(string[7]=string[1]\), \(string[1\dots 2]\) is not a plausible reoccurrence of \(subpat\) that meets the conditions. The rightmost plausible reoccurrence is \(\texttt{[(C)]ABCXXXABC}\), so \(rpr(j)=-1\);

For \(rpr(8)\), by definition of \(delta_2\), \(rpr(patlastpos)=patlastpos\), so \(rpr(8)=8\).

Now look at another example:

\[ \begin{aligned} \textit{j}:\qquad\qquad\quad\ \ &\texttt{0 1 2 3 4 5 6 7 8} \\ \textit{pat}:\qquad\qquad\ \ &\texttt{A B Y X C D E Y X} \\ \textit{rpr(j)}:\qquad\quad\ \ &\texttt{8 7 6 5 4 3 2 1 8} \\ \textit{sgn}:\qquad\qquad\ \ &\texttt{- - - - - - + - +} \end{aligned} \]

For \(rpr(0)\), \(subpat\) is \(\texttt{BYXCDEYX}\). The rightmost plausible reoccurrence before \(pat[0]\) can only be \(\texttt{[(BYXCDEYX)]ABYXCDEYX}\), i.e., the rightmost plausible reoccurrence position is -8, so \(rpr(j)=-8\);

For \(rpr(1)\), \(subpat\) is \(\texttt{YXCDEYX}\). The rightmost plausible reoccurrence before \(pat[1]\) can only be \(\texttt{[(YXCDEYX)]ABYXCDEYX}\), \(rpr(j)=-7\);

For \(rpr(2)\), \(subpat\) is \(\texttt{XCDEYX}\). The rightmost plausible reoccurrence before \(pat[2]\) can only be \(\texttt{[(XCDEYX)]ABYXCDEYX}\), \(rpr(j)=-6\);

For \(rpr(3)\), \(subpat\) is \(\texttt{CDEYX}\). The rightmost plausible reoccurrence before \(pat[3]\) can only be \(\texttt{[(CDEYX)]ABYXCDEYX}\), \(rpr(j)=-5\);

For \(rpr(4)\), \(subpat\) is \(\texttt{DEYX}\). The rightmost plausible reoccurrence before \(pat[4]\) can only be \(\texttt{[(DEYX)]ABYXCDEYX}\), \(rpr(j)=-4\);

For \(rpr(5)\), \(subpat\) is \(\texttt{EYX}\). The rightmost plausible reoccurrence before \(pat[5]\) can only be \(\texttt{[(EYX)]ABYXCDEYX}\), \(rpr(j)=-3\);

For \(rpr(6)\), \(subpat\) is \(\texttt{YX}\). Since \(string[2\dots 3]=string[7\dots 8]\) and \(string[6]\neq string[1]\), the rightmost plausible reoccurrence before \(pat[6]\) is \(\texttt{AB[YX]CDEYX}\), \(rpr(j)=2\);

For \(rpr(7)\), \(subpat\) is \(\texttt{X}\). Although \(string[3]=string[8]\), because \(string[2] = string[7]\), the rightmost plausible reoccurrence before \(pat[7]\) is \(\texttt{[X]ABYXCDEYX}\), \(rpr(j)=-1\);

For \(rpr(8)\), by definition of \(delta_2\), \(rpr(patlastpos)=patlastpos\), so \(rpr(8)=8\).

An Improvement to the Matching Algorithm

Finally, considering that in practice about 80% of the time during search is spent on the jumps of Observation 1, i.e., when \(string[i]\) and \(pat[patlastpos]\) do not match, then skipping the entire \(patlen\) for the next match.

Thus, we can optimize specifically for this:

We define a \(delta0\):

\[ \begin{array}{ll} \textbf{int}\ delta0(\textbf{char}\ char) \\ \qquad \textbf{if}\ char=pat[patlastpos] \\ \qquad\qquad \textbf{return}\ large\ \ \text{// large is an integer, need to satisfy large>stringlastpos+patlen} \\ \qquad \textbf{return}\ delta1(char) \end{array} \]

Using \(delta0\) instead of \(delta_1\), we get the improved matching algorithm:

\[ \begin{array}{ll} i \gets patlastpos \\ \textbf{loop} \\ \qquad\textbf{if} \ i > stringlastpos \\ \qquad\qquad\textbf{return}\ false\\ \\ \qquad\textbf{while}\ i < stringlen \\ \qquad\qquad i \gets i+delta0(string(i)) \ \ \text{// Unless string[i] matches the last character of pat, slide at most patlen }\\\ \qquad\textbf{if}\ i \leqslant\ large \qquad\qquad\qquad\qquad \text{// This means no character in string matches the last character of pat}\ \\ \qquad\qquad\textbf{return}\ false\\ \\ \qquad i \gets i-large \\ \qquad j \gets patlastpos. \\ \qquad\textbf{while}\ j \geqslant\ 0 \ and \ string[i]=pat[j]\\ \qquad \qquad j \gets j-1 \\ \qquad \qquad i \gets i-1 \\ \\ \qquad \textbf{if}\ j < 0 \\ \qquad \qquad \textbf{return}\ i+1 \\ \qquad i \gets i+max(delta_1(string[i]), delta_2(j)) \\ \\ \end{array} \]

Here \(large\) serves multiple purposes: first, similar to the Horspool algorithm for fast bad character jumps; second, assisting in detecting whether the string search is complete.

After this improvement, compared to the original algorithm, unnecessary \(delta_2\) calculations are avoided during Observation 1 jumps, resulting in a significant performance improvement in string searches under typical character sets.

Details of delta2 Construction

Introduction

In the October 1977 issue of Communications of the ACM, Boyer and Moor's paper¹ only described the \(delta_2\) static table.

The specific implementation discussion for constructing \(delta_2\) appeared in the June 1977 paper² by Knuth, Morris, and Pratt formally published in SIAM Journal on Computing.

Naive Algorithm

Before introducing Knuth's \(delta_2\) construction algorithm, according to the definition, we have a naive algorithm suitable for small-scale problems:

For each position i in the interval [0, patlen), determine the interval of reoccurrence positions based on the length of subpat, i.e., [-subpatlen, i];
Possible reoccurrence positions are compared character by character from right to left, looking for the rightmost \(subpat\) reoccurrence that meets the \(delta_2\) requirements;
Finally, don't forget to set \(delta_2(lastpos)= 0\).

Implementation

use std::cmp::PartialEq;

pub fn build_delta_2_table_naive(p: &[impl PartialEq]) -> Vec<usize> {
    let patlen = p.len();
    let lastpos = patlen - 1;
    let mut delta_2 = vec![];

    for i in 0..patlen {
        let subpatlen = (lastpos - i) as isize;

        if subpatlen == 0 {
            delta_2.push(0);
            break;
        }

        for j in (-subpatlen..(i + 1) as isize).rev() {
            // subpat match
            if (j..j + subpatlen)
            .zip(i + 1..patlen)
            .all(|(rpr_index, subpat_index)| {
                if rpr_index < 0 {
                    return true;
                }

                if p[rpr_index as usize] == p[subpat_index] {
                    return true;
                }

                false
            })
            && (j <= 0 || p[(j - 1) as usize] != p[i])
            {
                delta_2.push((lastpos as isize - j) as usize);
                break;
            }
        }
    }

    delta_2
}

Specifically, necessary explanations for Rust language features are given here and will not be repeated later:

usize and isize are unsigned and signed integers with the same number of bytes as memory pointers, equivalent to u32 and i32 on 32-bit machines, and u64 and i64 on 64-bit machines.
When indexing arrays, vectors, or slices, use numbers of type usize (because random memory access is performed and indices cannot be negative). So if negative values need to be handled, use isize, but when indexing, use usize again. This is where explicit conversion between the two using the as keyword is seen.
impl PartialEq is only used for generics, supporting both Unicode-encoded char and binary u8.

Clearly, the time complexity of this brute-force algorithm is \(O(n^3)\).

Efficient Algorithm

Below we introduce an efficient algorithm with time complexity \(O(n)\) but requiring extra \(O(n)\) space complexity.

Although Knuth proposed this construction method in 1977, his original version had a flaw; for some \(pat\), it could not produce a \(delta_2\) conforming to the definition.

Rytter's 1980 article³ in SIAM Journal on Computing proposed a correction. The following is the construction algorithm for \(delta_2\):

First, considering that the definition of \(delta_2\) is complex, we classify based on the reoccurrence position of \(subpat\) and handle each category separately. This is the key idea for efficient implementation.

According to the distance of reoccurrence positions from far to near, i.e., offset from large to small, they are divided into the following categories:

The entire \(subpat\) reoccurrence position is completely to the left of \(pat\), e.g., \(\texttt{[(EYX)]ABYXCDEYX}\). In this case, \(delta_2(j) = patlastpos\times 2 - j\);
Part of \(subpat\)'s reoccurrence is to the left of \(pat\), and part is at the head of \(pat\), e.g., \(\texttt{[(XX)ABC]XXXABC}\). In this case, \(patlastpos < delta_2(j) < patlastpos\times 2 - j\); We also classify the marginal case where \(subpat\) is completely at the head of \(pat\) here (of course, depending on implementation, it can also be classified below), e.g., \(\texttt{[ABC]XXXABC}\). In this case, \(patlastpos = delta_2(j)\);
\(subpat\)'s reoccurrence is completely within \(pat\), e.g., \(\texttt{AB[YX]CDEYX}\). In this case, \(delta_2(j) < patlastpos\).

Now let's discuss how to efficiently compute these three cases:

First Case

This is the simplest case, requiring only one traversal and can initialize \(delta_2\) along the way.

Second Case

We observe when does \(subpat\)'s reoccurrence have part to the left of \(pat\) and part at the head of \(pat\)? It should be when some suffix of \(subpat\) equals some prefix of \(pat\),

like the previous example:

\[ \begin{aligned} \textit{j}:\qquad\qquad\quad\ \ &\texttt{0 1 2 3 4 5 6 7 8} \\ \textit{pat}:\qquad\qquad\ \ &\texttt{A B C X X X A B C} \\ \end{aligned} \]

For \(delta_2(3)\)'s reoccurrence \(\texttt{[(XX)ABC]XXXABC}\), the suffix of \(subpat\) \(\texttt{XXABC}\) and the prefix of pat have an equal part, which is \(\texttt{ABC}\).

Actually, the key to computing the second and third cases relies on the computation and application of the prefix function.

So as long as \(j\) takes values such that \(subpat\) contains this equal suffix, we can get the reoccurrence of \(subpat\) for the second case. For the example, we only need \(j \leqslant 5\),

and when \(j = 5\), it is the marginal case where \(subpat\) is completely at the head of \(pat\).

We can compute \(delta_2(j)\) at this point:

Let the length of this pair of equal prefix-suffix be \(\textit{prefixlen}\). Then \(subpatlen = patlastpos - j\), so the length of the part to the left of \(pat\) is \(subpatlen-\textit{prefixlen}\),

and \(rpr(j) = -(subpatlen-\textit{prefixlen})\), so \(delta_2(j) = patlastpos - rpr(j) = patlastpos \times 2 - j - \textit{prefixlen}\).

There may be multiple pairs of equal prefixes and suffixes afterward, e.g.:

\[ \begin{aligned} \textit{j}:\qquad\qquad\quad\ \ &\texttt{0 1 2 3 4 5 6 7 8 9} \\ \textit{pat}:\qquad\qquad\ \ &\texttt{A B A A B A A B A A} \\ \end{aligned} \]

At \(j\leq2\), there is \(\texttt{ABAABAA}\); at \(2< j \leq 5\), there is \(\texttt{ABAA}\); at \(5<j\leq8\), there is \(\texttt{A}\).

The flaw in Knuth's algorithm is that it only considered the longest pair, but actually we need to consider all cases where \(subpat\) suffixes equal \(pat\) prefixes, which is equivalent to computing all cases where \(pat\)'s true suffixes equal true prefixes, and computing different \(delta_2(j)\) for \(j\) in intervals according to length from large to small.

Using the prefix function and inversely applying the state transition equation for computing the prefix function: \(j^{(n)} = \pi[j^{(n-1)}-1]\), to obtain all equal true prefix and true suffix lengths of \(pat\). Start from \(\pi[patlastpos]\) as the length of the longest pair, then run the state transition equation inversely to get the next longest equal true prefix and true suffix length.

This completes the computation of \(delta_2\) for the second case.

Third Case

\(subpat\)'s reoccurrence is exactly within \(pat\) (excluding the head of \(pat\)), i.e., searching for \(subpat\) in \(pat[0\dots patlastpos-1]\) in right-to-left order.

If solved with the BM algorithm, we get a recursive implementation of BM for the third case, with the termination condition \(patlen \leqslant 2\).

Moreover, according to the definition of \(delta_2\), the next character (i.e., the one to the left) of the found \(subpat\) reoccurrence cannot be the same as the next character of \(subpat\) as a suffix of \(pat\).

This inspires us well: we can use a process similar to computing the prefix function for the third case, but it's a left-right reversed prefix function:

Two pointers point to the left endpoint of the substring and the "prefix" position of the longest common prefix-suffix of the substring, moving from right to left. When the two characters they point to are equal, continue moving, which means the "prefix" becomes larger;
When the two characters are not equal, the previously equal part satisfies the requirement of \(delta_2\) for reoccurrence, and backtrack the pointer pointing to the "prefix" position until a new character equality is formed or it goes out of bounds.

Like the prefix function, an auxiliary array is needed for backtracking, which can use the space of the prefix array generated earlier for the second case.

Implementation

The above implementation

use std::cmp::PartialEq;
use std::cmp::min;

pub fn build_delta_2_table_improved_minghu6(p: &[impl PartialEq]) -> Vec<usize> {
    let patlen = p.len();
    let lastpos = patlen - 1;
    let mut delta_2 = Vec::with_capacity(patlen);

    // First case
    // delta_2[j] = lastpos * 2 - j
    for i in 0..patlen {
        delta_2.push(lastpos * 2 - i);
    }

    // Second case
    // lastpos <= delata2[j] = lastpos * 2 - j
    let pi = compute_pi(p);  // Compute prefix function
    let mut i = lastpos;
    let mut last_i = lastpos; // Just for initialization
    while pi[i] > 0 {
        let start;
        let end;

        if i == lastpos {
            start = 0;
        } else {
            start = patlen - pi[last_i];
        }

        end = patlen - pi[i];

        for j in start..end {
            delta_2[j] = lastpos * 2 - j - pi[i];
        }

        last_i = i;
        i = pi[i] - 1;
    }

    // Third case
    // delata2[j] < lastpos
    let mut j = lastpos;
    let mut t = patlen;
    let mut f = pi;
    loop {
        f[j] = t;
        while t < patlen && p[j] != p[t] {
            // Use min function to ensure later possible backtracking does not overwrite previous data
            delta_2[t] = min(delta_2[t], lastpos - 1 - j);
            t = f[t];
        }

        t -= 1;
        if j == 0 {
            break;
        }
        j -= 1;
    }

    // No practical meaning, just for complete definition
    delta_2[lastpos] = 0;

    delta_2
}

Galil Rule Improvement for Worst-Case in Multiple Matches

On Multiple Matching Problem for Suffix Matching Algorithms

Previous search algorithms only involved finding the first \(pat\) match in \(string\), but for finding all \(pat\) matches in \(string\), there are many different algorithmic ideas. The core concern of this problem is: how to utilize information from previously successfully matched characters to reduce the worst-case time complexity to linear.

After an original successful match, simply sliding the \(string\) pointer backward by \(patlen\) distance and restarting suffix matching would cause the worst-case time complexity to return to \(O(mn)\) (by convention, \(m\) is \(patlen\), \(n\) is \(stringlen\), same below).

For example, an extreme case: \(pat\): \(\texttt{AAA}\), \(string\): \(\texttt{AAAAA}\dots\).

Knuth proposed a method using a "finite number" of states to record \(patlen\) length characters. This algorithm guarantees that each character in \(string\) is compared at most once, but the cost is that this "finite number" of states may not be small. For a \(pat\) with distinct characters, \(\dfrac{1}{2}m^{2}+m\) states are needed.

The following introduces the Galil algorithm⁴, which is simple and requires no extra preprocessing overhead.

Galil Rule

Assume a \(pat\) that is a prefix of a string \(UUUU\dots\) formed by repeating some substring \(U\) n times. Then we call \(U\) a period of \(pat\).

For example, \(pat: \texttt{ABCABCAB}\) is a prefix of \(\texttt{ABC}\) repeated \(\texttt{ABCABCABC}\), so the length of \(\texttt{ABC}\), \(3\), is the period length of this \(pat\), i.e., \(pat\) satisfies \(pat[i] = pat[i+3]\).

\(pat\) has at least one period of length itself. We define the shortest period as \(k\), \(k\leq patlen\).

During search, if our \(pat\) successfully completes a match, then according to period characteristics, we only need to slide \(string\) backward by \(k\) characters and compare whether these \(k\) characters correspond equally to directly determine if there is another match of \(pat\).

To compute this shortest period length, we assume we know an equal pair of prefix-suffix of \(pat\). Let their length be \(\textit{prefixlen}\). Then \(pat[i] = pat[i+(patlen-\textit{prefixlen})]\). Thus we get a period of length \(patlen-\textit{prefixlen}\).

When we know the longest equal prefix-suffix pair of \(pat\), we get the shortest period of \(pat\).

And the longest equal prefix-suffix length, \(\pi[patlastpos]\), is already obtained during our computation of \(delta_2\), so actually no extra preprocessing time and space are needed to improve the worst-case time complexity of the suffix matching algorithm to linear.

Final implementation of BM search algorithm incorporating the above optimizations

#[cfg(target_pointer_width = "64")]
const LARGE: usize = 10_000_000_000_000_000_000;

#[cfg(not(target_pointer_width = "64"))]
const LARGE: usize = 2_000_000_000;

pub struct BMPattern<'a> {
    pat_bytes: &'a [u8],
    delta_1: [usize; 256],
    delta_2: Vec<usize>,
    k: usize  // Shortest period length of pat
}

impl<'a> BMPattern<'a> {
    // ...

    pub fn find_all(&self, string: &str) -> Vec<usize> {
        let mut result = vec![];
        let string_bytes = string.as_bytes();
        let stringlen = string_bytes.len();
        let patlen = self.pat_bytes.len();
        let pat_last_pos = patlen - 1;
        let mut string_index = pat_last_pos;
        let mut pat_index;
        let l0 =  patlen - self.k;
        let mut l = 0;

        while string_index < stringlen {
            let old_string_index = string_index;

            while string_index < stringlen {
                string_index += self.delta0(string_bytes[string_index]);
            }
            if string_index < LARGE {
                break;
            }

            string_index -= LARGE;

            // If string_index moves, it means at least one failed match occurred since the last successful match.
            // At this time, the offset for the second match of Galil rule needs to be reset to zero.
            if old_string_index < string_index {
                l = 0;
            }

            pat_index = pat_last_pos;

            while pat_index > l && string_bytes[string_index] == self.pat_bytes[pat_index] {
                string_index -= 1;
                pat_index -= 1;
            }

            if pat_index == l && string_bytes[string_index] == self.pat_bytes[pat_index] {
                result.push(string_index - l);

                string_index += pat_last_pos - l + self.k;
                l = l0;
            } else {
                l = 0;
                string_index += max(
                    self.delta_1[string_bytes[string_index] as usize],
                    self.delta_2[pat_index],
                );
            }
        }

        result
    }
}

Worst-Case Performance Impact in Practice

From a practical perspective, theoretical worst cases are not easy to affect performance. Even in random text tests with a small character set of only 4, the impact of such worst cases is too small to observe.

Therefore, without good design, using the Galil rule may drag down average performance slightly, but for some extremely special \(pat\) and \(string\) like the example: \(pat\): \(\texttt{AAA}\), \(string\): \(\texttt{AAAAA}\dots\), applying the Galil rule does improve performance several times.

Improved Algorithms

Simplified Boyer–Moore Algorithm

The most complex part of the BM algorithm is the construction of the \(delta_2\) table (i.e., the good suffix table). In practice, it is found that matching performance on general character sets mainly relies on the \(delta_1\) table (i.e., the bad character table). Thus, a simplified version of BM using only the \(delta_1\) table appeared, usually with little performance difference from the original.

Boyer–Moore–Horspol Algorithm

The Horspol algorithm is also based on the bad character rule, applying \(delta_1\) on the character aligned with the tail of \(pat\). The effect is similar to the improvement of the original matching algorithm, usually performing better than the original version.

Implementation

pub struct HorspoolPattern<'a> {
    pat_bytes: &'a [u8],
    bm_bc: [usize; 256],
}

impl<'a> HorspoolPattern<'a> {
    // ...
    pub fn find_all(&self, string: &str) -> Vec<usize> {
        let mut result = vec![];
        let string_bytes = string.as_bytes();
        let stringlen = string_bytes.len();
        let pat_last_pos = self.pat_bytes.len() - 1;
        let mut string_index = pat_last_pos;

        while string_index < stringlen {
            if &string_bytes[string_index-pat_last_pos..string_index+1] == self.pat_bytes {
                result.push(string_index-pat_last_pos);
            }

            string_index += self.bm_bc[string_bytes[string_index] as usize];
        }

        result
    }
}

Boyer–Moore–Sunday Algorithm

The Sunday algorithm also uses the bad character rule, but goes further than Horspool by directly focusing on the next character after the character aligned with the tail of \(pat\).

Implementing it only requires slight modification of the \(delta_1\) table, equivalent to constructing on a \(pat\) of length \(patlen+1\).

The Sunday algorithm is usually one of the simplest to implement and has one of the best average performance in general cases, usually performing slightly better than Horspool and BM.

Implementation

pub struct SundayPattern<'a> {
    pat_bytes: &'a [u8],
    sunday_bc: [usize; 256],
}

impl<'a> SundayPattern<'a> {
    // ...
    fn build_sunday_bc(p: &'a [u8]) -> [usize; 256] {
        let mut sunday_bc_table = [p.len() + 1; 256];

        for i in 0..p.len() {
            sunday_bc_table[p[i] as usize] = p.len() - i;
        }

        sunday_bc_table
    }

    pub fn find_all(&self, string: &str) -> Vec<usize> {
        let mut result = vec![];
        let string_bytes = string.as_bytes();
        let pat_last_pos = self.pat_bytes.len() - 1;
        let stringlen = string_bytes.len();
        let mut string_index = pat_last_pos;

        while string_index < stringlen {
            if &string_bytes[string_index - pat_last_pos..string_index+1] == self.pat_bytes {
                result.push(string_index - pat_last_pos);
            }

            if string_index + 1 == stringlen {
                break;
            }

            string_index += self.sunday_bc[string_bytes[string_index + 1] as usize];
        }

        result
    }
}

BMHBNFS Algorithm

This algorithm combines Horspool and Sunday, and is the algorithm used in CPython's implementation of the stringlib module's find function⁵, hereinafter referred to as B5S.

The basic idea of B5S is:

Following the suffix matching idea, first compare whether the character at position \(patlastpos\) matches. If equal, compare whether the characters at positions \(0\dots patlastpos-1\) match. If still equal, then a match is found;
If any stage mismatches, enter the jump phase;
In the jump phase, first observe the next character after position \(patlastpos\) whether it is in \(pat\). If not, directly slide right by \(patlen+1\), which is the maximum utilization of Sunday's algorithm;

If this character is in \(pat\), use \(delta_1\) for Horspool jump on the character at \(patlastpos\).

Depending on whether time saving or space saving is the primary goal, the algorithm can have vastly different implementations.

Time-Saving Version

Implementation

pub struct B5STimePattern<'a> {
    pat_bytes: &'a [u8],
    alphabet: [bool;256],
    bm_bc: [usize;256],
    k: usize
}

impl<'a> B5STimePattern<'a> {
    pub fn new(pat: &'a str) -> Self {
        assert_ne!(pat.len(), 0);

        let pat_bytes = pat.as_bytes();
        let (alphabet, bm_bc, k) = B5STimePattern::build(pat_bytes);

        B5STimePattern { pat_bytes, alphabet, bm_bc, k }
    }

    fn build(p: &'a [u8]) -> ([bool;256], [usize;256], usize)  {
        let mut alphabet = [false;256];
        let mut bm_bc = [p.len(); 256];
        let lastpos = p.len() - 1;

        for i in 0..lastpos {
            alphabet[p[i] as usize] = true;
            bm_bc[p[i] as usize] = lastpos - i;
        }

        alphabet[p[lastpos] as usize] = true;

        (alphabet, bm_bc, compute_k(p))
    }

    pub fn find_all(&self, string: &str) -> Vec<usize> {
        let mut result = vec![];
        let string_bytes = string.as_bytes();
        let pat_last_pos = self.pat_bytes.len() - 1;
        let patlen = self.pat_bytes.len();
        let stringlen = string_bytes.len();
        let mut string_index = pat_last_pos;
        let mut offset = pat_last_pos;
        let offset0 = self.k - 1;

        while string_index < stringlen {
            if string_bytes[string_index] == self.pat_bytes[pat_last_pos] {
                if &string_bytes[string_index-offset..string_index] == &self.pat_bytes[pat_last_pos-offset..pat_last_pos] {
                    result.push(string_index-pat_last_pos);

                    offset = offset0;

                    // Galil rule
                    string_index += self.k;
                    continue;
                }
            }

            if string_index + 1 == stringlen {
                break;
            }

            offset = pat_last_pos;

            if !self.alphabet[string_bytes[string_index+1] as usize] {
                string_index += patlen + 1;  // sunday
            } else {
                string_index += self.bm_bc[string_bytes[string_index] as usize];  // horspool
            }
        }

        result
    }
}

This version of B5S performs very ideally and is usually the fastest among the suffix matching series algorithms introduced so far.

Space-Saving Version

Also implemented in CPython stringlib, it uses two integers to approximate the role of the character table and \(delta_1\), greatly saving space:

Use a simple Bloom filter to replace the character table (alphabet)

Implementation

pub struct BytesBloomFilter {
    mask: u64,
}

impl BytesBloomFilter {
    pub fn new() -> Self {
        SimpleBloomFilter {
            mask: 0,
        }
    }

    fn insert(&mut self, byte: &u8) {
        (self.mask) |= 1u64 << (byte & 63);
    }

    fn contains(&self, char: &u8) -> bool {
        (self.mask & (1u64 << (byte & 63))) != 0
    }
}

The Bloom filter is a Set-type data structure designed to greatly save storage space at the cost of accuracy (and also runtime). Its characteristic is that it may misjudge items not in the set as present (False Positives, FP), but will not judge items in the set as absent (False Negatives, FN). Therefore, using it may not achieve the maximum character jump due to FP, but will not skip characters that should match due to FN.

Theoretically, the above "Bloom filter" implementation has an FP probability of about 0.5 when \(pat\) length is 50 Bytes, and about 0.15 when \(pat\) length is 10 Bytes.

Although this is not a standard Bloom filter—first, it does not use a real hash function; actually it's just a character mapping, mapping bytes 0-255 to the number formed by its first six bits.

But considering we are performing character search in memory, this simplification is very important. Even using the currently known fastest non-cryptographic hash algorithm xxHash, the time required for computation is still an order of magnitude higher.

Also, when pat is below 30 bytes, to achieve the best FP probability, more than one hash function is needed. But this is not very meaningful, because an array with two u128 numbers can already construct the full character set of the character table.

Use \(delta_1(pat[patlastpos])\) instead of the entire \(delta_1\)

Observe \(delta_1\). The most common usage is when the first character mismatches during suffix matching, which is the most common mismatch situation. So let skip = delta1(pat[patlastpos]),

When mismatching in the first stage, directly slide down skip characters; but when mismatching in the second stage, due to lack of information of the entire \(delta_1\), can only slide down one character.

Implementation

pub struct B5SSpacePattern<'a> {
    pat_bytes: &'a [u8],
    alphabet: BytesBloomFilter,
    skip: usize,
}

impl<'a> B5SSpacePattern<'a> {
    pub fn new(pat: &'a str) -> Self {
        assert_ne!(pat.len(), 0);

        let pat_bytes = pat.as_bytes();
        let (alphabet, skip) = B5SSpacePattern::build(pat_bytes);

        B5SSpacePattern { pat_bytes, alphabet, skip}
    }

    fn build(p: &'a [u8]) -> (BytesBloomFilter, usize)  {
        let mut alphabet = BytesBloomFilter::new();
        let lastpos = p.len() - 1;
        let mut skip = p.len();

        for i in 0..p.len()-1 {
            alphabet.insert(&p[i]);

            if p[i] == p[lastpos] {
                skip = lastpos - i;
            }
        }

        alphabet.insert(&p[lastpos]);

        (alphabet, skip)
    }

    pub fn find_all(&self, string: &'a str) -> Vec<usize> {
        let mut result = vec![];
        let string_bytes = string.as_bytes();
        let pat_last_pos = self.pat_bytes.len() - 1;
        let patlen = self.pat_bytes.len();
        let stringlen = string_bytes.len();
        let mut string_index = pat_last_pos;

        while string_index < stringlen {
            if string_bytes[string_index] == self.pat_bytes[pat_last_pos] {
                if &string_bytes[string_index-pat_last_pos..string_index] == &self.pat_bytes[..patlen-1] {
                    result.push(string_index-pat_last_pos);
                }

                if string_index + 1 == stringlen {
                    break;
                }

                if !self.alphabet.contains(&string_bytes[string_index+1]) {
                    string_index += patlen + 1;  // sunday
                } else {
                    string_index += self.skip;  // horspool
                }
            } else {
                if string_index + 1 == stringlen {
                    break;
                }

                if !self.alphabet.contains(&string_bytes[string_index+1]) {
                    string_index += patlen + 1;  // sunday
                } else {
                    string_index += 1;
                }
            }

        }

        result
    }
}

This version of the algorithm is not as fast as the previous suffix matching algorithms, but the gap is not large. Performance is still better than KMP, benefiting from its excellent space complexity of at most two u64 integers.

Theoretical Analysis

The following shows the performance of various algorithms under general character sets. The vertical axis is similar to execution cost (cost refers to the cost when mismatching after successfully matching m characters; skip refers to the probability of sliding down k characters when a mismatch occurs). The smaller, the better. The horizontal axis is the length of the pattern string pat:

String search algorithm performance comparison chart

Performance in smaller character sets (DNA {A, C, T, G} base pair sequences):

Small character set string search algorithm performance comparison chart

In summary, in larger character sets, such as daily searches, the superior performance of the BoyerMoore series algorithms mainly relies on the \(delta_1\) table for character jumps;

On the other hand, in smaller character sets, the role of \(delta_1\) decreases, and the role of \(delta_2\) is demonstrated.

If there is some spare space, the full BoyerMoore algorithm with space complexity \(O(m)\) is more universal and has the best overall performance.

References and Notes

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用