2

维基百科关于Levenshtein 距离的文章在其可能的修改部分中说，“[w]e 可以分别存储插入、删除和替换的数量”。

这是怎么做到的？我创建了文章中概述的基于矩阵的动态编程解决方案的实现，其中矩阵的每个单元格都有一个单独的删除/插入/替换值，但对于我的生活，我似乎无法解决逻辑。

直观地说，如果我发现需要在同一步骤中进行删除和插入，那么这些应该变成替代。

为了使我想要完全清楚，这是源字符串“mat”和目标字符串“catch”的示例矩阵。我希望这需要一次替换（即，将“m”更改为“c”）和两次插入（即附加“ch”）。每个单元格都是“删除/插入/替换”。

           抓住
  +-----+-----+-----+------+-----+-----+
  |D/I/S|0/1/0|0/2/0|0/3/0|0/4/0|0/5/0|
  +-----+-----+-----+------+-----+-----+
M |1/0/0|0/0/1|0/1/1|0/2/1|0/3/1|0/4/1|
  +-----+-----+-----+------+-----+-----+
A |2/0/0|1/0/1|0/0/1|0/1/1|0/2/1|0/3/1|
  +-----+-----+-----+------+-----+-----+
T |3/0/0|2/0/1|1/0/1|0/0/1|0/1/1|0/2/1|
  +-----+-----+-----+------+-----+-----+

有人研究过这个算法吗？

4

1 回答 1

4

对于目标细胞 x，我们需要找到以下的最小值：

this + substitution | this + deletion
--------------------+----------------
this + insertion    |       x

从左上角开始是我们还没有处理任何一个值，所以我们必须同时处理这两个值，因此它是一个替换。

从左到右是我们还没有处理目标值的时候，所以它是插入。

从顶部是当我们还没有处理源值时，所以它是删除。

要单独存储这些值，您需要一个 3D 数组：

array[targetSize+1][inputSize+1][3]

然后，对于前面 3 个单元格中的每一个，添加 1 个替换、删除或插入（如上所示），然后根据替换、删除和插入的数量计算总成本，并找到 3 个成本中的最小值。然后将给出最小值的单元格中的值复制到当前单元格（添加了 1 操作）。

因此对于：

0/1/0|0/2/0
-----+-----
0/0/1|  x

让我们假设每个操作的成本为 1。

我们计算：
0/1/0+ 1 替换 = 0/1/1，成本 = 2
0/0/1+ 1 插入 = 0/1/1，成本 = 2
0/2/0+ 1 删除 = 1/2/0，成本 = 3

然后我们选择成本 2 中的任何一个并将其0/1/1放入新单元格中。

我希望这会有所帮助。

于 2013-10-03T20:24:05.997 回答