使用确定有限状态自动机解KMP算法

发表于 | 分类于 | 阅读次数:
字数统计: 2,372 | 阅读时长 ≈ 9

这里介绍的方法来自于《算法(第4版)》一书，通过构造一个确定有限状态自动机来解决KMP算法。

预热

KMP算法解决这样一个问题：已知一个文本字符串和一个模式字符串，在前者中查找并返回后者第一次出现的位置。先看用暴力方法如何求解，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int search(String pat, String txt) {
    int j, M = pat.length();
    int i, N = txt.length();
    for (i = 0, j = 0; i < N && j < M; i++) {
        if (txt.charAt(i) == pat.charAt(j))
            j++;
        else {
            i -= j;
            j = 0;
        }
    }
    if (j == M)
        return i - M;
    else
        return N;
}

在暴力算法中，每次字符串上对应的单个字符匹配失败，i会回退到i-j+1的位置与j=0再次尝试新的匹配，在for循环执行完后，如果j等于模式字符串的长度M，则表示匹配成功，返回第一次出现的位置i-M，否则表示匹配失败，返回文本字符串的长度N来表示。

KMP算法

“KMP算法的主要思想是提前判断如何重新开始查找，而这种判断只取决于模式字符串本身。” ——摘自《算法》中文版496页

如果说这本书中介绍的关于实现KMP算法的方法和其它文章中构建next数组的方法有什么不同的话，我认为是前者不仅不回退，而且一直在”前行”，而后者的i不回退但是会“停留”。 不过这篇文章只单独针对《算法》书中的方法进行分析。

示例说明

为了方便理解，现假设有一个文本字符串txt（此字符串转化成的字符数组为t）：ACBACBACAB和一个模式字符串pat（此字符串转化成的字符数组为p）：ACBACAB，当i=0，j=0时文本第一个字符和模式第一个字符相等，各自+1进行下一次比较…一直到当i＝5、j＝5时，对应的字符分别是文本的第六个字符B和模式的第六个字符A，此时B不等于A所以不匹配(下图中浅红色部分)：

图1

要使i继续“前行”变更为i+1（也就是i＝6，指向第七个字符）的同时，还能保证算法的正确，那么找到与i＋1进行匹配的j的值就是本算法的关键。假设此时j＝k，k就是这样一个数：

  • 满足p[0]，p[1]，…，p[k-1]组成的字符串与t[i-k+1]，t[i-k+2]，…，t[i]所组成的字符串相等；
  • 为了减少后续比较次数以保证算法花费的时间尽可能少，在满足(1)的条件下k要尽可能大；

不难发现，p[0]，p[1]，…，p[j-1]所组成的字符串和t[i-j]，t[i-j+1]，…，t[i-1]所组成的字符串是相等的，即模式字符串的ACBAC和文本字符串的ACBAC相等(下图中紫色部分)：

图2

那么求k不就是求p[0]，p[1]，…，p[j-1]加上t[i]所组成字符串的前缀字符串和后缀字符串的最长共有元素的长度吗？

要说明的是，一个字符串的前缀字符串指的是除了最后一个字符外，该字符串的全部头部组合；一个字符串的后缀字符串指的是除了第一个字符外，该字符串的全部尾部组合。例如ACBACB的前缀字符串包括：A、AC、ACB、ACBA、ACBAC，后缀字符串包括：B、CB、ACB、BACB、CBACB。

p[0]，p[1]，…，p[j-1](即紫色部分ACBAC)和t[i](即字符B)组成的字符串为下图中蓝色部分表示：

图3

上图中蓝色部分ACBACB的前缀字符串和后缀字符串最长共有元素为ACB(下图中绿色部分分别为前缀字符串和后缀字符串ACB)，长度为3：

图4

这个3也就是k的值，那么接下来t[i+1]就只需要从p[k](k等于3)开始进行比较(虚线部分)，而p[2]与t[i]、p[1]与t[i-1]、p[0]与t[i-2]就不用再去一一比较了(下图中绿色的部分)，因为他们肯定是相等的：

图5

如此一来，i就做到了不用回退还能一直“前行”，达到了优化之前暴力算法的目的。

DFA

由前文的分析可得，i一直前进，且每进一位，只需要知道位于文本字符串上该位置的字符与模式字符串上的哪个位置的字符进行匹配。

不妨把j停留在的位置理解成一种状态，模式字符串一共有0，1，2，3，…，M-1这M个状态，那么用KMP算法成功查找到模式字符串第一次出现的位置的过程，其实也是一种j从0不断跳转，直到跳转到M-1状态并满足t[i] == p[j]的过程。

接下来需要构造一个int类型的二维数组dfa，用来模拟一个确定有限状态自动机：

  • 第一维：对应需要比较的文本字符串的字符(在实际的Java代码中传入的字符类型自动向上转化为int类型)；
  • 第二维：表示要比较的模式字符串所处的状态；
  • dfa元素的值：表示比较后应该跳转到的状态；

dfa一旦构造成功，就可以通过它找到文本字符串每个位置应该和模式字符串的什么位置比较，从而对之前的暴力解法for循环内的部分进行优化，这，就是《算法》一书介绍的KMP算法思想，暴力算法改进如下：

1
2
3
4
5
6
7
8
9
10
public static int search(String pat, String txt) {
    int j, M = pat.length();
    int i, N = txt.length();
    for (i = 0, j = 0; i < N && j < M; i++)
      j = dfa[txt.charAt(i)][j];
    if (j == M)
        return i - M;
    else
        return N;
}

字符匹配

那么dfa如何构造？

考虑到跳转分两种情形，一种是当前i和j指向的字符匹配不成功，一种则是匹配成功，所以分别对这两种情形进行分析。

匹配不成功

在匹配之前，由于p[0]，p[1]，…，p[j-1]组成的字符串和t[i-j]，t[i-j+1]，…，t[i-1]组成的字符串相等，设此时这个相等字符串的前缀字符串和后缀字符串的最长共有元素的长度为k，当匹配不成功时，t[i]不等于p[j]，dfa[t[i]][j]的值表示i+1后，t[i+1]从什么地方开始匹配，它应该等于dfa[t[i]][k]。

为什么dfa[t[i]][j]应该等于dfa[t[i]][k]？

这个问题可以转化为：已知一个字符串S，它的前缀字符串和后缀字符串的最长共有元素的长度为k，现将一个字符拼接在S的尾部组成新的字符串S’，求S’的前缀字符串和后缀字符串的最长共有元素的长度k’。

首先能够确定的是，k’的大小不会超过k+1，也就是说k’只可能<= k+1。分两种情况讨论：

  • 当拼接的字符等于S[k]时，k’的大小为k+1；
  • 当拼接的字符不等于S[k]时，k’等于S[0]、S[1]、S[2]、…、S[k-1]与该字符组成的字符串的前缀字符串和后缀字符串的最长共有元素的长度；

实际上这正是dfa[t[i]][k]的含义，当跳过这一小段文字，读至本文末尾就会发现，以上便是字符匹配的成功和不成功的两种情形，也就是说，本方法不停通过迭代进行构造。

所以匹配不成功的代码如下：

1
2
3
for (int c = 0; c < R; c++) {
  dfa[c][j] = dfa[c][k];
}

c是扩展ASCII中的字符，范围在0 ～ 255。

匹配成功

如果t[i]等于p[j]，说明匹配成功，j应该跳转到j+1，表示t[i+1]将与p[j+1]进行比较。所以dfa需要满足dfa[p[j]][j] = j+1的条件，代码如下：

1
dfa[p[j]][j] = j + 1;

更新k

无论匹配成功与否，每经过一轮匹配，k值都应该更新：

1
k = dfa[p[j]][k];

完整代码

设定初始值后，通过以上两种情形的处理，k可以不断迭代更新，最终构建出dfa，代码编写如下：

1
2
3
4
5
6
7
8
dfa[pat.charAt(0)][0] = 1;
for (int k = 0, j = 1; j < pat.length(); j++) {
  for (int c = 0; c < 256; c++) {
    dfa[c][j] = dfa[c][k];
  dfa[pat.charAt(j)][j] = j + 1;
  k = dfa[pat.charAt(j)][k];  
  }
}

关于初始值的说明：pat.charAt(0)是模式字符串的第一个字符，它与模式字符串所处的第0号状态的字符当然相等，所以dfa[pat.charAt(0)][0]的结果是跳转到状态1。

实际编写代码的时候需要注意：每次循环中匹配成功的代码不能在匹配失败的代码之前，不然会被覆盖。

小结

本篇主要分析了《算法(第4版)》一书介绍的方法。再回味一下书中给出的那句话：“KMP算法的主要思想是提前判断如何重新开始查找，而这种判断只取决于模式字符串本身。”这句话揭示KMP算法的本质。

参考

《算法(第4版)》