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

Question

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

欢呼,马丁

Answer 1

算法

下面的函数ff()使用递归(即回溯)来解决您的问题。基本思想是，在任何对f()的调用开始时，我们试图将原始"针"字符串的后缀t与"干草堆"字符串的后缀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("%dn", 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算法的特定实现更快。

Answer 2

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

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

Answer 3

我所知道的最好的算法是Gene Myers基于动态规划的近似字符串匹配的快速位向量算法。给定要搜索的文本长度为n，要搜索的模式字符串长度为m，最大不匹配/插入/删除次数为k，此算法需要时间O(mn/w)，其中w是计算机的字长(32或64)。如果你对字符串上的算法了解很多，你就会觉得存在一个与k无关的时间算法是非常不可思议的——在很长一段时间里，这似乎是一个不可能实现的目标。

我不知道上述算法的现有实现。如果您需要一个工具，agrep可能正是您所需要的。它使用较早的算法，耗时0 (mnk/w)，但在最坏的情况下，它已经足够快，可以比回溯搜索提前k英里。

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