algorithm - 博耶-摩尔伽利尔规则

Question

我正在实现 Boyer-Moore Algorithm当我了解到 Galil Rule 时在 Python 中进行子字符串搜索.我在网上四处寻找加利尔规则，但除了几句话外什么也没找到，而且我无法访问原始论文。如何将其实现到我当前的算法中？

i = 0
while i < (N - M + 1):
    skip = 0
    for j in reversed(range(0, M)):
        if pattern[j] != text[i + j]:
            skip = max(1, j - offsets[text[i+j]])
            break
    if skip == 0:
        return i
    i += skip
return -1

注意事项:

• offsets[c] = -1 如果 c 不在模式中
• offsets[c] = 模式中 c 的最后一个索引

例子:啊啊啊啊

• 偏移[a] = 2
• 偏移量[b] = 5
• 偏移量[c] = 4
• 偏移[d] = -1

我发现的几句话说要跟踪我的内循环中第一次不匹配发生的时间(j，如果内循环中的 if 语句为真)和我开始比较的位置(i + j，在我的例子中)。我理解直觉，我已经检查了它们之间的所有索引，所以我不必再次进行这些比较。我只是不明白如何将这些点联系起来并得出一个实现。

Answer 1

Galil 规则是关于利用模式中的周期性来减少比较。假设你有一个模式 abcabcab .它是周期性的，周期最小abc .一般来说，一个模式 P如果有一个字符串 U 是周期性的这样 P是 UUUUU... 的前缀. (在上面的示例中，abcabcab 显然是重复字符串 abc = U 的前缀。)我们将最短的此类字符串称为 P 的句点。 .令该期间的长度为 k (在上面的例子中 k = 3 自 U = abc )。

首先，请记住 Galil 规则仅在您发现 P 出现后应用在文中。当你这样做时，Galil 规则说你可以移动 k (模式的周期性)，你只需要比较最后一个 k现在移位模式的字符以确定是否存在匹配项。

这是一个例子:

P = ababa
T = bababababab
U = ab
k = 2

第一次出现:b[ababa]babab .现在你可以按 k = 2 移动了你只需要检查模式的最后两个字符:

T = bababa[ba]bab
P =    aba[ba]       // Only need to compare chars inside brackets for next match.

其余P 必须 匹配，因为 P 是周期性的并且您将它移动了它的周期 k 来自现有的匹配项(这很重要)，这样重复的部分就会很好地排列起来。

如果您找到了另一个匹配项，只需重复即可。但是，如果发现不匹配，则恢复到标准的 Boyer-Moore 算法，直到找到另一个匹配。请记住，只有当您找到匹配项并且您移动了 k 时，您才能使用 Galil 规则。 (否则不能保证模式与前一次匹配)。

现在，您可能想知道，如何确定 k对于给定的模式 P .您需要计算后缀数组 N首先，哪里N[i]将是前缀的最长公共(public)后缀的长度 P[0, i]和 P . (您可以通过使用 Z 算法计算 Z 的反向上的前缀数组 P 来计算后缀数组，例如，如 here 所述。)获得后缀数组后, 你可以轻松找到 k因为它将是最小的k > 0这样 N[m - k - 1] == m - k (其中 m = |P| )。

例如:

P = ababa
m = 5
N = [1, 0, 3, 0, 5]
k = 2  because  N[m - k - 1] == N[5 - 2 - 1] == N[2] == 3 == 5 - k