跳转至

Boyer–Moore 算法

前置知识:前缀函数与 KMP 算法

KMP 算法将前缀匹配的信息用到了极致,

而 BM 算法背后的基本思想是通过后缀匹配获得比前缀匹配更多的信息来实现更快的字符跳转。

引入

想象一下,如果我们的的模式字符串 pat,被放在文本字符串 string 的左手起头部,使它们的第一个字符对齐。

pat:EXAMPLEstring:HERE IS A SIMPLE EXAMPLE   

在这里做定义,往后不赘述:

pat 的长度为 patlen,特别地对于从 0 开始的串来说,规定 patlastpos=patlen1pat 串最后一个字符的位置;

string 的长度 stringlenstringlastpos=stringlen1

假如我们知道了 string 的第 patlen 个字符 char(与 pat 的最后一个字符对齐)考虑我们能得到什么信息:

观察 1

如果我们知道 char 这个字符不在 pat 中,我们就不用考虑 patstring 的第 1 个、第 2 个……第 patlen 个字符起出现的情况,,而可以直接将 pat 向下滑动 patlen 个字符。

观察 2

更一般地,如果出现在 pat 最末尾(也就是最右边)的那一个 char 字符的位置是离末尾端差了 delta1 个字符

那么就可以不用匹配,直接将 pat 向后滑动 delta1 个字符:如果滑动距离少于 delta1,那么仅就 char 这个字符就无法被匹配,当然模式字符串 pat 也就不会被匹配。

因此除非 char 字符可以和 pat 末尾的那个字符匹配,否则 string 要跳过 delta1 个字符(相当于 pat 向后滑动了 delta1 个字符)。并且我们可以得到一个计算 delta1 的函数 delta1(char)

int delta1(char char)if char不在pat中 || char是pat上最后一个字符return patlenelsereturn patlastposi// i为出现在pat最末尾的那一个char出现的位置,即pat[i]=char

注意:显然这个表只需计算到 patlastpos1 的位置

现在假设 charpat 最后一个字符匹配到了,那我们就看看 char 前一个字符和 pat 的倒数第二个字符是否匹配:

如果是,就继续回退直到整个模式串 pat 完成匹配(这时我们就在 string 上成功得到了一个 pat 的匹配);

或者,我们也可能会在匹配完 pat 的倒数第 m 个字符后,在倒数第 m+1 个字符上失配,这时我们就希望把 pat 向后滑动到下一个可能会实现匹配的位置,当然我们希望滑动得越远越好。

观察 3(a)

观察 2 中提到,当匹配完 pat 的倒数 m 个字符后,如果在倒数第 m+1 个字符失配,为了使得 string 中的失配字符与 pat 上对应字符对齐,

需要把 pat 向后滑动 k 个字符,也就是说我们应该把注意力看向之后的 k+m 个字符(也就是看向 pat 滑动 k 之后,末段与 string 对齐的那个字符)。

k=delta1m

所以我们的注意力应该沿着 string 向后跳 delta1m+m=delta1 个字符。

然而,我们有机会跳过更多的字符,请继续看下去。

观察 3(b)

如果我们知道 string 接下来的 m 个字符和 pat 的最后 m 个字符匹配,假设这个子串为 subpat

我们还知道在 string 失配字符 char 后面是与 subpat 相匹配的子串,而假如 pat 对应失配字符前面存在 subpat,我们可以将 pat 向下滑动一段距离,

使得失配字符 charpat 上对应的字符前面出现的 subpat(合理重现,plausible reoccurrence,以下也简称 pr)与 stringsubpat 对齐。如果 pat 上有多个 subpat,按照从右到左的后缀匹配顺序,取第一个(rightmost plausible reoccurrence,以下也简称 rpr)。

假设此时 pat 向下滑动的 k 个字符(也即 pat 末尾端的 subpat 与其最右边的合理重现的距离),这样我们的注意力应该沿着 string 向后滑动 k+m 个字符,这段距离我们称之为 delta2(j)

假定 rpr(j)subpat=pat[j+1patlastpos]pat[j] 上失配时的最右边合理重现的位置,rpr(j)<j(这里只给出简单定义,在下文的算法设计章节里会有更精确的讨论),那么显然 k=jrpr(j), m=patlastposj

所以有:

int delta2(int j)// j为失配字符在pat上对应字符的位置return patlastposrpr(j)

于是我们在失配时,可以把把 string 上的注意力往后跳过 max(delta1,delta2) 个字符

过程

箭头指向失配字符 char

pat:AT-THATstring:    WHICH-FINALLY-HALTS.--AT-THAT-POINT   

F 没有出现 pat 中,根据 观察 1pat 直接向下移动 patlen 个字符,也就是 7 个字符:

pat:  AT-THATstring:    WHICH-FINALLY-HALTS.--AT-THAT-POINT      

根据 观察 2,我们需要将 pat 向下移动 4 个字符使得短横线字符对齐:

pat:  AT-THATstring:    WHICH-FINALLY-HALTS.--AT-THAT-POINT   

现在char:T 匹配了,把 string 上的指针左移一步继续匹配:

pat:  AT-THATstring:    WHICH-FINALLY-HALTS.--AT-THAT-POINT    

根据 观察 3(a)L 失配,因为 L 不在 pat 中,所以 pat 向下移动 k=delta1m=71=6 个字符,而 string 上指针向下移动 delta1=7 个字符:

pat:  AT-THATstring:    WHICH-FINALLY-HALTS.--AT-THAT-POINT      

这时 char 又一次匹配到了 pat 的最后一个字符 Tstring 上的指针向左匹配,匹配到了 A,继续向左匹配,发现在字符 - 失配:

pat:  AT-THATstring:    WHICH-FINALLY-HALTS.--AT-THAT-POINT      

显然直观上看,此时根据 观察 3(b),将 pat 向下移动 k=5 个字符,使得后缀 AT 对齐,这种滑动可以获得 string 指针最大的滑动距离,此时 delta2=k+patlastposj=5+64=7,即 string 上指针向下滑动 7 个字符。

而从形式化逻辑看,此时,delta1=712=4, delta2=7,max(delta1,delta2)=7, 这样从形式逻辑上支持了进行 观察 3(b) 的跳转:

pat:AT-THATstring:    WHICH-FINALLY-HALTS.--AT-THAT-POINT     

现在我们发现了 pat 上每一个字符都和 string 上对应的字符相等,我们在 string 上找到了一个 pat 的匹配。而只花费了 14 次对 string 的引用,其中 7 次是完成一个成功的匹配所必需的比较次数(patlen=7),另外 7 次让我们跳过了 22 个字符。

算法设计

最初的匹配算法

解释

现在看这样一个利用 delta1delta2 进行字符串匹配的算法:

ipatlastpos.jpatlastpos.loopif j<0return i+1if string[i]=pat[j]jj1ii1continueii+max(delta1(string[i]),delta2(j))if i>stringlastposreturn falsejpatlastpos

如果上面的算法 return false,表明 pat 不在 string 中;如果返回一个数字,表示 patstring 左起第一次出现的位置。

然后让我们更精细地描述下计算 delta2,所依靠的 rpr(j) 函数。

根据前文定义,rpr(j) 表示在 pat(j) 失配时,子串 subpat=pat[j+1patlastpos]pat[j] 最右边合理重现的位置。

也就是说需要找到一个最好的 k, 使得 pat[kk+patlastposj1]=pat[j+1patlastpos],另外要考虑两种特殊情况:

  1. k<0 时,相当于在 pat 前面补充了一段虚拟的前缀,实际上也符合 delta2 跳转的原理。
  2. k>0 时,如果 pat[k1]=pat[j],则这个 pat[kk+patlastposj1] 不能作为 subpat 的合理重现。 原因是 pat[j] 本身是失配字符,所以 pat 向下滑动 k 个字符后,在后缀匹配过程中仍然会在 pat[k1] 处失配。

还要注意两个限制条件:

  1. k<j。因为当 k=j 时,有 pat[k]=pat[j],在 pat[j] 上失配的字符也会在 pat[k] 上失配。
  2. 考虑到 delta2(patlastpos)=0,所以规定 rpr(patlastpos)=patlastpos

过程

由于理解 rpr(j) 是实现 BoyerMoore 算法的核心,所以我们使用如下两个例子进行详细说明:

j:  0 1 2 3 4 5 6 7 8pat:  A B C X X X A B Crpr(j):  5 4 3 2 1 0 2 1 8sgn:  - - - - - - - - +

对于 rpr(0)subpatBCXXXABC,在 pat[0] 之前的最右边合理重现只能是 [(BCXXX)ABC]XXXABC,也就是最右边合理重现位置为 -5,即 rpr(j)=5

对于 rpr(1)subpatCXXXABC,在 pat[1] 之前的最右边的合理重现是 [(CXXX)ABC]XXXABC,所以 rpr(j)=4

对于 rpr(2)subpatXXXABC,在 pat[2] 之前的最右边的合理重现是 [(XXX)ABC]XXXABC,所以 rpr(j)=3

对于 rpr(3)subpatXXABC,在 pat[3] 之前的最右边的合理重现是 [(XX)ABC]XXXABC,所以 rpr(j)=2

对于 rpr(4)subpatXABC,在 pat[4] 之前的最右边的合理重现是 [(X)ABC]XXXABC,所以 rpr(j)=1

对于 rpr(5)subpatABC,在 pat[5] 之前的最右边的合理重现是 [ABC]XXXABC,所以 rpr(j)=0

对于 rpr(6)subpatBC,又因为 string[0]=string[6],即 string[0] 等于失配字符 string[6],所以 string[02] 并不是符合条件的 subpat 的合理重现,所以在最右边的合理重现是 [(BC)]ABCXXXABC,所以 rpr(j)=2

对于 rpr(7)subpatC,同理又因为 string[7]=string[1],所以 string[12] 并不是符合条件的 subpat 的合理重现,在最右边的合理重现是 [(C)]ABCXXXABC,所以 rpr(j)=1

对于 rpr(8),根据 delta2 定义,rpr(patlastpos)=patlastpos,得到 rpr(8)=8

现在再看一下另一个例子:

j:  0 1 2 3 4 5 6 7 8pat:  A B Y X C D E Y Xrpr(j):  8 7 6 5 4 3 2 1 8sgn:  - - - - - - + - +

对于 rpr(0)subpatBYXCDEYX,在 pat[0] 之前的最右边合理重现只能是 [(BYXCDEYX)]ABYXCDEYX,也就是最右边合理重现位置为 -8,即 rpr(j)=8

对于 rpr(1)subpatYXCDEYX,在 pat[1] 之前的最右边合理重现只能是 [(YXCDEYX)]ABYXCDEYXrpr(j)=7

对于 rpr(2)subpatXCDEYX,在 pat[2] 之前的最右边合理重现只能是 [(XCDEYX)]ABYXCDEYXrpr(j)=6

对于 rpr(3)subpatCDEYX,在 pat[3] 之前的最右边合理重现只能是 [(CDEYX)]ABYXCDEYXrpr(j)=5

对于 rpr(4)subpatDEYX,在 pat[4] 之前的最右边合理重现只能是 [(DEYX)]ABYXCDEYXrpr(j)=4

对于 rpr(5)subpatEYX,在 pat[5] 之前的最右边合理重现只能是 [(EYX)]ABYXCDEYXrpr(j)=3

对于 rpr(6)subpatYX,因为 string[23]=string[78] 并且有 string[6]string[1],所以在 pat[6] 之前的最右边的合理重现是 AB[YX]CDEYXrpr(j)=2

对于 rpr(7)subpatX,虽然 string[3]=string[8] 但是因为 string[2]=string[7],所以在 pat[7] 之前的最右边的合理重现是 [X]ABYXCDEYXrpr(j)=1;

对于 rpr(8),根据 delta2 定义,rpr(patlastpos)=patlastpos,得到 rpr(8)=8

对匹配算法的一个改进

最后,实践过程中考虑到搜索过程中估计有 80% 的时间用在了 观察 1 的跳转上,也就是 string[i]pat[patlastpos] 不匹配,然后跳跃整个 patlen 进行下一次匹配的过程。

于是,可以为此进行特别的优化:

我们定义一个 delta0

int delta0(char char)if char=pat[patlastpos]return large  // large为一个整数,需要满足large>stringlastpos+patlenreturn delta1(char)

delta0 代替 delta1,得到改进后的匹配算法:

ipatlastposloopif i>stringlastposreturn falsewhile i<stringlenii+delta0(string(i))  // 除非string[i]和pat末尾字符匹配,否则至多向下滑动patlen  if i large//此时表示string上没有一个字符和pat末尾字符匹配 return falseiilargejpatlastpos.while j 0 and string[i]=pat[j]jj1ii1if j<0return i+1ii+max(delta1(string[i]),delta2(j))

其中 large 起到多重作用,一是类似后面介绍的 Horspool 算法进行快速的坏字符跳转,二是辅助检测字符串搜索是否完成。

经过改进,比起原算法,在做 观察 1 跳转时不必每次进行 delta2 的多余计算,使得在通常字符集下搜索字符串的性能有了明显的提升。

delta2 构建细节

引入

在 1977 年 10 月的Communications of the ACM上,Boyer、Moor 的论文[^bm]中只描述了 delta2 静态表,

构造 delta2 的具体实现的讨论出现在 1977 年 6 月 Knuth、Morris、Pratt 在SIAM Journal on Computing上正式联合发表的 KMP 算法的论文[^kmp]。

朴素算法

在介绍 Knuth 的 delta2 构建算法之前,根据定义,我们会有一个适用于小规模问题的朴素算法:

  1. 对于 [0, patlen) 区间的每一个位置 i,根据 subpat 的长度确定其重现位置的区间,也就是 [-subpatlen, i]
  2. 可能的重现位置按照从右到左进行逐字符比较,寻找符合 delta2 要求的最右边 subpat 的重现位置;
  3. 最后别忘了令 delta2(lastpos)=0
实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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 匹配
            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
}

特别地,对 Rust 语言特性进行必要地解释,下不赘述:

  • usizeisize 是和内存指针同字节数的无符号整数和有符号整数,在 32 位机上相当于 u32i32,64 位机上相当于 u64i64
  • 索引数组、向量、分片时使用 usize 类型的数字(因为在做内存上的随机访问并且下标不能为负值),所以如果需要处理负值要用 isize,而进行索引时又要用 usize,这就看到使用 as 关键字进行二者之间的显式转换。
  • impl PartialEq 只是用作泛型,可以同时支持 Unicode 编码的 char 和二进制的 u8

显然,该暴力算法的时间复杂度为 O(n3)

高效算法

下面我们要介绍的是时间复杂度为 O(n),但是需要额外 O(n) 空间复杂度的高效算法。

虽然 1977 年 Knuth 提出了这个构建方法,然而他的原始版本的构建算法存在一个缺陷,实际上对于某些 pat 产生不出符合定义的 delta2

Rytter 在 1980 年SIAM Journal on Computing上发表的文章[^rytter]对此提出了修正,以下是 delta2 的构建算法:

首先考虑到 delta2 的定义比较复杂,我们按照 subpat 的重现位置进行分类,每一类进行单独处理,这是高效实现的关键思路。

按照重现位置由远到近,也就是偏移量由大到小,分成如下几类:

  1. 整个 subpat 重现位置完全在 pat 左边的,比如 [(EYX)]ABYXCDEYX,此时 delta2(j)=patlastpos×2j

  2. subpat 的重现有一部分在 pat 左边,有一部分是 pat 头部,比如 [(XX)ABC]XXXABC,此时 patlastpos<delta2(j)<patlastpos×2j; 我们把 subpat 完全在 pat 头部的的边际情况也归类在这里(当然根据实现也可以归类在下边),比如 [ABC]XXXABC,此时 patlastpos=delta2(j)

  3. subpat 的重现完全在 pat 中,比如 AB[YX]CDEYX,此时 delta2(j)<patlastpos

现在来讨论如何高效地计算这三种情况:

第一种情况

这是最简单的情况,只需一次遍历并且可以顺便将 delta2 初始化。

第二种情况

我们观察什么时候会出现 subpat 的重现一部分在 pat 左边,一部分是 pat 的头部的情况呢?应该是 subpat 的某个后缀和 pat 的某个前缀相等,

比如之前的例子:

j:  0 1 2 3 4 5 6 7 8pat:  A B C X X X A B C

delta2(3) 的重现 [(XX)ABC]XXXABCsubpat XXABC 的后缀与 pat 前缀中,有相等的,是 ABC

实际上对第二种和第三种情况的计算的关键都需要前缀函数的计算和和应用

那么只要 j 取值使得 subpat 包含这个相等的后缀,那么就可以得到第二种情况的 subpat 的重现,对于例子,我们只需要使得 j5

而当 j=5 时,就是 subpat 完全在 pat 头部的边际情况。

可以计算此时的 delta2(j)

设此时这对相等的前后缀长度为 prefixlen,可知 subpatlen=patlastposj,那么在 pat 左边的部分长度是 subpatlenprefixlen

rpr(j)=(subpatlenprefixlen),所以得到 delta2(j)=patlastposrpr(j)=patlastpos×2jprefixlen

其后面可能会有多对相等的前缀和后缀,比如:

j:  0 1 2 3 4 5 6 7 8 9pat:  A B A A B A A B A A

j2 处有 ABAABAA2<j5 处有 ABAA,在 $5