gpt4 book ai didi

algorithm - Boyer Moore算法的理解和例子?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:14:37 26 4
gpt4 key购买 nike

我在理解 Boyer Moore 字符串搜索算法时遇到问题。

我正在关注以下文档。 Link

我无法弄清楚 delta1 和 delta2 在这里的真正含义是什么,以及他们如何应用它来查找字符串搜索算法。语言看起来有点模糊..

如果有人能帮助我理解这一点,那将非常有帮助。

或者,如果您知道任何其他易于理解的链接或文档,请分享。

提前致谢。

最佳答案

Boyer-Moore 背后的见解是,如果您开始在以模式中的last 字符开头的字符串中搜索模式,则当遇到不匹配时,您可以将搜索向前跳转多个字符.

假设我们的模式 p 是字符序列 p1, p2, ..., pn我们正在搜索字符串 s,当前与 p 对齐,以便 pn 位于 i 中的索引 >s.

例如:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p = AT THAT
i = ^

B-M 论文提出了以下观察结果:

(1) 如果我们尝试匹配一个不在 p 中的字符,那么我们可以向前跳转 n 个字符:

'F' 不在 p 中,因此我们前进 n 个字符:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p = AT THAT
i = ^

(2) 如果我们尝试从 p 的末尾匹配一个最后位置为 k 的字符,那么我们可以向前跳转 k 个字符:

' 在 p 中的最后位置是从末尾算起 4,因此我们前进 4 个字符:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p = AT THAT
i = ^

现在我们从 i 开始向后扫描,直到我们成功或遇到不匹配。(3a) 如果不匹配从 p 开始出现 k 个字符并且不匹配的字符不在 p 中,那么我们可以前进(在至少)k 个字符。

'L' 不在 p 中并且与 p6 不匹配,因此我们可以(至少)前进 6 个字符:

s = WHICH FINALLY HALTS.  AT THAT POINT...
p = AT THAT
i = ^

然而,我们实际上可以做得比这更好。(3b) 因为我们知道在旧的 i 中我们已经匹配了一些字符(在本例中为 1)。如果匹配的字符不匹配p的开头,那么我们实际上可以向前跳多一点(这个额外的距离在论文中称为'delta2'):

s = WHICH FINALLY HALTS.  AT THAT POINT...
p = AT THAT
i = ^

此时,观察 (2) 再次适用,给出

s = WHICH FINALLY HALTS.  AT THAT POINT...
p = AT THAT
i = ^

宾果游戏!我们完成了。

关于algorithm - Boyer Moore算法的理解和例子?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6207819/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com