无法遵循最小编辑距离背后的直觉

Question

所以我刚开始阅读 MED，但我完全无法理解它。假设我必须将“WATER”转换为“ATERW”现在我可以替换：

W->A, A->T, T->E, E->R, R->W

因此总成本 = 2+2+2+2+2 =10（所有替换）

然而我知道这是不正确的，它应该是这样的

WATER-
-ATERW

因此这里的总成本= 1 + 1 = 2（删除和插入）但是我的问题是程序如何知道它不应该匹配'W'->'A'，而是删除'W'和匹配'ATER'两个字符串？如何将直觉/逻辑灌输到程序中？

Answer 1

首先，您应该检查有关 Levenshtein 距离的维基百科页面：https://en.wikipedia.org/wiki/Levenshtein_distance

它就像编辑距离一样，只是编辑成本不同。

正如您所看到的，要解决这个问题，您必须构建一个矩阵（这是一种动态规划方法）。行代表源单词，列代表目标单词。

首先用基本情况初始化矩阵：

现在您有了第一行和第一列。

  _ A T E R W
_ 0 1 2 3 4 5
W 1 ? ? ? ? ?
A 2 ? ? ? ? ?
T 3 ? ? ? ? ?
E 4 ? ? ? ? ?
R 5 ? ? ? ? ?

这个想法是逐个单元地填充矩阵。第一个填充的单元格是第二行第二列的单元格 (2,2)。它对应于源单词（即WATER）的字母W，以及目标单词（ATERW）的字母A。

让我们看一下周围的值，然后为每个值添加编辑成本。然后我们将选择最小值。对于插入（左侧单元格）或删除（上部单元格），编辑成本始终为 1。对于替换（左上角单元格），如果字母不同，则编辑成本为 1，否则为 0。

我们有：

现在选择最小值：1（替换）。单元格 2,2 现在值为 1。

  _ A T E R W
_ 0 1 2 3 4 5
W 1 1 ? ? ? ?
A 2 ? ? ? ? ?
T 3 ? ? ? ? ?
E 4 ? ? ? ? ?
R 5 ? ? ? ? ?

现在让我们对单元格 2,3 执行相同的操作。它对应于源词的后面的W（即WATER），以及目标词的字母T（ATERW）。

我们有：

现在选择最小值：2（插入或替换）。单元格 2,3 现在为值 2。

这意味着将W转换为AT的成本是2。

  _ A T E R W
_ 0 1 2 3 4 5
W 1 1 2 ? ? ?
A 2 ? ? ? ? ?
T 3 ? ? ? ? ?
E 4 ? ? ? ? ?
R 5 ? ? ? ? ?

正如您所看到的，我们使用之前的计算（单元格 2,2 中的值）来填充当前单元格 (2,3)。这就是动态规划的思想。

重复直到矩阵被填满。它应该看起来像这样：

  _ A T E R W
_ 0 1 2 3 4 5
W 1 1 2 3 4 4
A 2 1 2 3 4 5
T 3 2 1 2 3 4
E 4 3 2 1 2 3
R 5 4 3 2 1 2

看一下最后一个单元格 (6,6)：值为 2。它对应于将“WATER”转换为“ATERW”的成本。

为了恢复所执行的编辑操作的顺序，您可以使用反向指针表。对于给定单元格，每行给出您从中选取最小值的单元格。

2,2 1,1
2,3 2,2
2,4 2,3
2,5 2,4
2,6 1,5
3,2 2,1
...
6,5 5,4
6,6 6,5

现在您可以向后解析表并构建路径，即 (6,6) -> (6,5) -> (5,4)...