基于有限自动机的字符串匹配

2013-09-27 #-algorithm

###引言###

看到这个题目感觉挺玄乎的。自动机在编译原理和软件工程里面都接触过。之前编译原理的课程中好像有拿自动机进行字符串匹配的练习和介绍。基于自动机的字符串匹配主要就是建立状态转移表。字符串匹配到某一个位置之后根据下一个匹配去查找状态转移表，从而决定进入哪一个状态。如果能够进入最后的终止状态，说明匹配成功。

自动机的学问我觉得够很多人去研究很多年的。真不好意思说这是基于自动机的字符串匹配。因为感觉攀上这个自动机之后，瞬间高端大气上档次了。

有限自动机通常可分确定有限状态自动机(DFA)和非确定有限状态自动机(NFA)。其中DFA相对比较简单，因为每种状态下针对不同的输入都能进入下一个确定的状态。但NFA却复杂的多。在一个状态下针对同一个输入下一步能进入的状态可能有多个，也可能没有。而普通的字符串匹配则只涉及DFA。但带正则表达式的字符串匹配如果构造自动机进行匹配肯定就涉及NFA了。

基于确定有限状态自动机的字符串匹配，核心是自动机状态转移的构造，而具体的构造过程和 KMP 算法的 next 数组的生成类似。

变量定义

为表述方便还是预先变量进行定义。des[N] 表示目标串，pat[M] 表示模式串, next[M] 数组功能和前面 KMP 算法是一样的，这里不再赘述。des[i…j] 表示 des[] 中从i到j的子串, pat[i…j]的定义类似，数组下标从1开始

对于长度为 M 的模式串，自动机的状态有 M + 1 个。用状态 0, 状态 1, … , 状态 M - 1, 状态 M 来表示。假设模式串中不同的字符个数为 C(注意 C 是模式串中不同的字符个数，模式串中某些字符可能会多次出现），那么我们建立一个 table[M + 1][C] 来存储构造的自动机的状态转移表

###自动机构造###

对于自动机的构造前面已经提到和 KMP 算法的 next 数组生成比较类似。当字符串匹配到某一个状态。下一步可能的输入有C + 1种（ C 的定义参照前面的变量定义）。这 C + 1 种输入分别对应模式串中所有出现的字符（占 C 种）和不在模式串中出现的字符（占1种，我们把所有不在模式串中出现的字符归为一类，因为他们编制之内，是临时工）

前面已经说过不带正则表达式的字符串匹配是基于 DFA 的。因此在某一个状态下，针对任何一个输入都可以进入下一个确定的状态。但是状态如何转移。首先针对模式串 des[M] ，状态机一共有 M + 1 个状态分别对应于 M + 1 个字符串匹配位置。分别为匹配 0 个字符，匹配前 1 个字符，匹配前 2 个字符，匹配前 3 个字符，……匹配前 M - 1 个字符，匹配全部 M 个字符。其中匹配 0 个字符为初始状态。匹配全部字符为结束状态。如果进入结束状态说明匹配成功。

现在假设自动机的前 j - 1 (j>0) 个状态已经构造完毕，接下来构造状态 j （状态 j-1 在输入为 pat[j] 的情况下会进入状态 j ）。假设我们当前处于状态 j 。下面要构造状态 j 下的 C + 1 个状态转移。首先对输入为 pat[j + 1] 的情况肯定是转入状态 j + 1 。

但如果输入不为 pat[j + 1] 呢？此时我们就要利用前面生成的 next 数组了。对于输入 pat[] 数组中的任意一个字符 ch （一共 C - 1 种可能的输入，这里将 pat[j + 1] 除外了，因为输入为 pat[j + 1] 的状态转移已经确定）。我们将 pat[1…j] + ch 组成一个字符串 str 。找 str 中满足既是前缀又是后缀的最长子串。求法和KMP算法中求 next 数组的方法类似。如果写成函数的话，可以类似于下面这样（没有实测）

void nextState(int **table, int *next, int j, char ch)	//参数嫌多可以把某些设为全局变量
{
	int p = next[j];
	while (p >= 0 && pat[p] != ch) {	//注意next求解时,next[0]设为-1,以便结束循环。
		p = next[p];
	}
	table[j][Index[ch]] = p + 1;			
}
/* --------------------------------------------------------------------------*/
/**
* 上面的Index[]可以作为一个全局的索引数组, 设置方法也很简单比如假设pat[]数组中
* 不同的元素一共有C个，可以将其取出来放在一个数组中，我们假设放在一个数组list
* 中分别为list[1],list[2]...list[C]。那么我们就令Index[list[i]] = i ，而对于所
* 有不在list中的字符other，可令Index[other] = C + 1。list的求取方法也很简单。
* 最简单的就是将pat[]先拷贝到list[]然后对list[]排序，剔除重复的。但pat[]是不能
* 排序的。
*/
/* ----------------------------------------------------------------------------*/

对于 pat[] 数组中不同的元素。我们可以像注释中说的那样，放在一个数组 list[] 中。这样求另外的 C - 1 种输入的状态转移就挨个调用 nextState 函数就行了。前面都是说的是如果输入的是 pat[] 数组中的字符的状态转移。但如果输入不是 pat[] 数组中的呢？这个很显然直接跳回到状态 0 ，因为任何包含该一个不在 pat[] 数组中的字符的子串都是不可能和 pat[] 匹配的。所以唯一的情况就是从状态 0 开始，再从 des[i + 1] 开始匹配。

###构造的原理###

至此求解自动机的状态转移大致介绍完毕。但前面我们只是介绍了该怎么求解状态转移。但至于为什么这么求解，却没有讲明。下面我们说说构造的原因。

假设自动机当前处于状态 j 。对于输入为 pat[j + 1] 和输入为不在 pat[] 中的字符的状态转移就不讨论了。前面已经进行了解释。我们只讨论输入为 pat[] 中的字符且不为 pat[j + 1] 的情况。假设对这种情况下的任何一个输入 ch 。首先按照前面的方法。将 pat[1…j] + ch 组合成一个字符串 str 。找出 str 中既是前缀又是后缀的最长子串设为 pat[1…k] 那么，在状态 j 下输入为 ch 的状态转移就为 k 。

为什么在状态j下输入为ch的状态转移为k。我们分两种情况进行讨论

第一种假设状态 j 下输入为 ch 的状态转移为 b 且(b > k)。这个转移的意思就是说输入 ch 时为 pat[1…b] 能匹配 str 的后 b 个字符。显然这与 pat[1…k] 是 str 既是前缀又是后缀的最长子串矛盾。

第二种情况。假设状态 j 下输入为 ch 的状态转移为 a 且 (a < k) 。那么 pat[1…a] 必须 str 的前缀和后缀，因为 pat[1…a] 要匹配 str 的后 a 个字符。则 pat[1…a] 肯定也是 pat[1…k] 的前缀。（ pat[1…a] 而且也是 pat[1…k] 的后缀，可以参考 KMP 算法，其中关于 next 数组生成的方面有相关介绍）。

对于跳到状态 a 。首先他可能回漏掉成功的匹配。最简单的，如果接下来 des 中接下来 M - k 个字符与 pat[k + 1…M] 相同，那么跳到 k 是肯定能匹配到的。但如果跳到 a 却不一定能匹配到。

另外如果跳到 a ，之后能匹配到的情况那么跳到 k 他也一定能匹配到。因为它能够回到 a 的状态。至于为什么，学学少数牛逼人士和多数装逼人士的口头禅。留给读者自己去思考（潜台词就是我也说不出个所以然来，可以结合实例来分析）。

###匹配策略###

至此我们就当状态转移已经全部求解完毕。下面要做的就是直接将 des[] 遍历一遍。如果有状态 C ，则匹配成功。可能多次，也可能零次匹配成功。简要代码（没有实测）

int state = 0;
for(int i = 1; i <= N; i++) {
	state = table[state][Index[des[i]];
	if (state == M) {
		printf("pattern matched at %d\n", i);
	}
}

###对比和KMP算法的区别###

KMP 算法匹配到 des[i] 时。如果模式串和目标串不同。要根据 des[i] 的值来确定模式串回退到哪个位置。并且 i 不变。 des[i] 还要和模式串回退位置的下一个进行比对。但自动机就直接根据 des[i + 1] 的值确定下一次状态转移了。整个匹配过程只需遍历遍历一次 des 。但 KMP 算法的比对次数可能要大于 N ，但不会超过 2N 。

KMP 算法中 next[] 生成复杂度不超过 2M ，匹配时复杂度不超过 2N 。自动机策略。状态转移生成为 O(CM) 。匹配时复杂度为 N 。但空间复杂度自动机要高。

至此对基于确定的有限状态机的字符串匹配讨论基本结束。

###引用###

geeksforgeeks关于基于有限自动机匹配字符串的介绍

不过感觉这篇介绍把他搞复杂了。本来 next[] 数组生成复杂度为 O(M) 。那么状态转移的生成就是 O(CM) 。但文章弄成了 O(CM ^ 3) 。并且上面给每个可能的输入都弄一个状态转移。也觉得没得必要。费时间费空间。