字符串匹配的基本解决方案,是在长串中从头至尾遍历匹配模式串,直到找到完全匹配的位置,这样做一个最大的问题就是每次都重头开始匹配,完全没有用到已经匹配过的结果,非常的浪费,于是自动有限机和KMP就是基于这种利用已经匹配到的结果,在不匹配的位置出现时,立即查找下一个有效位置的算法。
在列出有限自动机的定义之前,想先讲讲这个算法的思想。所谓有限自动机机,我理解就是一张状态转移表,表头包括有限的模式串字符集与可能产生的状态。模式串字符集很好理解,例如要查找的模式串为aaba,那字符集就是{a, b};可能产生的状态也很好理解,也用aaba举例,可能产生的匹配结果无非是,a, ab, aab, aaba, 那状态也就是0,1,2,3,4,表示的是当前匹配成功多少位了,只有当状态达到4的时候,才表示完全匹配到了。
字符串匹配的有限自动机的关键,就在于构建这个状态转移表。
下面给出《算法导论》里自动有限机的定义:
一个有限自动机M是一个5元组(Q, q0, A, ∑, δ)
- Q是状态的有限集合
- q0∈Q 是Q的初始状态
- A 是Q的子集,是一个特殊的接受状态集合
- ∑ 是有限输入字母表
- δ是一个从Q×∑到Q的函数,成为M的转移函数
有点抽象,但是对应到字符串匹配的问题里看看,就一目了然了,下面将用于匹配的模式串用P表示。
Q:就是此前提到的字符串可能匹配到的数目,从0到P.length;q0肯定是0呀;A很显然在完全匹配的情况下只能是P.length;∑ 就是前文所说的P的字符集,而重中之重的转移函数δ,就是接下来要详细解析一下的东西了。
状态转移函数其实也很好理解,以aaba为例。假设当前aaba与被匹配的字符串已经匹配到了aa两个字符,那么当前的状态就是2,在状态2的前提下,去查看下一个字符,如果下一个字符是b那么状态很自然就转移成了2+b= 2+1=3,如果下一个字符是a,a和b不相等了,那此时的状态是几呢?是0吗?需要重新开始匹配吗?显然不是呀,因为aaa 和 aaba明显 还是可以成功匹配aa的呀,所以状态2+a的结果仍旧是2,这个值的求解过程简单说来就是每当遇到一个不匹配的位置时,查看此前已经匹配成功的结果后缀与P的前缀最长的公共部分,例如aab的前缀与aaa的后缀能匹配到的最大长度就是2(这一部分算法导论里给了非常详细的证明,因为公式实在不好敲,加上论证也比较绕口,就不贴了哈,这个思想其实就是KMP算法的基础,下一篇文章会再分析)。这就是状态转移表的一行,现在我试着把整个状态转移表画出来。
| 状态 | a | b|
| -- |:-----:|
| 0 | 1 | 0|
| 1 | 2 | 1|
| 2 | 2 | 3|
|3| 4| 0|
|4| 2| 1|
要求出状态4与字符集的转移关系其实是为了查找下一个匹配位置的。而状态值,我啰嗦一下,就是表示当前能够匹配成功字符串长度,例如状态3+b=0,表示aabb的后缀( abb ,bb, b ) 都没有办法和aab进行匹配,我们就可以跳过abb和P的比较,直接进行到b之后的下一个字符了,这就是算法利用已知结果免去重复计算的方法。我们通过在状态表中根据当前状态+下一个字符输入查询得到新的状态,然后比较新的状态是否就是可接受状态P.length 来判断是否匹配成功,从而最终完成字符串的匹配。这就是自动有限机用在字符串匹配里的计算过程。
下面我贴一下求解状态转移表的伪代码
compute-transition-function(P, ∑)
m = P.length
for q = 0 to m
for each character a in ∑
k = min(m+1, q+2)
repeat
k = k -1
until P[0..k] == P[q-k..q]a
δ(q, a) = k
return δ