字符串匹配算法

一、简介

文本信息可以说是迄今为止最主要的一种信息交换手段，而作为文本处理中的一个重要领域——字符串匹配，就是我们今天要说的话题。（原文还特意提及文本数据数量每18个月翻一番，以此论证算法必须要是高效的。不过我注意到摩尔定律也是18个月翻番，这正说明数据的增长是紧紧跟随处理速度的，因此越是使用高效的算法，将来待处理的数据就会越多。这也提示屏幕前的各位，代码不要写得太快了……）

字符串匹配指的是从文本中找出给定字符串（称为模式）的一个或所有出现的位置。本文的算法一律输出全部的匹配位置。模式串在代码中用x[m]来表示，文本用y[n]来，而所有字符串都构造自一个有限集的字母表Σ，其大小为σ。

根据先给出模式还是先给出文本，字符串匹配分为两类方法：

· 第一类方法基于自动机或者字符串的组合特点，其实现上，通常是对模式进行预处理；

· 第二类方法对文本建立索引，这也是现在搜索引擎采用的方法。

本文仅讨论第一类方法。

文中的匹配算法都是基于这样一种方式来进行的：设想一个长度为m的窗口，首先窗口的左端和文本的左端对齐，把窗口中的字符与模式字符进行比较，这称为一趟比较，当这一趟比较完全匹配或者出现失配时，将窗口向右移动。重复这个过程，直到窗口的右端到达了文本的右端。这种方法我们通常叫sliding window。

对于穷举法来说，找到所有匹配位置需要的时间为O(mn)，基于对穷举法改进的结果，我们按照每一趟比较时的比较顺序，把这些算法分为以下四种：

1. 从左到右：最自然的方式，也是我们的阅读顺序

2. 从右到左：通常在实践中能产生最好的算法

3. 特殊顺序：可以达到理论上的极限

4. 任意顺序：这些算法跟比较顺序没关系（例如：穷举法）

一些主要算法的简单介绍如下：

从左到右

采用哈希，可以很容易在大部分情况下避免二次比较，通过合理的假设，这种算法是线性时间复杂度的。它最先由Harrison提出，而后由Karp和Rabin全面分析，称为KR算法。

在假设模式长度不大于机器字长时，Shift-Or算法是很高效的匹配算法，同时它可以很容易扩展到模糊匹配上。

MP是第一个线性时间算法，随后被改进为KMP，它的匹配方式很类似于自动机的识别过程，文本的每个字符与模式的每个字符比较不会超过log_Φ(m+1)，这里Φ是黄金分隔比1.618，而随后发现的类似算法——Simon算法，使得文本的每个字符比较不超过1+log₂m，这三种算法在最坏情况下都只要2n-1次比较。（抱歉限于我的水平这一段既没看懂也没能查证，大家就看个意思吧）

基于确定性有限自动机的算法对文本字符刚好只用n次访问，但是它需要额外的O(mσ)的空间。

一种叫Forward Dawg Matching的算法同样也只用n次访问，它使用了模式的后缀自动机。

Apostolico-Crochemore算法是一种简单算法，最坏情况下也只需要3n/2次比较。

还有一种不那么幼稚（Not So Naive）的算法，最坏情况下是n平方，但是预处理过程的时间和空间均为常数，而且平均情况下的性能非常接近线性。

从右到左

BM算法被认为是通常应用中最有效率的算法了，它或者它的简化版本常用于文本编辑器中的搜索和替换功能，对于非周期性的模式而言，3n是这种算法的比较次数上界了，不过对于周期性模式，它最坏情况下需要n的二次方。

BM算法的一些变种避免了原算法的二次方问题，比较高效的有：Apostolico and Giancarlo算法、Turbo BM算法和Reverse Colussi算法。

实验的结果表明，Quick Search算法（BM的一个变种）以及基于后缀自动机的Reverse Factor和Turbo Reverse Factor算法算是实践中最有效的算法了。

Zhu and Takaoka算法和BR算法也是BM的变种，它们则需要O(σ²)的额外空间。

特殊顺序

最先达到空间线性最优的是Galil-Seiferas和Two Way算法，它们把模式分为两部分，先从左到右搜索右边的部分，如果没有失配，再搜索左边的部分。

Colussi和Galil-Giancarlo算法将模式位置分为两个子集，先从左至右搜索第一个子集，如果没有失配，再搜索剩下的。Colussi算法作为KMP算法的改进，使得最坏情况下只需要3n/2次比较，而Galil-Giancarlo算法则通过改进Colussi算法的一个特殊情况，把最坏比较次数减少到了4n/3。

最佳失配和M最大位移算法分别根据模式的字符频率和首字位移，对模式位置进行排序。

Skip Search，KMP Skip Search和Alpha Skip Search算法运用“桶”的方法来决定模式的起始位置。

任意顺序

Horspool算法也是BM的一个变种，它使用一种移位函数，而与字符比较顺序不相干。还有其他的变种如：Quick Search算法，Tuned Boyer-Moore算法，Smith算法，Raita算法。

在接下来的章节中，我们会给出上面这些算法的实现。我们把字母表限定为ASCII码或者它的任意子集，编程语言用C，这就意味着数组索引是从0开始，而字符串以NULL结尾。

（第一章完。好像这些算法被挨个夸了个遍，反而不知道该选哪一种了，老外介绍别人的东西时就是这样，尽来虚的。）

二、穷举与自动机

穷举法又叫暴力法。大多数程序员眼里，它是幼稚的，但大师们不这么认为。

Rob Pike, 最伟大的C 语言大师之一, 在《Notes on C Programming》中阐述了一个原则：花哨的算法比简单算法更容易出bug、更难实现，尽量使用简单的算法配合简单的数据结构。而Ken Thompson——Unix 最初版本的设计者和实现者，禅宗偈语般地对Pike 的这一原则作了强调：拿不准就穷举（When in doubt , use brute force）。而对于装13爱好者来说，更是自豪的称其使用的是BF算法。

穷举法用在字符串匹配上，简单的描述就是，检查文本从0到n-m的每一个位置，看看从这个位置开始是否与模式匹配。这种方法还是有一些优点的，如：不需要预处理过程，需要的额外空间为常数，每一趟比较时可以以任意顺序进行。

尽管它的时间复杂度为O(mn)，例如在文本"aaaaaaaaaaaaaaaaaaaaaaaaaaa"中寻找"aaaaab"时，就完全体现出来了。但是算法的期望值却是2n，这表明该算法在实际应用中效率不低。

C代码如下：

1. void BF(char *x, int m, char *y, int n) {

2. int i, j;

3.

4. /* Searching */

5. for (j = 0; j <= n - m; ++j) {

6. for (i = 0; i < m && x[i] == y[i + j]; ++i);

7. if (i >= m)

8. OUTPUT(j);

9. }

10. }

11.

如果我们注意到C库函数是汇编优化过的，并通常能提供比C代码更高的性能的话，我们可以用memcmp来完成每一趟比较过程，从而达到更好的性能：

1. #define EOS '\0'

2.

3. void BF(char *x, int m, char *y, int n) {

4. char *yb;

5. /* Searching */

6. for (yb = y; *y != EOS; ++y)

7. if (memcmp(x, y, m) == 0)

8. OUTPUT(y - yb);

9. }

10.

11.

自动机的方法其实和穷举法有点相似，都是用最简单直白的方式来做事情。区别在于穷举法是在计算，而自动机则是查表。尽管自动机的构造过程有一点点难解，要涉及到DFA的理论，但是自动机的比较过程那绝对是简单到无语。

简单说来，根据模式串，画好了一张大的表格，表格m+1行σ列，这里σ表示字母表的大小。表格每一行表示一种状态，状态数比模式长度多1。一开始的状态是0，也就是处在表格的第0行，这一行的每个元素指示了当遇到某字符时就跳转到另一个状态。每当跳转到最终状态时，表示找到了一个匹配。

语言表述起来还是比较啰嗦，看代码就知道了：

1. #define ASIZE 256

2.

3. int preAut(constchar *x, int m, int* aut) {

4. int i, state, target, old;

5.

6. for (state = 0, i = 0; i < m; ++i) {

7. target = i + 1;

8. old = aut[state * ASIZE + x[i]];

9. aut[state * ASIZE + x[i]] = target;

10. memcpy(aut + target * ASIZE, aut + old * ASIZE, ASIZE*sizeof(int));

11. state = target;

12. }

13. return state;

14. }

15.

16.

17. void AUT(constchar *x, int m, constchar *y, int n) {

18. int j, state;

19.

20. /* Preprocessing */

21. int *aut = (int*)calloc((m+1)*ASIZE, sizeof(int));

22. int Terminal = preAut(x, m, aut);

23.

24. /* Searching */

25. for (state = 0, j = 0; j < n; ++j) {

26. state = aut[state*ASIZE+y[j]];

27. if (state == Terminal)

28. OUTPUT(j - m + 1);

29. }

30. }

（注：原文的代码使用一个有向图的数据结构，我遵循大师的指引，改用了更简单一点的数组）

从代码上我们很容易看出，自动机的构造需要时间是O(mσ)，空间也是O(mσ)（严格来说这份代码使用了O((m+1)σ)），但是一旦构造完毕，接下来匹配的时间则是O(n)。

匹配的过程前面已经说了，太简单了没什么好说的，这里就解释一下构造过程吧！

我们构造的目标是对应模式长度，构造出同样多的状态，用0表示初始状态，然后第一个字符用状态1表示，第二个用状态2表示，依次类推，直到最后一个字符，用m表示，也是最终状态。

一开始，数组全都置0，，这个时候的自动机遇到任何字符都转到初始状态。然后给它看模式的第一个字符，假设这是'a'吧，告诉它，状态0遇到'a'应该到一个新的状态——状态1，所以把第0行的第'a'列修改为1。而这个时候状态1还是空白的，怎么办呢？

这时候状态0就想呀，在我被告知遇到'a'要去状态1之前，我原本遇到'a'都要去状态0的，也就是修改之前第'a'列所指的那个状态，称为old状态吧；而现在我遇到'a'却要去一个新的状态，既然以前old状态能处理遇到'a'之后的事情，那么我让新的状态像old状态一样就好了。于是状态0把old状态拷贝到状态1。

现在轮到状态1了，给它看第二个字符，它也如法炮制，指向了状态2，又把old状态拷贝给了状态2。

于是，状态机就在这种代代传承的过程中构造完毕了。

虽然理论上自动机是最完美的匹配方式，但是由于预处理的消耗过大，实践中，主要还是用于正则表达式。

结语：穷举法与自动机各自走了两个极端，因此都没能达到综合性能的最佳，本文之后介绍的算法，可以看成是在穷举和自动机两者之间取舍权衡的结果。

三、位运算的魔法——KR与SO

位运算经常能做出一些不可思议的事情来，例如不用临时变量要交换两个数该怎么做呢？一个没接触过这类问题的人打死他也想不出来。如果拿围棋来做比喻，那么位运算可以喻为编程中的“手筋”。

按位的存储方式能提供最大的存储空间利用率，而随着空间被压缩的同时，由于CPU硬件的直接支持，速度竟然神奇般的提升了。举个例子，普通的数组要实现移位操作，那是O(n)的时间复杂度，而如果用位运算中的移位，就是一个指令搞定了。

KR算法

KR算法之前第一章介绍中说是利用哈希，原文这么介绍的。而我的看法是，哈希只是一个幌子。这个算法的基本步骤同穷举法一样，不同在于每趟比较前先比较一下哈希值，hash值不同就不必比较了。而如果hash值无法高效计算，这样的改进甚至还不如不改进呢。你想想，比较之前还要先计算一遍hash值，有计算的功夫，直接比都比完了。

KR算法为了把挨个字符的比较转化为两个整数的比较，它把一个m长度的字符串直接当成一个整数来对待，以2为基数的整数。这样呢，在第一次算出这个整数后，以后每次移动窗口，只需要移去最高位，再加上最低位，就得出一个新的hash值。但是m太大，导致超出计算机所能处理的最大整数怎么办？不用担心，对整数最大值取模，借助模运算的特性，一切可以完美的进行。而且由于是对整数最大值取模，所以取模这一步都可以忽略掉。

这是KR算法的代码：

1. #define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))

2.

3. void KR(char *x, int m, char *y, int n) {

4. int d, hx, hy, i, j;

5.

6. /* Preprocessing */

7. /* computes d = 2^(m-1) with

8. the left-shift operator */

9. for (d = i = 1; i < m; ++i)

10. d = (d<<1);

11.

12. for (hy = hx = i = 0; i < m; ++i) {

13. hx = ((hx<<1) + x[i]);

14. hy = ((hy<<1) + y[i]);

15. }

16.

17. /* Searching */

18. j = 0;

19. while (j <= n-m) {

20. if (hx == hy && memcmp(x, y + j, m) == 0)

21. OUTPUT(j);

22. hy = REHASH(y[j], y[j + m], hy);

23. ++j;

24. }

25.

26. }

27.

28.

我们可以看到，KR算法有O(m)复杂度的预处理的过程，总感觉它的预处理没有反映出模式本身的特点来，导致它的搜索过程依然是O(mn)复杂度的，只不过一般情况下体现不出来，在"aaaaaaaaaaaaaaaaaaaaaaaaa"中搜"aaaaa"就知道KR多慢了。

总的来说，KR算法比穷举强一点，比较次数的期望值是O(m+n)。

Shift Or 算法

为了最大限度的发挥出位运算的能力，Shift Or算法就有了一个最大缺陷：模式不能超过机器字长。按现在普遍的32位机，机器字长就是32，也就是只能用来匹配不大于32个字符的模式。而带来的好处就是匹配过程是O(n)时间复杂度的，达到自动机的速度了。而预处理所花费的时间与空间都为O(m+σ)，比自动机少多了。

我们来看看它怎么巧妙的实现“只看一遍”的：

假设我们有一个升级系统，总共有m个级别。每一关都会放一个新人到第0级上，然后对于系统中所有的人，如果通过考验，升一级，否则，咔嚓掉。而对于升到最高级的人，那说明他连续通过了m次考验，这就是我们要选拔的人。

KR算法的思路就是上面的升级规则，给出的考验就是你的位置上的字符与给出的文本字符是否一致。升满级了，说明在连续m个位置上与不断给出的文本字符一致，这也就是匹配成功了。

明白了这个思路后，疑问就开始出来了：检查哪些位置与文本字符一致，需要m次吧？那么整个算法就是O(mn)了？

现在就该位运算出场了，对，这个算法的思路是很笨，但是我位运算的效率高呀，事先我算出字母表中每个字符在模式中出现的位置，用位的方式存在整数里，出现的地方标为0，不出现的地方标为1，这样总共使用σ个整数；同样，我用一个整数来表示升级状态，某个级别有人就标为0，没人就标为1，整个系统升级就恰好可以用“移位”来进行，当检查位置的时候只需要与表示状态的整数“或”1次，所以整个算法就成O(n)了。Shift-Or算法名字就是这样来的。

有一个地方很奇怪，0和1的设定和通常的习惯相反呀，习惯上，喜欢把存在设为1，不存在设为0的。不过这里没有办法，因为移位新移出来的是0。

这时我们来看代码就容易理解多了：

1. #define WORDSIZE sizeof(int)*8

2. #define ASIZE 256

3.

4. int preSo(constchar *x, int m, unsigned int S[]) {

5. unsigned int j, lim;

6. int i;

7. for (i = 0; i < ASIZE; ++i)

8. S[i] = ~0;

9. for (lim = i = 0, j = 1; i < m; ++i, j <<= 1) {

10. S[x[i]] &= ~j;

11. lim |= j;

12. }

13. lim = ~(lim>>1);

14. return(lim);

15. }

16.

17. void SO(constchar *x, int m, constchar *y, int n) {

18. unsigned int lim, state;

19. unsigned int S[ASIZE];

20. int j;

21. if (m > WORDSIZE)

22. error("SO: Use pattern size <= word size");

23.

24. /* Preprocessing */

25. lim = preSo(x, m, S);

26.

27. /* Searching */

28. for (state = ~0, j = 0; j < n; ++j) {

29. state = (state<<1) | S[y[j]];

30. if (state < lim)

31. OUTPUT(j - m + 1);

32. }

33. }

代码中lim变量其实就是一个标尺，例如出现最高级的状态是01111111，那么lim就成了10000000，因此只要小于lim，就表示最高级上的0出现了。

原文中对Shift-Or算法的描述还是很难懂的，如果对着那段说明去看代码，有点不知所云的感觉。我还是直接对着代码才想出这个升级的比喻来。

四、可以滑动多远

记得在穷举法中，每一趟比较后，无论成与不成，都将模式向右滑动一个位置，然后继续比较。有没有办法能利用之前的比较结果，使得模式滑动的更远一点呢？

在介绍经典的KMP算法前，我先介绍几个简单的滑动类算法。

Not So Naive

同名字一样，这个算法的确有点幼稚，它根据模式的前两个字符是否相同来滑动比穷举法稍长一点的距离：如果前两个字符相同，那么文本中与第二个字符不同则必然也与第一个不同；如果前两个字符不同，则与第二个相同的文本字符必然与第一个不同。

那么这两种情况下不用比较都可以断定，文本字符与模式的第一个字符肯定不相同，于是能比穷举法多滑动1个位置。

代码见下：

这个算法仅需要常数时间和空间的预处理，比较过程中，先比较模式第二个字符，然后比较其余位置，为的就在某些情况下省掉第一个字符的比较，达到滑动的目的。不过复杂度依然是O(mn)的，比起穷举法或者有轻微改善吧。

想法的确够幼稚，仅仅只考虑了两个模式字符，滑动的步子也太小，能否考虑的更多一点呢？下面请看Quick Search算法。

Quick Search

见到这个名字，不禁让人想起快速排序了，快速排序在最坏情况下是n平方的复杂度，而通常情况下速度超级快，Quick Search莫非也是这样的？没错，就是这样，这个算法在模式长度短而字母表大时，有着优异的表现，尽管它的搜索时间复杂度是O(mn)。

算法的思想是这样，如果文本中某个字符根本就没在模式中出现过，那么就不需要再去和模式中的任何一个比较；如果该字符出现过，那么为了不漏掉可能的匹配，只好与最晚出现过的位置对齐进行比较了。

代码如下：

理解这个算法，请看22行，无论这一趟比较是否成功，都进行模式串的滑动，这个滑动就是根据窗口之外的第一个字符位于模式串的位置来决定的，你可以把窗口外第一个字符是否能匹配看成下一趟比较的前提。

现在你知道为何这个算法最适合在短模式和大字母表下运行了，因为字母表大，模式短，则文本字符不在模式中出现的几率就大，因此更大可能性得进行最长距离的滑动，而且模式短，花在比较上的时间就短，可以尽量多滑动。

美中不足的是这个算法最坏情况下复杂度还是O(mn)，尽管预处理中已经利用上了每一个模式字符了。通过滑动能找到一个线性算法吗？仔细审视一下比较过程，造成算法非线性的根本原因是什么？没错，文本串回溯了。让我们来看看一个真正的线性算法——MP，以及它的改进——KMP。

MP/KMP

本着文本串不回溯的目标，MP算法横空出世，它的一个重要指导思想是，凡是比较过，被认定为相同的文本字符，绝不再拿出来比。道理上也是能说得通的，因为既然和模式串一部分相同，那么它的信息就已经存在于模式串中了。预处理时，模式串自己和自己的一部分进行比较，存储下自身的相似信息——Next数组。

以后在比较时，如果某处失配了，根据之前预处理的结果，可以直接滑动到自身相似的那一部分与文本串对齐，然后从失配处继续比较，避免了文本串回溯。

伟大的计算机科学家Knuth，就是写TAOUP的那位，对MP算法进行了些许修正，加上了自己的名字，成了KMP。Knuth注意到，如果滑动前的那个模式字符与滑动后的模式字符相同的话，那么再比较必然再次失配，导致又一次滑动，与其多级滑动，不如一滑到底。

代码：

MP和KMP算法都达到了O(m)的预处理时间和空间，O(n+m)的比较时间，算法实现是如此简单优美，算法思想是如此无可挑剔，还能滑的更远吗？我们拭目以待。