了解Knuth-Morris-Pratt算法

Question

谁可以给我解释一下这个？我一直在阅读它,但仍然很难遵循.

文字:ababdbaababa
模式:ababa

ababa的表是-1 0 0 1 2.

我想我理解表是如何构建的,但是,我不明白一旦发生不匹配,如何转换.好像我们甚至在转移时都不使用桌子？

我们什么时候用这张桌子？

Answer 1

这里我简要描述了计算前缀函数并在此处移动文本.

有关详细信息:Knuth-Morris-Pratt字符串搜索算法

翻阅文字:

Text:     ABC ABCDAB ABCDABCDABDE
Pattern : ABCDABD

场景1 - 模式和文本中存在/是一些匹配的字符.
例如1:这里有3个匹配的字符.

从表中获取3个字符的值.(索引2,ABC)即0因此shift = 3 - 0即3

例如2:这里有6个匹配的字符.

从表中获取6个字符的值.(索引5,ABCDAB)即2因此shift = 6-2即4

场景2 - 如果没有匹配的字符,则移动一个.

Answer 2

当您的不匹配发生时使用该表.让我们将模式应用于您的文本:

如果您的模式可以是文本,则从第一个位置开始,您开始将模式与模式匹配并进行测试.你比较text[1]有pattern[1]和原来是一场比赛.你做同样的text[2],text[3]和text[4].

当你想text[5]与pattern[5]你匹配时没有匹配(d<> a).然后你知道你的模式不会从第一个位置开始.然后,您可以再次为位置2重新开始匹配,但效率不高.您现在可以使用该表.

发生错误,pattern[5]因此您转到table[5]2.这告诉您可以使用2个已匹配的字符再次在当前位置开始匹配.您可以从之前的位置(1)+ table[5](2)= 3 开始,而不必开始匹配位置2 .事实上,如果我们看一下text[3]和text[4]我们看到,它等于pattern[1]和pattern[2],respectivily.

表中的数字表示发生错误时已经匹配了多少个位置.在这种情况下,下一个模式的2个字符已经匹配.然后,您可以立即开始匹配位置3并跳过位置2(因为从位置[2]开始无法找到模式).

Answer 3

嗯,这是一个古老的话题,但希望将来有人能够看到它.上面给出的答案是好的,但我自己通过一个例子来看看究竟发生了什么.

博览会的第一部分来自wiki,我真正想要详述的部分是如何构建这种回溯数组.

开始:

我们通过算法(相对人工)运行,其中

W = "ABCDABD" and 
S = "ABC ABCDAB ABCDABCDABDE". 

在任何给定时间,算法处于由两个整数确定的状态:

m 这表示S中的位置,这是W的预期匹配的开始

i W中的索引表示当前正在考虑的字符.

在每一步中,我们比较S[m+i]有W[i]和推动,如果他们是平等的.这在运行开始时被描述为

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

我们继续比较W的连续字符到S的"并行"字符,如果它们匹配则从一个字符移动到下一个字符.然而,在第四步中,我们得到S [3]是一个空格而W [3] ='D',一个不匹配.我们注意到S中的位置0和3之间没有"A",而是在0处,而不是开始在S [1]再次搜索; 因此,在检查过所有这些字符之前,我们知道如果我们再次检查它们就没有机会找到匹配的开头.因此,我们转到下一个字符,设置m = 4和i = 0.

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

我们很快就获得了几乎完全匹配的"ABCDAB",当时在W [6](S [10]),我们再次出现差异.然而,就在当前部分比赛结束之前,我们通过了一个"AB",这可能是新比赛的开始,所以我们必须考虑到这一点.我们已经知道这些字符与当前位置之前的两个字符匹配,我们不需要再次检查它们; 我们只需重置m = 8,i = 2并继续匹配当前字符.因此,我们不仅省略了先前匹配的S字符,而且还省略了先前匹配的W字符.

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

然而,这种搜索立即失败,因为模式仍然不包含空格,因此在第一次尝试中,我们返回到W的开头并开始搜索S的下一个字符:m = 11,重置i = 0.

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

我们再次立即点击匹配"ABCDAB"但是下一个字符'C'与单词W的最终字符'D'不匹配.如前所述,我们设置m = 15,从两个开始 - 字符串"AB"通向当前位置,设置i = 2,并从当前位置继续匹配.

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

这次我们能够完成比赛,其第一个角色是S [15].

上面的示例包含算法的所有元素.目前,我们假设存在"部分匹配"表T,如下所述,其表示在当前的匹配以不匹配结束的情况下我们需要在哪里寻找新匹配的开始.构造T的条目使得如果我们具有从S [m]开始的匹配,其在比较S [m + i]和W [i]时失败,则下一个可能的匹配将从索引m + i开始 - T [我在S中(也就是说,T [i]是在不匹配之后我们需要做的"回溯"量).这有两个含义:首先,T [0] = -1,表示如果W [0]不匹配,我们不能回溯,只需检查下一个字符; 第二,尽管下一个可能的匹配将从索引m + i - T [i]开始,如上例所示,我们不需要在此之后实际检查任何T [i]字符,以便我们继续从W搜索[T [I]].

回溯阵列施工:

所以这个回溯数组T []我们将调用lps [],让我们看看我们如何计算这个人

lps[i] = the longest proper prefix of pat[0..i] 
            which is also a suffix of pat[0..i].

示例:对于"AABAACAABAA"模式,

lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

//所以只是快速通过这个

 lps[0] is just 0 by default
 lps[1] is 1 because it's looking at AA and A is both a prefix and suffix
 lps[2] is 0 because it's looking at AAB and suffix is B but there is no prefix equal to B unless you count B itself which I guess is against the rules
 lps[3] is 1 because it's looking at AABA and first A matches last A
 lps[4] is 2 becuase it's looking at AABAA and first 2 A matches last 2 A
 lps[5] is 0 becuase it's looking at AABAAC and nothing matches C
 ...


 For the pattern “ABCDE”, lps[] is [0, 0, 0, 0, 0]
 For the pattern “AAAAA”, lps[] is [0, 1, 2, 3, 4]
 For the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3]
 For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

如果你想一想这就完全有意义了......如果你不匹配,你想尽可能地回去,你走多远(后缀部分)本质上是前缀,因为你必须开始匹配第一个字符再次定义.所以如果你的字符串看起来像

aaaaaaaaaaaaaaa..b..aaaaaaaaaaaaaaac并且你在最后一个字符上不匹配,那么你想重新aaaaaaaaaaaaaaa用作你的新头,只要想一想