string - 瓦格纳-费歇尔算法

Question

我正在尝试了解用于查找字符串之间距离的 Wagner–Fischer 算法。我正在以下链接中查看它的伪代码:http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm

int EditDistance(char s[1..m], char t[1..n])
   // For all i and j, d[i,j] will hold the Levenshtein distance between
   // the first i characters of s and the first j characters of t.
   // Note that d has (m+1)  x(n+1) values.
   let d be a 2-d array of int with dimensions [0..m, 0..n]

   for i in [0..m]
     d[i, 0] ← i // the distance of any first string to an empty second string
   for j in [0..n]
     d[0, j] ← j // the distance of any second string to an empty first string

   for j in [1..n]
     for i in [1..m]
       if s[i] = t[j] then  
         d[i, j] ← d[i-1, j-1]       // no operation required
       else
         d[i, j] ← minimum of
                    (
                      d[i-1, j] + 1,  // a deletion
                      d[i, j-1] + 1,  // an insertion
                      d[i-1, j-1] + 1 // a substitution
                    )

   return d[m,n]

实际上我明白了算法的要点并直观地理解了它，因为对我来说并不明显为什么 d[i-1, j] + 1, d[i, j-1] + 1 和 d[i -1, j-1] + 1 视为删除、插入和替换。如果有人以更详细的方式解释实现的细微差别，那就太好了。

Answer 1

我创建了一个 gist它打印出操作顺序以及每个步骤试图解决的目标，这应该补充我对 Fischer-Wagner 算法的解释。

为了能够理解 Fischer-Wagner 算法，您必须记住它属于 dynamic programming 系列算法。这意味着它将计算更大问题的部分解决方案，存储部分解决方案并将部分计算的结果用于下一次计算。

那么这对 Fisher-Wagner 算法意味着什么？在这种情况下，这意味着距离矩阵 d 的每个元素都包含使您从当前字符串 A 到另一个字符串 B 的最佳可能操作轨迹。这个解释仍然有点抽象，所以让我解释一下我的意思通过一个例子来引导你。

假设您要使用 Fischer-Wagner 算法计算两个字符串“ABV”和“FV”的 Levensthein 距离。然后您的距离矩阵将如下所示:

+-----+---+---+---+---+
|     |j->| 0 | 1 | 2 |
+-----+---+---+---+---+
|   i |   | # | F | V |
+-----+---+---+---+---+
|   0 | # |   |   |   |
|   1 | A |   |   |   |
|   2 | B |   |   |   |
|   3 | C |   |   |   |
+-----+---+---+---+---+

该表的第一行/列命名距离矩阵的索引，第二个命名字符串的字符。 '#' 是空字符串(即长度为零的字符串)。

此距离矩阵的每个元素都标记了一个您要解决的子问题。例如，条目 [i=0, j=2] 包含从空字符串 ""到 "FV"的最短距离条目 [i=2, j=1] 包含问题“AB”=>“F”的最短距离。

让我们将算法快进到子问题 [i=2, j=2]，即如何从“AB”到“FV”。在这种情况下，距离矩阵如下所示。

+-----+---+---+---+---+
|     |j->| 0 | 1 | 2 |
+-----+---+---+---+---+
|   i |   | # | F | V |
+-----+---+---+---+---+
|   0 | # | 0 | 1 | 2 |
|   1 | A | 1 | 1 | 2 |
|   2 | B | 2 | 2 |   |
|   3 | C | 3 | 3 |   |
+-----+---+---+---+---+ 

“B”和“V”不相等，这意味着我们需要执行以下三种操作之一才能使它们相等:

1. 删除“B”。我们取 d[i=1, j=2] 以上单元格的成本，因为我们知道这个单元格是从 "A"=> "FV”。然而，我们的问题是来自“AB”=>“FV”，而不是来自“A”=>“FV。我们确实知道我们可以通过应用单元格 d[i=1, j=2] 的操作将“A”替换为“FV”(我们之前解决了这个子问题)，这给我们留下了一个字符串“FVB”，成本为 2。然后我们删除了“B”(“FVB"=> "FV")，我们就完成了。这个操作的成本是 2+1。
2. 插入“V”。类似于删除“B”，只是我们取左边的值 d[i=2, j=1] 因为我们知道这是从“AB”得到的最便宜的操作序列"=>"F"。由于我们的问题是从“AB”=>“FV”得到，我们只需要加上插入“V”的代价和我们完了。
3. 用“V”替换“B”。与之前的案例类似。我们知道 d[i=1, j=1] 包含改变“A”=>“F”的最便宜的操作序列。应用此操作将我们的问题更改为“FB”=>“FV”，可以通过将“B”替换为“< em>F”。

在考虑了这 3 个选项后，我们选择了成本最低的一个，即将“B”替换为“F”(1+1)。

以这种方式解决所有子问题后，输出将产生最终结果，即与“ABC”的最小编辑距离 => “FV”。