1

近似字符串匹配并不是一个陌生的问题。

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

在其 wiki 页面（近似字符串匹配）中，它说

蛮力方法是计算 T 的所有子串到 P（模式）的编辑距离，然后选择具有最小距离的子串。但是，该算法的运行时间为 O(m * n^3)，n 是 T 的长度，m 是 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 个部分？

这是否distance between two prefixes意味着我们需要进行distance多次更改才能使两个前缀（或字符串）相等？

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

4

1 回答 1

1

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

至于您的编辑：您需要查看，{"su", "sv"}因为更改"suv"为的最佳方法可能"svi"是将最后一个替换为v，i其成本将高于更改"su"为的成本"sv"。或者，最好的方法可能是更改"suv"为"sv"某种方式，然后添加一个i. 或者，最好的方法可能是先删除vfrom"suv"然后更改"su"为"svi". 在这种情况下，第一种方法被证明是最好的（或与其他选项一样好）。编辑距离确实是2，操作是把theu变成a v，把thev变成an i。

于 2012-05-28T22:53:08.993 回答