33

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

我正在关注以下文档。关联

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

如果有人可以帮助我理解这一点，那将非常有帮助。

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

提前致谢。

4

2 回答 2

117

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

假设我们的模式p是字符序列p1, p2, ...，pn并且我们正在搜索一个字符串s，当前p对齐，因此它pn位于索引iin s。

例如：

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

BM 论文提出以下意见：

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

'F' 不在 中p，因此我们推进n字符：

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

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

' 的最后一个位置p是从末尾开始的 4，因此我们提前 4 个字符：

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

现在我们向后扫描，i直到我们成功或遇到不匹配。(3a) 如果不匹配k的字符从开头发生p并且不匹配的字符不在 中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 =                             ^

和宾果游戏！我们完成了。

于 2011-06-02T02:25:30.697 回答
49

该算法基于一个简单的原理。假设我正在尝试匹配长度的子字符串m。我将首先查看 index 处的字符m。如果该字符不在我的字符串中，我知道我想要的子字符串不能以 indices 的字符开头1, 2, ... , m。

如果该字符在我的字符串中，我会假设它在我的字符串中的最后一个位置。然后我会跳回来并开始尝试从那个可能的起始位置匹配我的字符串。这条信息是我的第一个表。

一旦我从子字符串的开头开始匹配，当我发现不匹配时，我不能从头开始。我可能会部分参加从不同点开始的比赛。例如，如果我试图匹配成功 match, anand，意识到以下不是 a ，但我刚刚匹配了，所以我应该跳回尝试匹配我的子字符串中的第三个字符。这个，“如果我在匹配 x 个字符后失败，我可能在匹配的第 y 个字符上”信息存储在第二个表中。ananandananadan

请注意，当我无法匹配第二张桌子时，我知道我可能会根据我刚刚匹配的内容在比赛中走多远。第一个表根据我刚刚看到的我未能匹配的角色知道我可能回溯多远。您想使用这两条信息中更悲观的一条。

考虑到这一点，算法的工作原理如下：

start at beginning of string
start at beginning of match
while not at the end of the string:
    if match_position is 0:
        Jump ahead m characters
        Look at character, jump back based on table 1
        If match the first character:
            advance match position
        advance string position
    else if I match:
        if I reached the end of the match:
           FOUND MATCH - return
        else:
           advance string position and match position.
    else:
        pos1 = table1[ character I failed to match ]
        pos2 = table2[ how far into the match I am ]
        if pos1 < pos2:
            jump back pos1 in string
            set match position at beginning
        else:
            set match position to pos2
FAILED TO MATCH
于 2011-06-01T23:36:49.823 回答