5

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

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

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

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

特里

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

该算法的工作原理如下：

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

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

dd 函数

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

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

dd（这里称为 D）的定义如下：

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。_

4

1 回答 1

0

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

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

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

于 2014-06-28T05:32:05.650 回答