在一个字符串中查找另外一个字符串是文本编辑和DNA序列分析中常见的问题。假设我们有一个由字符表$S$中的字符构成的字符串$T$。$S$可能只是集合${0, 1}$,这样的情况下可能的字符串都是二进制串(比如”1001010011″);$S$也可能是${A,C,T,G}$,这样的情况下字符串是DNA序列(比如”GATTACA”)。字符串匹配问题就是:给定一个小一些的字符串$P$(模式串),查找是否存在于$T$中;如果$P$在$T$中存在且位移为$i$,则$P[j] = T[i+j]$对于$P$中所有的索引$j$都成立。

例如在字符串”ABABABAC”中,模式串”BAB”出现在位移1和3处。

这里考虑的是这个问题的简化版本,我们只是找$P$在$T$中第一次出现的位置,但是很容易对这个问题的算法进行一些调整以解决一些更一般的问题。

(* 返回P在T中出现的最小的位移, 在T中找不到P时返回T的长度 *)
int stringMatch(string T, string P)

当然我们可以推广这个问题,我们要匹配的字符串可以是任何类型的数组,假设对数组元素能做的操作只有判断他们是否相等。这里有个朴素的字符串匹配算法,每次向前移动一个元素的位置,然后尝试比较对应的字符。

for (int i = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
    if (P[j] != T[i + j]) break;
  }
  if (j == m) return i;
}

显然最坏的情况下是$O(nm)$的算法,如果模式串比较短还好说,但是长一点的话就很慢了。

注意:我们这里的$P[i…j]$都是指$P$串下标在$i$与$j$之间(包括$i$和$j$)的子串。

  • $P$的一个前缀是子串$P[0…k]$,其中$k < m$;
  • $P$的一个合适的前缀是子串$P[0…k]$,其中$k < m – 1$。
  • $P$的一个后缀是子串$P[k…m – 1]$,其中$k \geq 0$;
  • $P$的一个合适的后缀是子串$P[k…m – 1]$,其中$k > 0$。

Boyer-Moore 算法

Boyer-Moore算法的思想是从模式串$P$的末尾而不是从开头开始匹配。当失配发生时,它允许位移的增加大于一,考虑下面两个字符串:

T = UNTITLED STATES
P = EDITED

从末尾开始匹配,我们首先遇到了发现了一个在”L”处的失配,因为”L”不在$P$中,所以我们可以直接将位移增加4,而不用担心可能错过一些潜在的匹配。一般来说,不匹配的字符是可能在$P$中的,这种情况下位移只能增加到P中出现的字符的位置。这里是一个简化版本的Boyer-Moore算法,使用了坏字符规则

s = 0; (* 当前的位移 *)
while (s <= n - m) {
  j = m - 1;
  while (P[j] = T[s + j] && j >= 0) j--;
  if (j < 0) return s;
  s += max(1, j - last[T[s + j]] + 1);
}

$last$数组必须先预处理出来,$last[c]$是字符$c$在$P$中最后出现的位置,如果没有出现则为0。时间复杂度为$O(m+|S|)$,其中$|S|$是组成字符串的字母表$S$的大小:

memset(last, 0, sizeof(last));
for (int j = 0; j < m; j++) {
  last[P[j]] = j;
}

这个算法在字母表较大,但不是特别大的时候效果较好。若最后一个字符总是失配,循环中当前的位移$s$每次增加$m$。总共字符比较的次数大约是$n / m$,比在类似问题上需要大概$n$次比较的朴素算法要好。事实上,模式串越长搜索越快!但是最坏的运行时间还是$O(nm)$。在字母表较小的情况下这个算法运行的不是很好,因为就算字符串是随机生成的,任何一个给定字符最后一次出现的位置都接近字符串的末尾,我们可以使用另外一个规则来增加位移。考虑下面的例子:

T = ...LIVID_MEMOIRS...
P =   EDITED_MEMOIRS

当发现了I和E的失配,坏字符规则不会有什么帮助,因为I在$P$中最后一次出现的位置早已经超过了比较的位置,上面的算法只会把位移增加1。但是,已知后缀(“D_MEMOIRS”)早已经匹配过了,这告诉我们$P$可以向前移动全部$m$个字符,因为在$P$中不存在当前点之前的”D_MEMOIRS”的后缀。

当失配发生时,已知后缀$S = P[j + 1…m – 1]$已经匹配,我们可以根据此后缀的一些后缀在$P$中出现的位置来计算向前移动的距离。这称为好后缀规则:我们可以保守地向前移动最小的位移,使得$S$的后缀和$P$的前缀“后缀匹配”。实际上最小的位移对应于与$P$后缀匹配的最长合适前缀$S\prime$,当两个串中更短的串是另一个串的后缀时我们称这两个串“后缀匹配”。如果$S\prime$是两个字符串中较长的一个,则意味着可能存在一个$P$,起点处于当前$P$的位移起点和失配点之间。 如果字符串$S$是两个字符串中较长的一个,则可能存在一个$P$,起点处于当前$P$的失配点与位移终点之间。 以下是这两种情况的例子:

(case 1) T = ....CABABDABAB... S = ABAB, S' = BAB, 最大安全位移 = 8 - 3 = 5
         P =  BABDABAB

(case 2) T = ...CCABABAB...    S = ABAB, S' = CCABAB, 最大安全位移 = 8 - 6 = 2
         P =  CCABABAB

对于每个可能的$j$,令$k_j$是与$P [j + 1…m-1]$后缀匹配的最长合适前缀的长度。 对于每个$j$,我们将$good-suffix[j]$定义为$m – k_j$; 即该算法可以安全地向前移动$m-k_j$个字符。 这里是完整的Boyer-Moore算法:

s = 0; (* 当前的位移 *)
while (s <= n - m) {
  j = m - 1;
  while (P[j] = T[s + j] && j >= 0) j--;
  if (j < 0) return s;
  s += max(good_suffix[j], j - last[T[s + j]] + 1);
}

在上面的”MEMOIRS”例子中,$k_j = 0$,所以完全移动$m$个字符也是安全的。对于好后缀规则,考虑一个不太平凡的例子:

T = ...BABABABA...
P =    BABACABA

字符串$S =$“ABA”,最长的后缀匹配前缀是“BABA”,因此可能的移动是$8 – 4 = 4$个字符,注意这里坏字符规则会产生$-2$的无用位移。如果字母表比较小,字母后缀的细化特别有用。注意$good\_suffix[j]$总是正数,因为一定有$k < m$(如果它们相等,模式串将被找到!)。这就是我们不再需要在计算$s$的移动时与1取最大值的原因。

我们可以在$O(m)$的时间内计算数组$good\_suffix$,下面会讨论如何计算。所以即使有了这种改进,Boyer-Moore算法的总时间仍然是$O(m + |S|)$。在最坏的情况下,总运行时间仍然不会更好。

Knuth-Morris-Pratt 算法

对于大多数字符串匹配的问题Boyer-Moore算法都是一个好的选择,但是它并不保证比朴素的算法强。若需要保证,Knuth-Morris-Pratt算法(KMP)是一个更好的替代品。算法是下面这种形式:

j = 0;
for (int i = 0; i < n; i++) {
  while (j > 0 and P[j] != T[i]) {
    j = prefix[j];
  }
  if (P[j] == T[i]) j++;
  if (j == m) return i - m + 1;
}

思想就是从左向右遍历字符串$T$,检查每个字符$T[i]$,变量$j$记录了$P$中哪个字符正在与$T[i]$比较。当失配发生时,当前已经匹配的字符$S=T[i-j…i-1] = P[0…j-1]$可能是匹配的一部分。这样的话$P[0…j-1]$中一些合适后缀本身一定是$P$的一个前缀。设$prefix[j]$是$S$的后缀与$P$的前缀相等的最大的串的长度,因此我们在保证$S$的后缀与$P$的前缀相等的前提下移动最小的长度,即把$j$设置为$prefix[j]$。我们可以检查$P[j]=T[i]$,来判断是否达到包含失配字符$T[i]$的部分匹配。如果不匹配,我们就尝试下一个与$S$的后缀相等的$P$的更小的前缀,直到遇见了一个匹配,或者因为没有$S$的合适后缀,此时$j = 0$。注意每次外循环将位移增加$i-j$或者不变,因为每次循环中$j$最多增加1,但$i$总是增加,且$prefix[j] < j$。

为了看这个算法是如何工作的,考虑字符串$P = $“ababaca”。这个字符串的前缀数组是:

prefix[1] = 0
prefix[2] = 0    ("ab"唯一的合适后缀是"b", 但不是一个前缀)
prefix[3] = 1    ("a"是"aba"的一个合适后缀并且是一个前缀)
prefix[4] = 2
prefix[5] = 3
prefix[6] = 0    ("ababac"的合适后缀中没有一个是它的前缀)
prefix[7] = 1

现在考虑搜索这个字符串,现在对于$T$的扫描已经进行到箭头处的位置:

T = ...ababababa...
P =    ababaca
            ^
            i

这里在$j=5$处有一个失配,故将其向前移动两个字符到$j=prefix[5]=3$,然后检查字符’b’是否与$P[3]$匹配,发现是匹配的。因此算法继续匹配$T$的下一个字符。还有下面能跳的更远的一种情况:

T = ...ababaxaba...
P =    ababaca
            ^
            i

同样是在$j=5$处有一个失配,将其向前移动到$j=prefix[5]=3$,发现此时’x’与$P[3]$失配,于是继续向前移动到$j=prefix[3]=1$,发现还是失配的,继续移动到$j=prefix[1]=0$,此时内循环结束。$P$所有可能匹配的前缀从长到短都试了一遍,因为其中没有”x”,所以内层循环有效的将$P$向前推进了6个字符。

上面的代码是$O(n)$的,虽然不是很显然。显然除去内层的while循环之后是$O(n)$的,问题就变成了while循环可以执行多少次。每次while循环执行,$j$必定减少,但是$j$永远非负,也就是$j$减少的次数最多和$j++$的次数一样多,所以最多是$n$次。故内层循环最多执行$n$次,总的时间复杂度为$O(n)$。

这个算法剩下的部分是计算$prefix[j]$。回忆下$prefix[j]$是$P[0…j-1]$的后缀与$P$的前缀相等的最大的串的长度,则此数组可以用与KMP类似的方法在$O(m)$的时间内计算出来。这是说得通的,因为我们是在$P$的内部搜索$P$的前缀。关键在与已知$prefix[0], …, prefix[j]$,我们便可以高效的计算出$prefix[j + 1]$:

prefix[1] = 0;
int j = 0;
for (int i = 1; i < m; i++) {
  while (j > 0 && P[j] != P[i]) {
    j = prefix[j];
  }
  if (P[j] == P[i]) j++;
  prefix[i + 1] = j;
}

显然上面的算法也是$O(m)$的,可以用我们之前用的方法得到,但这个算法为什么有效呢?看起来确实像是在运行KMP来在$P$中搜索$P$本身,除了在运行这段代码之前$prefix$没有进行初始化,并且我们从$i=1$处开始,以避免位移为0时的平凡匹配。$prefix$未初始化的状态不影响计算,因为显然计算$prefix[i+1]$时没有用到$prefix[k]$,其中$k > i$。现在对于正在被搜索的字符串的每个索引$i$,KMP算法找到了模式串与后缀$P[i-j…i]$匹配的最长的前缀$P[0…j-1]$,这就是$prefix[i+1]$的定义。

计算 good_suffix

现在让我们回到Boyer-Moore算法,我们可以使用相同的前缀计算方法在$O(m)$的时间内有效地计算出$good\_suffix$数组。 回想下$good\_suffix[j]$是$m-k_j$,其中$k_j$是与$P[j + 1…m-1]$后缀匹配的最长合适前缀的长度。 这里是计算$good\_suffix$的算法,调用了前面$compute\_prefix$的代码:

prefix = compute_prefix(P);
for (int j = 0; j < m; j++) {
  good_suffix[j] = m - prefix[m];
}
P' = reverse(P);
prefix' = compute_prefix(P');
for (int j' = 1; j <= m; j++) {
  j = m - prefix'[j'] - 1;
  good_suffix[j] = min(good_suffix, j' - prefix'[j']);
}

注意$prefix[m]$是匹配到$P$的结尾的最长的合适前缀的长度。$prefix[m]$的值是$P$的最大合适前缀的长度,可以与任何后缀$P$进行后缀匹配,而与$j$无关。因此,$m – prefix [m]$是与可能的后缀匹配相对应的最小的相对偏移位置,而不管$j$的值如何。$m – prefix[m]$的值因而设置了$good\_suffix [j]$的值的上限 – 算法绝对不能安全地超出该值。它也尽可能早地捕获了第一种情况的后缀匹配。但是可能不是最早可能的后缀匹配,因为可能存在具有较小偏移值的情况2的实例。

第二个循环修复了$good\_suffix$,使其不会超出可能出现的小于$m-prefix[m]$的第2种情况。诀窍是将$compute\_prefix$应用于$P$的反向以找到最长的后缀。$prefix’[j’]]$是匹配$P[m-j’… m-1]$的合适前缀的$P$的最长后缀的长度。

注意到$j’ – prefix’[j’] > 0$且$m-prefix[m] > 0$,所以$good\_suffix [j] > 0$,保证了Boyer-Moore算法的进步。

一个小例子可能有助于说明,考虑字符串$P =$“ADEADHEAD”,下表显示了相关的计算值:

  A D E A D H E A D      (m=9)
  0 1 2 3 4 5 6 7 8 9    j
    0 0 0 1 2 0 0 1 2    prefix[j]  (m-prefix[m] = 7)

  9 8 7 6 5 4 3 2 1      j'
  2 1 3 2 1 0 0 0 0      prefix'[j']
  6 7 5 6 7 8 8 8 8      j=m-prefix[j']-1
  7 7 4 4 4 4 3 2 1      j'-prefix'[j']

因此,运行该算法将把$good\_suffix[5] \cdots good\_suffix[7]$设置为4,将$good\_suffix[8]$设置为1,这是我们期望的,因为重复的“EAD”允许第二种情况的后缀匹配转移4。

阅读

  • Cormen T H, Leiserson C E, Rivest R L. 算法导论[J]. 第 2 版 机械工业出版社, 2006.
  • 一个很棒的关于Boyer-Moore算法(以及许多其他的字符串匹配算法)的可视化与讨论:Exact String Matching Algorithms