字符串匹配之 KMP 算法

某天在群里看到 井大侠 提起传说中的“看毛片”算法,在网上搜到一篇好文章(见参考资料 [1]),发现从有限状态自动机的角度来理解可能会更容易一些。

简单的逐个字符比较

最简单的匹配算法是将两个字符串第一个字符对齐,然后开始逐字符比较。当在某个位置发现不匹配时,把模式串向右移动一个字符,再从模式串的第一个字符开始与主串对应位置的字符开始比较。例如要从字符串 T 中查找模式串 P,比较过程如下:

                        1                   2
pos 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
T   A B C Z A B C D A E Z A B C D A B C D A B D E
P   A B C D A B D
          *

在 pos[3] 发现不匹配,把 P 向右移动一个字符,从 P 的第一个字符开始比较:

                        1                   2
pos 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
T   A B C Z A B C D A E Z A B C D A B C D A B D E
P     A B C D A B D
      *

在 pos[1] 不匹配,再向右移动……直到 p[0] 移动到 pos[15],发现所有字符都匹配:

                        1                   2
pos 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
T   A B C Z A B C D A E Z A B C D A B C D A B D E
P                                 A B C D A B D
                                              *

这种情况可以看成是由模式串构成的一个有限状态自动机,主串作为输入流,每次发现不匹配时都回到初始状态:

  +--------------------------+
  |                          |
  +-----------------+        |
  |                 |        |
  +--------+        |        |
  |        |        |        |
  v        |        |        |
+---+ A  +---+ B  +---+ C  +---+ D  +---+ A  +---+ B  +---+ D  +===+
| 0 | -> | 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 | -> | 6 | -> | 7 |
+---+    +---+    +---+    +---+    +---+    +---+    +---+    +===+
  ^                                   |        |        |
  |                                   |        |        |
  +-----------------------------------+        |        |
  |                                            |        |
  +--------------------------------------------+        |
  |                                                     |
  +-----------------------------------------------------+

除非在前两个字符就发现不匹配,否则输入需要回溯(比较的位置往前移)。

记 T 的长度为 n,P 的长度为 m,0 < m <= n。

最好的情况是 p[0] 与 t[0], t[1], …, t[n-m-1] 均不相同,这样只需比较 n-m 次;最坏情况是 P[0, 1, …, m-2] 与 T[i, i+1, …, i+m-2] 匹配,而 p[m-1] 与 t[i+m-1] 不相同(0 <= i < n-m-1),比较次数为 m(n-m) 次。

KMP 算法

KMP 算法是由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 共同发现的,因此以三人的首字母命名该算法。从状态转移的角度看,KMP 算法通过对模式串的预处理,使得每次在不匹配的时候不必回到初始状态,而是可以退回到初始状态和当前状态之间的某个状态再开始比较,并且输入不需要回溯。

假设当前 p[0] 位于 pos[i],已匹配的字符范围是 pos[i, …, k],不匹配的位置是 pos[k+1],即 P[0, …, k-i] 和 T[i, …, k] 已经匹配,p[k-i+1] != t[k+1]。如果要退回到当前状态前的某个状态 s,即把 P 向右移动 x 个字符,如果移动前的字符串和移动后有交集的话,P[0, …, j] 和 P[x, …, x+j] 必须匹配(0 < j < m-x),从 p[j+1] 开始和主串对应位置的字符比较:

      i                   k
pos   11  12  13  14  15  16  17  18  19  20  21  22
    +---+---+---+---+---+---+---+---+---+---+---+---+
T   | A | B | C | D | A | B | C | D | A | B | D | E |
    +---+---+---+---+---+---+---+---+---+---+---+---+
    +---+---+---+---+---+---+---+
P   | A | B | C | D | A | B | D |
    +---+---+---+---+---+---+---+
                    +---+---+---+---+---+---+---+
P'                  | A | B | C | D | A | B | D |
                    +---+---+---+---+---+---+---+
                    | <- -> |

KMP 算法就是要找出 j 的最大值,这样就能尽量减少重复比较的次数。可以看到 j 的值与字符串 T 无关,只与模式串 P 有关。这里用一个一维数组 next 保存转移的状态,对于 j>0,next[j] 表示当前状态为 j,如果输入不匹配应该退回到状态 next[j] 继续比较。例如下面是比较过程中的某个状态:

                        1                   2
pos 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
T   A B C Z A B C D A E Z A B C D A B C D A B D E
P           A B C D A B D
                      *

在 pos[9] 发现不匹配,根据预处理得到的下一个状态,应该把 p[0] 向右移动到 pos[8],p[0] 和 t[8] 匹配,然后从 pos[9] 开始比较:

                        1                   2
pos 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
T   A B C Z A B C D A E Z A B C D A B C D A B D E
P                   A B C D A B D
                      *

发现不匹配,由于该位置前已经没有重叠的字串,所以只能向右移动一个字符,再从头比较。经过两次移动后:

                        1                   2
pos 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
T   A B C Z A B C D A E Z A B C D A B C D A B D E
P                         A B C D A B D
                          *

当在 pos[17] 发现不匹配时,向右移动使 p[0] 和 pos[15] 对齐,从 pos[17] 开始比较:

                        1                   2
pos 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
T   A B C Z A B C D A E Z A B C D A B C D A B D E
P                                 A B C D A B D
                                      *

到 pos[21] 发现完全匹配,比较过程结束。

根据以上的例子,可以得到下面的比较程序:

char* do_kmp(const char *text, int tlen, const char *pattern,
      int plen, int next[])
{
   int i = 0, j = 0;

   while (i < tlen) {
      while (j != -1 && pattern[j] != text[i])
         j = next[j];

      ++i;
      ++j;
      if (j == plen)
         return (char*)(text + i - j);
   }

   return NULL;
}

上面的程序有个小问题,就是当模式串的末尾已超出主串末尾,而当前的比较位置还没到达主串末尾的时候,比较并不会立刻终止。不过这样的比较次数一般不多,和加上判断条件相比,后者要做的额外判断可能还要多一些。后面给出了比较过程的另一种实现,可以避免这个问题。

参考资料 [3] 中提到了一个构造模式串的有限状态自动机来匹配的算法,其中保存转移状态用了一个二维数组:一维是输入字符,另一维是对应于某个输入的转移状态;而 KMP 算法只用了一个一维数组,原因在于期望输入字符可以通过当前状态来获得,并且状态只分为匹配和不匹配两种(自动机可以根据不匹配字符的不同跳转到不同的状态),从而节省了空间。KMP 算法可以认为是有限状态自动机的一个特例,两者的不同之处在于 KMP 的模式串是确定的,而有限状态自动机可以处理正则表达式等模式串。

假设已知 next[j]=k,即已知 P[0, …, j] 和 P[x, …, x+j] 匹配,求 next[j+1]。为了方便统一处理,令 next[0]=-1 作为后退的终止条件。这里分两种情况讨论:

  1. 如果 p[j+1]=p[x+j+1],说明是期望的输入,可以直接进入下一个状态,即 next[j+1]=next[j]+1。例如模式串“ABCDABD”,已知 next[5]=1,表示当在状态 5 时(这时期望输入是 p[5]=’B’),如果输入和期望输入不匹配可以回到状态 1,让 p[1](新的期望输入 ‘B’)和不匹配位置上的字符重新比较。如果 p[2]=p[6],说明在状态 6 时(此时期望输入为 p[b]=’D’),如果实际输入和期望输入不匹配时可以回到状态 2,让 p[2](新的期望输入 ‘C’)和不匹配位置上的字符比较,从而避免了 p[0],p[1] 的重复比较。
  2. 如果 p[j+1]<>p[x+j+1],说明下一个字符不匹配,那么退回到前一个匹配的状态 next[j](next[j] 表示 P[0, …, next[j]] 和 T[x, …, x+next[j]] 匹配),看新的期望输入是否和当前输入一样。如果一样则是情况 1,不一样则再退回到 next[next[j]]……直到进入情况 1 或者退到状态为 -1。

根据分析,下面是一个 c 语言实现:

void kmp_transition_table(const char *pattern, int len, int next[])
{
   int state = 0, last_state /* = next[0] */ = -1;

   next[0] = -1;

   while (state < len - 1) {
      while (last_state != -1 && pattern[state] != pattern[last_state])
         last_state = next[last_state];

      ++state;
      ++last_state;
      next[state] = last_state;
   }
}

可以发现计算状态转移的过程和实际比较的过程很相似(计算状态转移可以看成模式串的自我匹配)。根据上面的程序,对于模式串“ABCDABD”,可以得到下面的状态转移图:

            +-----------------------------------+
            |                                   |
            +--------------------------+        |
            |                          |        |
            +-----------------+        |        |
            |                 |        |        |
            +--------+        |        |        |
            |        |        |        |        |
            v        |        |        |        |
+----+    +---+ A  +---+ B  +---+ C  +---+ D  +---+ A  +---+ B  +---+ D  +===+
| -1 | -> | 0 | -> | 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 | -> | 6 | -> | 7 |
+----+    +---+    +---+    +---+    +---+    +---+    +---+    +---+    +===+
  ^         |        ^        ^                          |        |
  |         |        |        |                          |        |
  +---------+        +--------|--------------------------+        |
                              |                                   |
                              +-----------------------------------+

从上面的状态转移图看到,当在状态 5 不匹配时退回到状态 1,很明显状态 5 和状态 1 的期望输入都是 ‘B’,既然在状态 5 时不匹配,退回到状态 1 也同样不匹配,应该继续往后退才对,因此有下面的改进:

void kmp_transition_table(const char *pattern, int len, int next[])
{
   int state = 0, last_state /* = next[0] */ = -1;

   next[0] = -1;

   while (state < len - 1) {
      while (last_state != -1 && pattern[state] != pattern[last_state])
         last_state = next[last_state];

      ++state;
      ++last_state;

      if (pattern[state] == pattern[last_state])
         next[state] = next[last_state];
      else
         next[state] = last_state;
   }
}

修改后对于模式串“ABCDABD”生成新的状态转移图如下:

            +--------------------------------------------+
            |                                            |
            +--------------------------+                 |
            |                          |                 |
            +-----------------+        |                 |
            |                 |        |                 |
            +--------+        |        |                 |
            |        |        |        |                 |
            v        |        |        |                 |
+----+    +---+ A  +---+ B  +---+ C  +---+ D  +---+ A  +---+ B  +---+ D  +===+
| -1 | -> | 0 | -> | 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 | -> | 6 | -> | 7 |
+----+    +---+    +---+    +---+    +---+    +---+    +---+    +---+    +===+
  ^         |                 ^                 |                 |
  |         |                 |                 |                 |
  +---------+                 +-----------------|-----------------+
  |                                             |
  +---------------------------------------------+

Linux 内核里也有 kmp 的实现,在 lib/ts_kmp.c 中,主要用于网络过滤等方面。

最后是一个带 debug 信息的完整 c 程序,输出状态转移表以及每次比较的情况。

/*--------------------------------------*/
/* a demonstration of the KMP algorithm */
/* http://ouonline.net/      2011.06.03 */
/*--------------------------------------*/

#include <stdio.h>
#include <stdlib.h>

#define KMP_DEBUG

#ifdef KMP_DEBUG
static void kmp_debug_transition_table(int next[], int len)
{
   int i;

   printf("==================================\n");
   printf("transition table:\n");

   printf("index   0");
   for (i = 1; i < len; ++i) {
      if (i < 10 && next[i] < 0)
         printf(" ");
      printf(" %d", i);
   }
   printf("\n");

   printf("state  ");
   for (i = 0; i < len; ++i) {
      if (i < 10)
         printf("%d ", next[i]);
      else /* if (i < 100) */ {
         if (next[i] >= 0 && next[i] < 10)
            printf(" %d ", next[i]);
         else
            printf("%d ", next[i]);
      }
   }

   printf("\n==================================\n");
}
#endif

void kmp_transition_table(const char *pattern, int len, int next[])
{
   int state = 0, last_state /* = next[0] */ = -1;

   next[0] = -1;

   while (state < len - 1) {
      while (last_state != -1 && pattern[state] != pattern[last_state])
         last_state = next[last_state];

      ++state;
      ++last_state;

      if (pattern[state] == pattern[last_state])
         next[state] = next[last_state];
      else
         next[state] = last_state;
   }

#ifdef KMP_DEBUG
   kmp_debug_transition_table(next, len);
#endif
}

#ifdef KMP_DEBUG
static void kmp_debug_compare(const char *text, int tlen,
                              const char *pattern, int plen,
                              int i, int j)
{
   int c, k;

   if (tlen > 10) {
      printf("     ");
      for (c = 1; c < tlen / 10; ++c)
         printf("                   %d", c);
      if (tlen % 10 != 0)
         printf("                   %d", c);
      printf("\n");
   }
   printf("pos");
   for (c = 0; c <= tlen / 10; ++c)
      for (k = 0; k < 10; ++k)
         if (c * 10 + k < tlen)
            printf(" %d", k);
   printf("\n");

   printf("T  ");
   for (c = 0; c < tlen; ++c)
      printf(" %c", text[c]);
   printf("\n");

   printf("P  ");
   for (c = 0; c < i - j; ++c)
      printf("  ");
   for (c = 0; c < plen; ++c)
      printf(" %c", pattern[c]);
   printf("\n");

   printf("   ");
   for (c = 0; c < i; ++c)
      printf("  ");
   printf(" *\n");

   printf("---------------------------------\n");
}
#endif

char* do_kmp(const char *text, int tlen, const char *pattern,
      int plen, int next[])
{
   int i = 0, j = 0;

   while (plen - j + i <= tlen) {
#ifdef KMP_DEBUG
      kmp_debug_compare(text, tlen, pattern, plen, i, j);
#endif
      if (pattern[j] == text[i]) {
         ++i;
         ++j;
         if (j == plen)
            return (char*)(text + i - j);
      } else {
         j = next[j];
         if (j == -1) {
            ++i;
            j = 0;
         }
      }
   }

   return NULL;
}

int kmp(const char *text, int tlen, const char *pattern, int plen,
      const char **match_pos)
{
   int *next;

   *match_pos = NULL;

   if (!text || !pattern || !match_pos || plen < 0 || tlen < 0)
      return -1;

   if (plen > tlen)
      return 0;

   next = malloc(plen * sizeof(int));
   if (!next)
      return -2;

   kmp_transition_table(pattern, plen, next);
   *match_pos = do_kmp(text, tlen, pattern, plen, next);

   free(next);

   return 0;
}

#include <string.h>

int main()
{
   int ret;
   const char *text = "ABCZABCDAEZABCDABCDABDE", *pattern = "ABCDABD", *pos;

   ret = kmp(text, strlen(text), pattern, strlen(pattern), &pos);
   if (ret != 0)
      fprintf(stderr, "error.\n");
   else {
      if (pos == NULL)
         printf("no match.\n");
      else
         printf("pos = %lu\n", pos - text);
   }

   return 0;
}

参考资料

[1] 基于有限状态自动机分析KMP字符串匹配算法
[2] 维基百科上的KMP词条
[3] 算法导论(第二版),(美) Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein 著,潘金贵,顾铁成,李成法,叶懋 译
[4] KMP算法深度解析

发表于 2011年6月3日
  1. 2011年6月3日 19:21 | #1

    。。。。。。
    ASCII的自动机用啥工具画的。。。。。

    • ou
      2011年6月3日 20:15 | #2

      vim……
      vim有一个插件用来画ASCII图的,忘了叫什么名字了,我用了一下觉得不好用就删了

显示 隐藏 1 trackbacks

发表评论

XHTML: 您可以使用这些标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>