我了解不良字符启发法的工作原理。当找到不匹配的字母x
时,只需移动模式,以使模式中最右边的x
与字符串中的x
对齐。而且很容易在代码中实现。
我想我也了解后缀启发式的工作原理。当找到合适的后缀s
时,请在模式中的不同位置找到相同的后缀,然后将其移动,以使模式中的s
与字符串中的s
对齐。但是我不明白如何在代码中做到这一点。我们如何查找模式中另一个位置是否存在相同的后缀?我们如何知道它的位置?代码:
void bmPreprocess1()
{
int i=m, j=m+1;
f[i]=j;
while (i>0)
{
while (j<=m && p[i-1]!=p[j-1])
{
if (s[j]==0) s[j]=j-i;
j=f[j];
}
i--; j--;
f[i]=j;
}
}
从http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm中获取对我来说没有意义...有人可以为此任务编写尽可能简单的伪代码吗?或以某种方式解释?
最佳答案
首先,我将使用p[i]
表示模式中的字符,m
模式长度,$
模式中的最后一个字符,即$ = p[m-1]
。
良好的后缀启发式案例1有两种情况。
情况1
考虑以下示例,
leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
cXXXbXXXcXXXcXXX
^
| mismatch here
因此,模式
XXX
中的子字符串cXXXbXXXcXXXcXXX
是很好的后缀。不匹配发生在字符c
。那么在不匹配之后,我们应该将4移到右边还是8?如果我们按如下所示将4移位,则将再次发生相同的错误(
b
导致错误c
), leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
cXXXbXXXcXXXcXXX
^
| mismatch occurs here again
因此,在这种情况下,我们实际上可以向右移动8个字符。
情况二
让我们来看另一个例子
leading TEXT cXXXcXXXbXXXcXXX rest of the TEXT
cXXXXcXXXbXXXcXXX
^
| mismatch happens here
我们可以在这里移动4或8或更多吗?显然,如果我们移位8或更多,我们将错过将模式与文本匹配的机会。因此,在这种情况下,我们只能向右移动4个字符。
那么这两种情况有什么区别?
区别在于,在第一种情况下,不匹配的字符
c
加上后缀XXX
为cXXX
,与下一个(从右数起)匹配的XXX
加上前一个字符相同那。在第二种情况下,cXXX
与下一个匹配项(从右数起)加上该匹配项之前的字符不同。因此,对于任何给定的GOF SUFFIX(让我们将其称为
XXX
),我们需要弄清楚这两种情况下的变化,(1)在GOOD SUFFIX和GOOD SUFFIX之前的字符(我们将其称为c
),模式中的字符也匹配好后缀+下一个字符的下一个(从右数)匹配,(2)字符加GOF SUFFIX不匹配例如,对于情况(1),如果具有模式
0XXXcXXXcXXXcXXXcXXXcXXX
,并且在c
的第一次测试失败后,则可以向右移动20个字符,并使0XXX
与测试的文本对齐。这就是数字20的计算方式,
1 2
012345678901234567890123
0XXXcXXXcXXXcXXXcXXXcXXX
^ ^
发生不匹配的位置是20,移位后的子字符串
0XXX
的位置将从20到23。0XXX
从位置0开始,所以20-0 = 20。对于情况(2),如本例中的
0XXXaXXXbXXXcXXX
,如果c
的第一次测试失败,则只能向右移动4个字符,并使bXXX
与测试的文本对齐。这就是数字
4
的计算方式, 0123456789012345
0XXXaXXXbXXXcXXX
发生不匹配的位置是12,下一个要代替的子字符串是
bXXX
,它从位置8、12-8 = 4开始。如果我们设置j = 12
和i = 8
,则移位是,在代码中为j - i
。边境
要考虑所有的后缀,我们首先需要了解什么是所谓的
s[j] = j - i;
。边框是一个子字符串,它既是字符串的
border
前缀又是proper
后缀。例如,对于字符串proper
,XXXcXXX
是边框,X
是边框,XX
也是如此。但是XXX
不是。我们需要确定模式后缀的最宽边界的起点,并且此信息保存在数组XXXc
中。如何确定
f[i]
?假设我们知道
f[i]
,并且对于所有其他f[i] = j
具有f[k]
的字母,这意味着从位置i < k < m
开始于位置i
的后缀的最宽边框。我们想基于j
查找f[i-1]
。例如,对于模式
f[i]
,在位置aabbccaacc
处,后缀为i=4
,其最宽边框为ccaacc
(cc
),因此为p[8]p[9]
。现在我们想根据对j = f[i=4] = 8
,f[i-1] = f[3]
,...的信息来了解f[4]
,对于f[5]
,后缀现在为f[3]
。在bccaacc
位置,它是j-1=7
!= a
,它是p[4-1]
。因此b
不是边界。我们知道宽度bcc边界必须以
bccaacc
开头,后缀的边界必须从positin b
开始,在本例中为j = 8
。 cc
在cc
位置上的c
边框最宽。因此,我们继续比较j = f[8]
与9
。他们又不平等了。现在后缀为p[4-1]
,并且在位置p[j-1]
处只有零长度的边框。所以现在是p[9] = c
,它是10
。因此,我们继续进行比较,将j = f[9]
与10
进行比较,它们不相等,那就是字符串的结尾。那么p[4-1]
仅具有零长度的边框,使其等于10。从更一般的意义上描述过程
因此,
p[j-1]
的含义是这样的, Position: 012345 i-1 i j - 1 j m
pattern: abcdef ... @ x ... ? x ... $
如果位置
f[3]
处的字符f[i] = j
与位置@
处的字符i - 1
相同,我们知道?
或j - 1
。边框后缀f[i - 1] = j - 1;
从位置--i; --j; f[i] = j;
开始。但是,如果位置
@x ... $
上的字符j-1
与位置@
上的字符i - 1
不同,我们必须继续在右侧搜索。我们知道两个事实:(1)现在我们知道边界宽度必须小于从位置
?
开始的宽度,即小于j - 1
。其次,边框必须以j
开头并以字符x...$
结束,否则可以为空。基于这两个事实,我们继续在子字符串
@...
(从位置j到m)中搜索以$
开头的边框。然后,下一个边框应位于等于x ... $
的x
,即j
。然后,我们将字符f[j];
与j = f[j];
之前的字符(在@
处)进行比较。如果它们相等,则找到边界,否则,继续进行处理,直到j> m。以下代码显示了此过程, while (j<=m && p[i-1]!=p[j-1])
{
j=f[j];
}
i--; j--;
f[i]=j;
现在查看条件
x
p [j-1] j-1
p [i] p[i -1] !=
p [j] , this is what we talked about in situation (2),
p [i -1]!= matches
,因此我们从, but
转换为p[j-1]
,即i
。现在剩下的唯一没有解释的是测试
j
,当较短的后缀具有相同的边框时,将发生该测试。例如,您有一个模式 012345678
addbddcdd
计算
s[j] = j - i;
和if (s[j] == 0)
时,将设置f[i - 1]
。但是,当您为i = 4
计算s[7]
时,如果没有测试f[i-1]
,则将再次设置i = 1
。这意味着,如果在位置s[7]
不匹配,则将if (s[j] == 0)
向右移动(将6
与所占据的位置3
对齐)而不是bdd
(直到cdd
移至位置6
占据)。代码注释
void bmPreprocess1()
{
// initial condition, set f[m] = m+1;
int i=m, j=m+1;
f[i]=j;
// calculate f[i], s[j] from i = m to 0.
while (i>0)
{
// at this line, we know f[i], f[i+1], ... f[m].
while (j<=m && p[i-1]!=p[j-1]) // calculate the value of f[i-1] and save it to j-1
{
if (s[j]==0) s[j]=j-i; // if s[j] is not occupied, set it.
j=f[j]; // get the start position of the border of suffix p[j] ... p[m-1]
}
// assign j-1 to f[i-1]
i--; j--;
f[i]=j;
}
}
关于c - Boyer-Moore良好后缀的启发式方法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/19345263/