c++ - 了解 Baeza-Yates Régnier 算法(多字符串匹配，从 Boyer-Moore 扩展而来)

Question

首先，如果我写了很多，请原谅，我试着总结一下我的研究，以便大家能够理解。

R。 Baeza-Yates 和 M. Regnier 于 1990 年发表了一种用于在二维 nn 文本中搜索二维 mm 模式的新算法。 The publication写得很好，对于像我这样的新手来说也很容易理解，算法是用伪代码描述的，我能够成功地实现它。

BYR 算法的一部分需要 Aho-Corasick 算法。这允许在字符串文本中搜索多个关键字的出现。然而，他们还表示，他们的这部分算法可以通过使用 Commentz-Walter 算法(基于 Boyer-Moore 而不是 Knuth-Morris-Pratt 算法)而不是 Aho-Corasick 算法来大大改进。他们唤起了 Commentz-Walter 算法的替代方案，这是他们自己开发的替代方案。这在 their previous publication 中进行了描述和解释。 (见第 4 章)。

这就是我的问题所在。正如我所说，该算法遍历文本并检查它是否包含关键字集中的单词。单词倒置放置在一棵树上。为了提高效率，当他知道找不到匹配项时，有时需要跳过一些字母。

要确定可以跳过的字符数，必须计算两个表d 和dd。那么，算法就很简单了:

The algorithm works as follows:

• We align the root of the trie with position m in the text, and we start matching the text from right to left following the corresponding path in the trie.
• If a match is found (final node), we output the index of the corresponding string.
• After a match or mismatch, we move the trie further in the text using the maximum of the shift associated to the current node (means dd), and the value of d[x], where x is the character in the text corresponding to the root of the trie.
• Start matching the trie again from right to left in the new position.

我的问题是我不知道如何计算 dd 函数。在他们的出版物中，R. Baeza-Yates 和 M. Regnier 提出了一个正式的定义:

pi 是关键字集合中的一个词，j 是这个词中一个字母的索引，所以 pi[j] 就像我之前展示的 trie 中的一个节点。节点中的数字表示 dd(node)。 L为单词个数，mi为单词pi中的字母个数。

他们没有给出关于这个函数的构造的指示。他们只推荐看the work of W. Rytter .本文档构建了一个类似于预期的功能，不同之处在于在这种情况下，只有一个关键字而不是一组。

dd(这里称为D)的定义如下:

可能会注意到与之前定义的相似之处，但我并不理解所有内容。

论文中给出了构造这个函数的伪代码，我已经实现了，这里用C++:

int pattern[] = { 1, 2, 3, 1 };  /* I use int instead of char, simpler */
const int n = sizeof(pattern) / 4;
int D[n];
int f[n];

int j = n;
int t = n + 1;

for (int k = 1; k <= n; k++){
    D[k-1] = 2 * n - k;
}

while (j > 0) {
    f[j-1] = t;
    while (t <= n) {
        if (pattern[j-1] != pattern[t-1]) {
            D[t-1] = min(D[t-1], n - j);
            t = f[t-1];
        }
        else {
            break;
        }
    }
    t = t - 1;
    j = j - 1;
}

int f1[n];
int q = t;
t = n + 1 - q;
int q1 = 1;
int j1 = 1;
int t1 = 0;


while (j1 <= t) {
    f1[j1 - 1] = t1;
    while (t1 >= 1) {
        if (pattern[j1 - 1] != pattern[t1 - 1]) {
            t1 = f1[t1 - 1];
        }
        else {
            break;
        }
    }
    t1 = t1 + 1;
    j1 = j1 + 1;
}
while (q < n) {
    for (int k = q1; k <= q; k++) {
        D[k - 1] = min(D[k - 1], n + q - k);
    }
    q1 = q + 1;
    q = q + t - f1[t - 1];
    t = f1[t - 1];
}

for (int i = 0; i < n; i++)
{
    cout << D[i] << " ";
}

它有效，但我不知道如何将它扩展为几个词，我不知道如何与 Baeza-Yates 和 Régnier 给出的 dd 的正式定义一致。我说这两个定义很相似，但不知道到什么程度。

我没有找到关于他们算法的任何其他信息，我不可能知道如何实现 dd 的构造，但我正在寻找可能理解并告诉我如何实现的人到达那里，向我解释 D 和 dd 的定义之间的联系。

Answer 1

我认为d[x]对应http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm中的坏字符规则而D对应同一篇文章中的Good Suffix规则。这意味着 d[x] 中的 x 不是树根中的字符，而是正在搜索的文本中与当前节点的子节点不匹配的第一个字符的值.

我觉得这个想法和 Boyer-Moore 是一样的。只要有匹配项，就沿着树移动，当出现不匹配项时，您会知道两件事:导致不匹配项的字符，以及目前已匹配的子字符串。独立地考虑这些事情，你可能会发现如果你沿着被搜索的文本移动 1,2,..k 位置你仍然没有匹配，因为在这些偏移处导致不匹配的字符仍然会导致不匹配，或者之前匹配的文本部分在这个偏移量处不匹配。因此，您可以跳到第一个未被任何一个值排除的偏移量。

实际上，这暗示了一种变体方案，其中 d 和 DD 提供的不是数字而是位掩码，并且您将两个位图放在一起并根据仍设置的第一个位的位置移动。据推测，这并不能为您节省足够的时间，值得额外的设置时间。