了解 Baeza-Yates Régnier 算法（多字符串匹配，从 Boyer-Moore 扩展）

Question

首先，如果我写了很多，请原谅，我试图总结我的研究，以便每个人都能理解。

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

BYR 算法的一部分需要 Aho-Corasick 算法。这允许在字符串文本中搜索多个关键字的出现。然而，他们也说他们的这部分算法可以通过使用 Aho-Corasick 而不是 Commentz-Walter 算法（基于 Boyer-Moore 而不是 Knuth-Morris-Pratt 算法）得到很大的改进。他们唤起了他们自己开发的 Commentz-Walter 算法的替代方案。这在他们之前的出版物中进行了描述和解释（见第 4 章）。

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

以确定可以被跳过，两个表中的字符数d，并dd必须被计算出来。那么，算法很简单：

该算法的工作原理如下：

• 我们将树的根与文本中的位置 m 对齐，然后沿着树中的相应路径从右到左开始匹配文本。
• 如果找到匹配项（最终节点），我们输出相应字符串的索引。
• 在匹配或不匹配之后，我们使用与当前节点关联的最大移位（表示 dd）和 d[x] 的值在文本中进一步移动特里树，其中 x 是文本中对应于树根。
• 在新位置从右到左再次开始匹配树。

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

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

他们没有给出关于这个函数的构造的说明。他们只推荐观看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] << " ";
}

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

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

Answer 1

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

我认为这个想法和博耶-摩尔是一样的。只要有匹配，您就沿着树移动，而当您有不匹配时，您知道两件事：导致不匹配的字符，以及迄今为止匹配的子字符串。独立地考虑这些事情中的每一个，您可能会发现，如果您沿着正在搜索的文本移动 1,2,..k 个位置，您仍然不会有匹配项，因为在这些偏移处，导致不匹配的字符仍然会导致不匹配，或者先前匹配的文本部分在此偏移量处将不匹配。因此，您可以跳到未被任一值排除的第一个偏移量。

实际上，这表明了一种变体方案，其中 d 和 DD 提供的不是数字，而是位掩码，并且您将两个位图结合在一起，并根据仍设置的第一位的位置进行移位。据推测，这并不足以为您节省足够多的额外设置时间。