使用回溯近似字符串匹配

Question

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

干杯，

马丁

Answer 1

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

由于该算法使用自下而上的动态编程，因此您可能能够找到所有子字符串，而无需对每个潜在子串执行算法。

Answer 2

我所知道的最好的算法是 A Fast Bit-基于动态规划的近似字符串匹配向量算法，作者：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 速度因子。

Answer 3

算法

下面的函数 ff() 使用递归（即回溯）来解决您的问题。基本思想是，在对 f() 的任何调用开始时，我们尝试将原始“needle”字符串的后缀 t 与后缀 匹配。 >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 个插入（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

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

Haystack: abbbbc
Needle:   abb--c

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

指数时间

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