goo*_*ing 17 c algorithm boyer-moore
我理解不良角色启发式的工作方式.当您找到不匹配的字母时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对我来说没有意义......有人可以为此任务编写尽可能简单的伪代码吗？还是以某种方式解释？
CS *_*Pei 11
首先,我将使用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个字符.
情况2
让我们看另一个例子
leading TEXT cXXXcXXXbXXXcXXX rest of the TEXT
cXXXXcXXXbXXXcXXX
^
| mismatch happens here
我们可以在这里换4或8或更多？显然,如果我们移动8或更多,我们将错过将模式与文本匹配的机会.所以在这种情况下我们只能向右移4个字符.
那么这两种情况有什么区别呢？
不同之处在于,在第一种情况下,不匹配的字符c加上良好的后缀XXX,即cXXX与XXX之前的字符相加的下一个(从右边开始计数)匹配.在第二种情况下,cXXX与下一场比赛(从右边开始计数)加上该比赛前的角色不同.
因此,对于任何给定的GOOD SUFFIX(让我们称之为XXX),我们需要弄清楚这两种情况的转变,(1)c在GOOD SUFFIX加GOOD SUFFIX之前的角色(让我们称之为),在模式中也是匹配的下一个(从右边算起)匹配好的后缀+前面的字符,(2)字符加上GOOD 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]s i < k < m,这意味着从位置i开始的后缀的最宽边界j.我们希望找到f[i-1]基于f[i].
例如,对于模式aabbccaacc,在postion 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不是边界.
我们知道宽度> = 1的任何边界bccaacc都必须b加上从positin开始的后缀边框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]对p[j-1],他们是不相等的,这是字符串的结尾.然后f[3]只有零长度边界,使其等于10.
从更广泛的意义上描述过程
因此,f[i] = j意味着这样的事情,
Position: 012345 i-1 i j - 1 j m
pattern: abcdef ... @ x ... ? x ... $
如果字符@其中位置i - 1是相同的字符?在位置j - 1,我们知道
f[i - 1] = j - 1;,或者--i; --j; f[i] = j;.边界是@x ... $从位置开始的后缀j-1.
但如果@位置i - 1上的角色?与位置上的角色不同j - 1,我们必须继续向右搜索.我们知道两个事实:(1)我们现在知道边界宽度必须小于从位置开始的边界宽度j,即小于x...$.其次,边界必须以@...字符开头并以字符结束,$否则它可能是空的.
基于这两个事实,我们继续在子字符串x ... $(从位置j到m)内搜索边界开头x.然后下一个边界应该j等于 f[j];,即j = f[j];.然后我们将字符@与之前的字符进行比较x,即at j-1.如果它们相等,我们发现边界,如果没有,则继续该过程直到j> m.此过程由以下代码显示,
while (j<=m && p[i-1]!=p[j-1])
{
j=f[j];
}
i--; j--;
f[i]=j;
现在看条件p[i -1] !=P [J-1] , this is what we talked about in situation (2),P [I] matchesP [J] , butP [I] - 1]!= p[j-1],所以我们从转变i到j,那就是s[j] = j - i;.
现在唯一没有解释的是if (s[j] == 0)当较短的后缀具有相同的边界时将发生的测试.例如,你有一个模式
012345678
addbddcdd
当你计算f[i - 1]和i = 4,你将设置s[7].但是当你计算f[i-1]时i = 1,s[7]如果没有测试,你将再次设置if (s[j] == 0).这意味着,如果你在的位置偏移6,你转移3到右侧(对齐bdd的位置cdd占用)不6(不转移,直到add到位置cdd占用).
代码的评论
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;
}
}