algorithm - 使用回溯的近似字符串匹配

Question

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

干杯，

马丁

Answer 1

算法

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

// 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 个插入(y)和 1 个删除(g)，以及

Haystack: xxabcyde-f
Needle:     abc-defg

有 1 次插入(y)、1 次删除(f)和 1 次 g 到 f 的替换。

支配关系

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

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

Haystack: abbbbc
Needle:   a-b-bc

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

Haystack: abbbbc
Needle:   ab--bc

如果您重复执行此操作，直到不再需要替换就无法分流字符，您将得到一个匹配，其中两个字符串中相同字符的最大初始段相互对齐:

Haystack: abbbbc
Needle:   abb--c

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

指数时间

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