标签归档:KMP

KMP 算法:实现高效的子字符串搜索

在计算机日常应用中,我们经常会遇到需要在一篇文章中搜索某个字词的情形,这就是子字符串查找算法运用的实例。例如在字符串 “http://luodichen.com/blog/” 中找出子字符串 “luodichen.com” 第一次出现的位置(索引),通过观察可以很轻松地得到答案是 7。在子字符串查找中,期望查找的子字符串是以“字符串某一部分与期望查找的子字符串完全相同”的规则存在的,这个以子字符串表示的匹配规则称为“模式(Pattern)”。上面查找 “luodichen.com”的例子中,模式就是 “luodichen.com”。

如何编程实现子字符串查找呢?假设有长度为 l 字符串 S,需要在 S 中寻找长度为 m 的子字符串 R 第一次出现的位置(m < l)。粗看起来,这个问题似乎并不难回答。一个直观的做法就是依次设查找索引 i = 0, 1, 2, …, l – m,每次都检查 S 在索引 i 处长度为 m 的子字符串是否与 R 完全相等,如果相等,则说明查找成功,i 就是要找的答案;否则就尝试下一个 i 的值,如果尝试了每一个 i 的值都没有找到答案,说明查找失败,S 中不存在要找的子字符串。这是一种简单粗暴的方法,下文称其为“暴力算法”。

考察“检查在索引 i 处长度为 m 的子字符串是否与 R 完全相等”的实现过程,我们会逐一比较字符 S[i + j] 与 R[j](0 <= j < m)是否相等,会发现这个操作实质上可以看作一个确定有限状态自动机。这个状态机在每比较一个字符时发生一次状态转移:如果比较的两个字符相等,则进入下一个状态,否则匹配失败停机,直到比较完所有的字符,转入成功停机状态。状态机停机之后,只要判断当前的状态是成功还是失败就能得出此次匹配的结果。假设要查找的字符串是 “LUODC”,状态机的图示如下。

图1 在字符串中查找 “LUODC” 时的状态机表示

对于每个 i 的取值,这个操作最少需要 1 次字符比较,最多需要做 m 次字符比较。因此,这种字符串搜索算法在最差的情况下的时间复杂度是 O(ml – m2)。当然,在实际应用中碰到较差的情况是比较罕见的,因为在通常情况下,大部分匹配尝试都会在前几个字符的比较中就会转到失败状态,暴力算法在一般的情形下性能还是可以接受的。

然而,1970 年,S.Cook 在理论上证明一个关于某种特定类型的抽象计算机的结论,该结论暗示了一种在最坏情况下用时也只是与 m + l 成正比的解决子字符串查找问题的算法[1]。D.E.Knuth 与 V.R.Pratt 在这些基础上做了一些改进,提出了一个相对简单而实用的算法。另外,J.H.Morris 也独立发明了相似的子字符串查找算法。后来,这个算法取发明者三人名字的首字母,得名 KMP 算法

考虑以下问题:在字符串 S[] = “AAAAAAAAAB” 中搜索模式 R[] = “AAAAB”。按上文中提到的暴力算法,先测试 S[0…4] 与 R[] 是否相等,直到比较到字符 S[4] 与 R[4] 时,才发现 S[4] 的值是 ‘A’ 而 R[4] 的值是 ‘B’,此时子串 s[0…4] 测试失败,下一步应当测试 S[1…5] 与 R[] 是否相等。在下一轮测试中,又需要依次比较 S[i + 1] 与 R[i](1 <= i <= 5)的值是否相等,并最终以 S[5] 与 R[4] 不相等而匹配失败收场。

等等——我们注意到,在第一轮测试中,其实已经可以知道 S[1…4] 的值是 “AAAA”,与 R[0…3] 的四个字符是完全吻合的,实际上只需要比较 S[5] 与 R[4] 两个字符是否相等就行了,接下来的几轮比较也是如此。这样,通过这个小的改进,省下了多次不必要的字符比较,节省了操作时间。

以上是一个特殊的例子,KMP 算法将这种思路推广到了一般情形,对于任意模式的查找操作都能最大限度地省去不必要的字符比较。

在暴力算法的状态机描述中,假设某一轮测试将 a[i], a[i+1] ,…, a[i+m-1] 依次输入状态机中后,发生了失败停机,则下一轮需要将 a[i+1], a[i+2], …, a[i+m] 输入状态机中重新测试。在最坏的情形下,每轮测试都不得不输入 m – 1 个与上次重复的字符。KMP 算法最大的优势在于,如果把它也用状态机来描述,KMP 状态机是没有失败状态的,它可以连续地接收被查找字符串中的所有字符,直到找到一个匹配的子字符串才停机。在这个过程中,被查找的字符串中竟没有任何重复扫描的字符!下面是一个用 KMP 算法在只由 ‘A’、’B’ 和 ‘C’ 构成的字符串中查找子字符串 “ABABAC” 的状态机的例子。

kmp-fsm-2图2 用 KMP 算法在字符串中查找子字符串 “ABABAC” 时的状态机

KMP 算法按顺序连续(而不回头)地读取被查找字符串中的字符,每读取一个字符都会改变一次状态机的状态,自发地根据当前的状态“决策”最适合的下一个状态以达到找出子字符串的目的。如上图所示,KMP 算法为每一个匹配进度都设置了一个状态,假定要查找的模式 R[] 的长度是 m,那么状态机 DFA 就有 S0, S1, …, Sm-1 一共 m 个状态,其中每个状态都根据不同的输入对应一个转移路径。例如上图中的例子,假设当前的状态为匹配进度 “ABABA_”,那么如果下一个输入正好是 ‘C’,毫无疑问此时子字符串匹配成功,转移到 succeed 状态;如果下一个输入是 ‘B’,意味着当前匹配到了一个 “ABABAB” 的字符串,最佳的决策是丢掉前面两个字符 “AB”,再期望输入一个 ‘A’ 和一个 ‘C’ 即可达到子字符串匹配的目的,因此转移到匹配进度为 “ABAB_” 的状态;如果下一个输入是 ‘A’,意味着当前匹配到了一个 “ABABAA”,的字符串,显然地,这时只能丢掉前五个字符 “ABABA”,只留下字符 “A”,并期望输入 “BABAC” 来达到匹配的目的,因此转移到匹配进度为 “A_” 的状态。

可见,KMP 算法高效的原因是有一个“聪明的”状态机总能根据当前的匹配进度为每种可能的输入选择最佳的匹配方案。那么,现在的问题是如何构建一个任意的模式 R[] 对应的状态机。假设 R 的长度为 m,那么 R 所有可能的匹配进度有匹配前 0 个字符、匹配前 1 个字符、匹配前 2 个字符……匹配前 m 个字符,每个匹配进度对应状态机一个状态,记作 S0, S1, S2, …, Sm。另设构成被查找字符串的字符集为 E,则构成确定有限自动机 DFA 的 5-元组要素如下:

  • 状态集合 Q = {S0, S1, S2, …, Sm}
  • 输入字母表 ∑ = E
  • 开始状态 s = S0
  • 接受状态集合 F = {Sm}

接下来要做的是构造自动机的转移函数。设当前状态为 S,输入的字符为 c 时的状态转移函数为 f(S, c),另设模式 R[0…m-1] 的字符分别为 c0, c1, …, cm-1,显然地,当状态机处于 Si 状态时,说明已经完成了 c0-ci-1 共 i 个字符的匹配,此时如果输入的字符正好与 ci 相等,那么状态机一定会再次完成一次匹配,进入 Si+1 状态。于是可以得出下式:

f(Si, ci) = Si+1    ①
特别地:f(S0, c0) = S1    ②

再考虑状态机处于 S0 状态时,显然只有当输入的字符与 c0 相等时才会进入下一个状态 S1,其他输入都是不匹配的,只会让状态机回到原地。因此对 S0 的其他非 c0 输入又可以得到下式:

f(S0, c) = S0 (c ≠ c0)    ③

那么,在非 S0 状态时的不匹配输入,应当怎样处理呢?显然,状态机不匹配时应当回到当前状态之前某个状态,这正是 KMP 算法的精妙之处。再回过头来看图 2 中的例子,假设当前状态是已匹配 “ABABA_”,已经匹配了 5 个字符,也就是当前的状态是 S5。当输入 c ≠ ‘C’ 时,状态机需要回退到之前某个状态,目前已知的是如果向状态机中依次输入 (‘A’, ‘B’, ‘A’, ‘B’, ‘A’, c) 一定是不匹配的,在输入 c 后能获得最佳匹配结果的状态是将 (‘B’, ‘A’, ‘B’, ‘A’, c) 依次输入重新初始化过的状态机,最终得到的状态,这个状态即是要求的 S5 转换函数 f(S5, c)。因为 5 个输入最多能使状态机转换到 S5,所以使用上述方法推导 S5 的转换函数时,只需要已知 S0-S4 各个状态的转换函数即可!换言之,如果要推导 Sn (n > 0) 的转换函数,最多只需已知 S0, S1, …, Sn-1 即可,有了这个递推关系之后,竟可以只已知 S0 的全部转换函数而推导出其他所有状态的非匹配转换函数!总结以上的方法,当需要求 Sn (n > 0) 的转换函数时,只需将当前已经匹配过的字符,跳过第一个后(即 c1, c2, …, cn)依次输入到已初始化的状态机中,状态机给出的状态即 Sn

设函数 g(Si, cm, cn) = f(f(f(…f(Si, cm), cm+1), cm+2), …, cn) (n > m),则有
f(Si, c) = f(g(S0, c0, ci-1), c) (i > 0, c ≠ ci)   ④

至此就可以从 S1 开始,依次根据已知的状态函数推导出状态机所有状态对全部输入的转换函数了。下面是一个由模式 mPattern 生成 KMP 算法状态机转换函数表的 Java 实现。

KMP 算法的 Java 完整实现包括测试用例已经托管于我的 GitHub,查看

参考文献
[1] Sedgewick R, Wayne K. Algorithms[M]. 人民邮电出版社, 2012.

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=272 )