string - 近似字符串匹配的具体算法代码

Question

Approximate string matching不是一个陌生的问题。

我正在学习并试图了解如何解决它。我什至现在都不想深入了解它，只想了解蛮力方式。

在它的维基页面(Approximate string matching)中，它说

A brute-force approach would be to compute the edit distance to P (the pattern) for all substrings of T, and then choose the substring with the minimum distance. However, this algorithm would have the running time O(m * n^3), n is the length of T, m is the length of P

好的。我通过以下方式理解此声明:

1. 我们找出 T 所有可能的子串
2. 我们计算每对字符串 {P, t1}, {P, t2}, ... 的编辑距离
3. 我们找出哪个子串与 P 的距离最短，这个子串就是答案。

我有以下问题:

一个。我可以使用两个 for 循环来获取所有可能的子字符串，这需要 O(n^2)。因此，当我尝试计算一个子字符串和模式的编辑距离时，是否需要 O(n*m)？为什么？

我究竟如何计算一对(一个子串和模式)的距离？我知道我可以插入、删除、替换，但谁能给我一个只计算一对的算法？

谢谢

---

编辑

好的，我应该使用 Levenshtein distance , 但我不太明白它的方法。

部分代码

for j from 1 to n
{
    for i from 1 to m
    {
      if s[i] = t[j] then  
        d[i, j] := d[i-1, j-1]       // no operation required
      else
        d[i, j] := minimum
                   (
                     d[i-1, j] + 1,  // a deletion
                     d[i, j-1] + 1,  // an insertion
                     d[i-1, j-1] + 1 // a substitution
                   )
    }
  }

因此，假设我现在正在比较 {"suv", "svi"}。

所以 'v' != 'i'，然后我必须看到另外三对:

1. {"su", "sv"}
2. {"suv", "sv"}
3. {"su", "svi"}

这部分怎么理解？为什么我需要看到这 3 个部分？

两个前缀之间的距离是否意味着我们需要距离的变化才能使两个前缀(或字符串)相等？

那么，让我们看一下{"su", "sv"}。我们可以看到{"su", "sv"}的距离是1，那么{"su", "sv"}怎么变成{"suv", "svi"} 只需加 1？我认为我们需要将“v”插入“su”，将“v”插入“sv”，然后将最后一个“i”替换为“v”，这涉及 3 个操作，对吗？

Answer 1

测量两个字符串之间编辑距离的标准方法称为 Levenshtein distance - 维基百科页面包含算法的伪代码。

至于您的编辑:您需要查看 {"su", "sv"} 因为可能是将 "suv" 更改为的最佳方法"svi"是将最后一个v替换为i，其代价是在改变"su"的代价之上 到 “sv”。或者，最好的方法可能是以某种方式将 "suv" 更改为 "sv"，然后添加一个 i。或者，最好的方法是先从 "suv" 中删除 v，然后将 "su" 更改为 “svi”。在这种情况下，第一种方法被证明是最好的(或与其他选项一样好)。编辑距离确实是2，操作就是把u变成v，把v变成i.