algorithm - Levenshtein 距离，分别跟踪插入/删除/替换

Question

关于 Levenshtein distance 的维基百科文章说，在其 possible modifications部分，即“[w]e 可以分别存储插入、删除和替换的次数”。

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

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

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

           C     A     T     C     H  +-----+-----+-----+-----+-----+-----+  |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|  +-----+-----+-----+-----+-----+-----+

有人研究过这个算法吗？

Answer 1

对于目标单元格 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 放入新单元格中。

希望对您有所帮助。