3

我想使用回溯来搜索允许可变长度匹配的长字符串中的所有子字符串——即允许最大给定数量的不匹配、插入和删除的匹配。我找不到任何有用的例子。我找到的最接近的是这里的这篇论文，但这非常复杂。任何人？

干杯，

马丁

4

3 回答 3

3

算法

下面的函数ff()使用递归（即回溯）来解决您的问题。基本思想是，在任何对 的调用开始时f()，我们都试图t将原始“needle”字符串的后缀s与“haystack”字符串的后缀匹配，同时只允许一定数量的每种类型的编辑操作。

// ss is the start of the haystack, used only for reporting the match endpoints.
void f(char* ss, char* s, char* t, int mm, int ins, int del) {
    while (*s && *s == *t) ++s, ++t;    // OK to always match longest segment
    if (!*t) printf("%d\n", s - ss);    // Matched; print endpoint of match
    if (mm && *s && *t) f(ss, s + 1, t + 1, mm - 1, ins, del);
    if (ins && *s) f(ss, s + 1, t, mm, ins - 1, del);
    if (del && *t) f(ss, s, t + 1, mm, ins, del - 1);
}

// Find all occurrences of t starting at any position in s, with at most
// mm mismatches, ins insertions and del deletions.
void ff(char* s, char* t, int mm, int ins, int del) {
    for (char* ss = s; *s; ++s) {
//      printf("Starting from offset %d...\n", s - ss);
        f(ss, s, t, mm, ins, del);
    }
}

示例调用：

ff("xxabcydef", "abcdefg", 1, 1, 1);

这输出：

9
9

因为有两种方法可以在“xxabcydef”中找到“abcdefg”，每种变化最多1个，并且这两种方法都在第9位结束：

Haystack: xxabcydef-
Needle:     abc-defg

其中有 1 个插入 (of y) 和 1 个删除 (of g)，并且

Haystack: xxabcyde-f
Needle:     abc-defg

其中有 1 个插入 (of y)、1 个删除 (of f) 和 1 个gto替换f。

支配关系

while为什么使用第3 行的循环在两个字符串的开头贪婪地匹配尽可能多的字符实际上是安全的，这可能并不明显。事实上，这可能会减少特定结束位置被报告为匹配的次数，但它永远不会导致结束位置被完全遗忘——因为我们通常只关心是否存在比赛在大海捞针的给定位置结束，如果没有这个while循环，算法总是会花费时间指数在针大小上，这似乎是双赢的。

由于支配关系，它可以保证工作。为了看到这一点，假设相反——它实际上是不安全的（即错过了一些匹配）。然后会有一些匹配，其中两个字符串中相等字符的初始段彼此不对齐，例如：

Haystack: abbbbc
Needle:   a-b-bc

但是，任何这样的匹配都可以通过将最左边的字符分流到间隙左侧的间隙后，转换为具有相同数量的每种类型的操作并在相同位置结束的另一个匹配：

Haystack: abbbbc
Needle:   ab--bc

如果您反复执行此操作，直到不再可能在不需要替换的情况下分流字符，您将获得一个匹配，其中两个字符串中相等字符的最大初始段相互对齐：

Haystack: abbbbc
Needle:   abb--c

我的算法会找到所有这样的匹配，因此它不会忽略任何匹配位置。

指数时间

与任何回溯程序一样，此函数将在某些输入上表现出指数减速。当然，可能是在您碰巧使用的输入上，这不会发生，并且它比 DP 算法的特定实现更快。

于 2011-09-27T08:53:50.787 回答
0

我将从Levenshtein 的距离算法开始，这是通过不匹配、插入和删除检查字符串相似性时的标准方法。

由于该算法使用自下而上的动态规划，您可能能够找到所有子字符串，而不必为每个潜在的子字符串执行算法。

于 2011-09-26T15:12:12.087 回答
0

我所知道的最好的算法是Gene Myers 的基于动态编程的近似字符串匹配的快速位向量算法。给定一个长度为 n 的要搜索的文本、一个长度为 m 的要搜索的模式字符串和最大不匹配/插入/删除数 k，这个算法需要时间 O(mn/w)，其中 w 是您计算机的字长（32或 64）。如果您对字符串算法了解很多，那么实际上存在一种算法，它需要与 k 无关的时间——长期以来，这似乎是一个不可能实现的目标。

我不知道上述算法的现有实现。如果你想要一个工具，agrep可能正是你所需要的。它使用了一个需要时间 O(mnk/w) 的早期算法，但它对于低 k 来说已经足够快了——在最坏的情况下，它比回溯搜索提前了几英里。

agrep基于Shift-Or（或“Bitap”）算法，这是一种非常聪明的动态规划算法，它设法将其状态表示为整数中的位，并通过二进制加法来完成大部分更新状态的工作，其中是使算法比更典型的实现提高 32 或 64 倍的原因。:) Myers 的算法也使用这个想法来获得它的 1/w 速度因子。

于 2011-09-26T20:58:56.403 回答