3

我试图了解 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被认为是删除、插入和替换。如果有人以更详细的方式解释实现的细微差别，那就太好了。

4

2 回答 2

9

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

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

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

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

+-----+---+---+---+---+
|     |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]（我们之前解决了这个子问题），这给我们留下了一个字符串“ 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 ”替换为“ F ”来解决。

在考虑了这三个选项后，我们选择了最便宜的一个，将“ B ”替换为“ F ”（1+1）。

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

于 2016-11-23T13:58:22.370 回答
2

请注意，假设保留在 columns 的字符串是恒定的，我们需要找到保留在 rows 的字符串的编辑距离。例如看这个 在此处输入图像描述

在这里，我们正在尝试计算 AVERY 的编辑距离！所以现在，子结构 DP[i][j]=DP[i-1][j-1] (如果 G[j]==A[i])

注意：G 代表 GARVEY，A 代表 AVERY

因为如果我们可以在 k 个操作中解决 G[j-1] 和 A[i-1] 的编辑距离，我们可以解决 G[j] 和 A[i] 操作（最后一个字符不需要操作）

否则

DP[i][j]= 最少关注

DP[i-1][j]+1 （见我们只能从行字符串中删除（要计算其编辑距离！） DP[i-1][j] 表示字符串 G[1...j ] 和 A[1...i-1]！看到字符 A[i] 被删除了吗？？）

DP[i][j-1]+1（看这不是删除！！我们所做的是在第 i+1 个位置添加一个字符！因此它等于 G[j]（我们可以添加任何字符))

DP[i-1][j-1]+1（我想这很容易，现在第 i 个和第 j 个字符不一样，所以我们所做的就是将第 A[i] 个字符更改为第 G[j] 个字符)

随时提出疑问:)

于 2015-06-12T04:53:09.350 回答