Wagner-Fischer算法

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

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

为了能够理解Fischer-Wagner算法,您必须记住它属于动态编程 算法系列.这意味着它将计算更大问题的部分解决方案,存储部分解决方案并使用部分计算的结果进行下一次计算.

那么这对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的操作将" A " 替换为" FV "[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 " 来解决.

在考虑了这三个选项之后,我们选择最便宜的一个,用" F " 代替" B "(1 + 1).

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

Answer 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] 个字符）

有疑问请尽管问:)