0%

站在DFA角度看KMP算法

概要

因为人工智能导论课的作业要求,站在DFA的角度上重新认识了KMP算法。

关于KMP算法,之前有过一篇文章介绍,不再过多介绍。前文链接
若是对KMP算法还不了解,最好还是先看前文,更好懂一些。

因为使用dfa对于kmp进行实现和我们一般写的kmp还是有些差别的,所以我在
下面表述的时候会使用KMP的一般表示法dfa表示法做区别。

其实如果是使用一般表示法,其实也没有必要站在DFA的角度。
而且DFA的表示法的效率,并没有我们一般表示法高。

关于DFA

确定有限状态自动机(DFA)就是一个自动机,在某状态下根据新的输入,进入新的状态。
确定-在确定的前置状态下,给定确认的输入,得到的新的状态时确认的
有限-状态的个数是有限的

DFA是一个有向图,图的结点代表状态,边代表转移条件。

理论过程

下文中使用,P串代表模板串(短串),T串代表文本串(长串)

过程就是两个部分:

  1. 对于模板串P建立好DFA
  2. 在DFA上对T串进行匹配,得出匹配结果

建立DFA的方法

(以下图示,P串=ABABAC)

  1. 根据P串建立一条主链,建立若干 (len(P)+1个) 状态节点 。每个状态节点均表示一个字符串,表示的内容为从初始状态节点出发,沿主链形成的字符串。
    如下图:3号状态结点表示的字符串为ABA,5号为ABABA,初始结点为空串
    t1.png
  2. 对所有的状态结点加上若干的转移路径。

规则如下:
设字符串集Q为现在所有状态结点所表示的字符串的集合。
对于字符串S定义它的S’串为它的最长公共前缀后缀(不包含本身)

现在Q的集合为{ABABAC,ABABA,ABAB,ABA,AB,A,空串}

关于S与S',举一些例子:ABABA – ABA, ABA-A, AB-空串。

对于任意一个不在集合Q中的字符串S ,若S'在Q中,则S需要指向表示字符串为S'的状态结点。否则S指向初始状态节点。

eg:对于5号状态结点(ABABA),若输入条件为B,则字符串表示为ABABA+B=ABABAB,它的S’串为ABAB,可由4号结点表示,故指向4号结点。

因ABABAC中的字符集为{A,B,C},故做出简略版本的DFA(不包含其他字符)。

t2.png
ps:3号结点少一条边C,忘了画了。

终结状态实际上也可以加上条件转移,加上才可以做多次匹配。

DFA的求解与存储表示

图片来自于《算法》第四版。
t3.jpg

对上面的DFA数组做一点解释
第一列: 前置状态为0(j=0),输入条件为ABC时,结果状态为(1,0,0)
后面同理。

这个结果与我们上面所说的内容是匹配的。
eg:当前值结点为5号,由5号结点代表的字符串ABABA

输入条件为A,ABABA+A=ABABAA,他的最长公共前缀后悔为A,可由1号结点表示。
输入条件为B,ABABA+B=ABABAB,他的最长公共前缀后悔为ABAB,可由4号结点表示。
输入条件为C,ABABA+C=ABABAC,在集合Q中可由终结结点表示。结果是6

DFA数组使用DFA[i][j]来表示 j号为转移前的状态结点,输入条件为i的转移后的结点。

在具体的实现的时候,整个DFA的求解是迭代的。

即在求解 dfa[][j]的时候dfa[][0~j-1]都已经求解出来了。

eg:以j=4为例,构建上面的DFA。(最终结果5,0,0)

首先定义一个X值,X值表示4号结点表示字符串ABAB的S’串=AB的表示结点,X=2

复制dfa[][X]的值给dfa[][j] (2,0,0)
修改根据长链的转移结果 (5,0,0)
修改X的值为5号结点对应的X值 X=3

5号结点的X值 = 5号结点表示字符串的S’串表示的结点
5号结点的表示的字符串 = 4号结点表示的字符串 + P[4]
5号串的S’ = 4号串的S’ 根据输入条件 P[4] 进行转移

给出所有的X值对应关系: X=f(j)

j f(j) 表示的字符串
0 / 空串
1 0 A
2 0 AB
3 1 ABA
4 2 ABAB
5 3 ABABA
5 0 ABABAC

这个X值实际上就是一般表示法中的next数组了。一般表示法中,f(0)的值常用-1;在dfa表示法中这个值并没有意义。
可以使用我在上篇文章中的代码打印出next数组验证一下。

对于这部分的理解如果不能理解还是看前文把,必须理解kmp是如何使用最长公共前缀后缀来优化匹配的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//求解DFA
void DFA()
{
int M = pat.length();
int R = 256;
dfa[pat[0]][0] = 1;
for (int X = 0, j = 1; j < M; j++)
{
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][X];
dfa[pat[j]][j] = j + 1;
X = dfa[pat[j]][X];
}
}

匹配过程:

对于通过上面方法建立的DFA,现在给出T串。
沿着DFA转移即可,没有什么可说的。

代码实现

此处代码参考《算法》第四版 ,只做最简单的实现。
在时间复杂度上是O(KN+M),M为P串的长度,N为T串的长度,K为字符集大小
但是在构造DFA的时候是O(K*M),比一般表示法的O(M)要大

鉴于M和K的大小一般是字符串匹配中各参数比较小的,差距可能没有太大。
但是在空间占用上,K倍就不可以接受了,远不如一般表示法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include 
using namespace std;
const int maxn = 1e3 + 10;
int dfa[256][maxn];
string pat,txt;
void DFA()
{
int M = pat.length();
int R = 256;
dfa[pat[0]][0] = 1;
for (int X = 0, j = 1; j < M; j++)
{
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][X];
dfa[pat[j]][j] = j + 1;
X = dfa[pat[j]][X];
}
}
int search()
{
int i, j;
int N = txt.length(), M = pat.length();

for (i = 0, j = 0; i < N && j < M; i++)
{
j = dfa[txt[i]][j];
}

if (j == M)
return i - M;
else
return -1;
}
int main()
{
cin>>pat>>txt;
DFA();
cout<endl;
}