algorithm - 莱文斯坦距离 : Inferring the edit operations from the matrix

Question

我用 C++ 写了 Levenshtein 算法

如果我输入:
字符串 s:民主
字符串 t:共和党

我得到了填充的矩阵 D 并且可以在 D[10][8] = 8 中读取操作次数(Levenshtein 距离)
除了填充矩阵，我想构建最佳解决方案。必须如何看待这个解决方案？我没有想法。
请只写我如何必须寻找这个例子。

Answer 1

问题是
给定 Levenshtein 算法生成的矩阵，如何找到“ 的最优解 ”？
即我们如何找到字符串操作的精确序列:插入、删除和替换 [单个字母]，将“字符串”转换为“t 字符串”所必需的？

首先需要说明的是在许多情况下，有几个最佳解决方案 .虽然 Levenshtein 算法提供最少数量的操作(在民主/共和党示例中为 8 个)，但有许多序列(8 个操作)可以产生这种转换。

通过“解码”Levenshtein 矩阵，可以枚举所有此类最佳序列。
总体思路是最优解都遵循一条“路径”，从左上角到右下角 (或在另一个方向)，由此该路径上的矩阵单元格值要么保持不变，要么增加一(或在相反方向减少一)，从 0 开始，以对中的字符串的最佳操作次数结束问题(0 到 8 民主党/共和党案例)。当需要操作时，数字增加，当字符串中相应位置的字母相同时，数字保持不变。

很容易产生产生这样一条路径的算法(产生所有可能的路径稍微复杂一些)，并从这样的路径推导出操作的顺序。

这个寻路算法应该从右下角开始并向后工作。这种方法的原因是我们知道这样一个事实，即要成为最佳解决方案，它必须在这个角落结束，并且要在这个角落结束，它必须来自紧邻其左侧、紧邻上方的 3 个单元格之一它或立即对角线。通过在这三个单元格中选择一个满足我们“相同值或减一”要求的单元格，我们可以有效地选择最佳路径之一上的单元格。通过重复操作直到我们到达左上角(或者实际上直到我们到达一个值为 0 的单元格)，我们有效地在最佳路径上回溯了我们的方式。

以民主党人的例证 - 共和党人的例子

还应该注意的是，可以通过以下两种方式之一构建矩阵:水平或垂直使用“民主”。这不会改变 Levenshtein 距离的计算，也不会改变所需的操作列表；它只会改变我们解释矩阵的方式，例如在“路径”上水平移动意味着插入一个字符 [从 t 字符串] 或删除一个字符 [从 s 字符串] 取决于“字符串 s”是否是“水平的”或矩阵中的“垂直”。

我将使用以下矩阵。因此，约定是(仅在从左到右和/或从上到下的方向)

水平移动是 插入 来自“t 字符串”的字母

垂直移动是 删除 来自“字符串”的字母

对角线移动是:

a 无操作(各自位置的两个字母相同)；号码不变

替代 (各位置字母不同)；数量增加一。

s = "democrat", t="republican"的 Levenshtein 矩阵

      r  e  p  u  b  l  i  c  a  n
   0  1  2  3  4  5  6  7  8  9  10
d  1  1  2  3  4  5  6  7  8  9  10
e  2  2  1  2  3  4  5  6  7  8  9
m  3  3  2  2  3  4  5  6  7  8  9
o  4  4  3  3  3  4  5  6  7  8  9
c  5  5  4  4  4  4  5  6  6  7  8
r  6  5  5  5  5  5  5  6  7  7  8
a  7  6  6  6  6  6  6  6  7  7  8
t  8  7  7  7  7  7  7  7  7  8  8

任意我用来在几个可能的最佳路径中选择一个路径的方法大致描述如下:

Starting at the bottom-rightmost cell, and working our way backward toward 
the top left.

For each "backward" step, consider the 3 cells directly adjacent to the current
cell   (in the left, top or left+top directions)

   if the value in the diagonal cell (going up+left) is smaller or equal to the
      values found in the other two cells
   AND 
      if this is same or 1 minus the value of the current cell 
   then  "take the diagonal cell"
         if the value of the diagonal cell is one less than the current cell:
            Add a SUBSTITUTION operation (from the letters corresponding to
            the _current_ cell)
         otherwise: do not add an operation this was a no-operation.

   elseif the value in the cell to the left is smaller of equal to the value of
       the of the cell above current cell
   AND 
       if this value is same or 1 minus the value of the current cell 
   then "take the cell to left", and
        add an INSERTION of the letter corresponding to the cell
   else
       take the cell above, add
       Add a DELETION operation of the letter in 's string'

遵循这个非正式的伪代码，我们得到以下内容:

从右下角的“n”、“t”单元格开始。
选择 [对角线] "a", "a"单元格作为下一个目标，因为它小于其他两个(并且满足相同或 -1 条件)。
请注意，新单元格比当前单元格小 1
因此，第 8 步将“t”替换为“n”:democra 电话

继续“a”，“a”单元格，
选择 [对角线] "c", "r"单元格作为下一个目标...
请注意，新单元格与当前单元格的值相同 ==> 无需操作。

继续“c”，“r”单元格，
选择 [对角线] "i", "c"单元格作为下一个目标...
请注意，新单元格比当前单元格小 1
因此，第 7 步是将“r”替换为“c”: democ C 一个

继续“i”，“c”单元格，
选择 [对角线] "l", "o"单元格作为下一个目标...
请注意，新单元格比当前单元格小 1
因此，第 6 步是将“c”替换为“i”:演示 我能够

继续“l”、“o”单元格，
选择 [对角线] "b", "m"单元格作为下一个目标...
请注意，新单元格比当前单元格小 1
因此，第 5 步将“o”替换为“l”: dem L 我可以

继续“b”，“m”单元格，
选择 [对角线]"u"、"e"单元格作为下一个目标...
请注意，新单元格比当前单元格小 1
因此，第 4 步是将“m”替换为“b”: de 乙 许可

继续“u”、“e”单元格，
请注意“对角线”单元格不合格，因为“左”单元格小于它。
选择 [left] "p", "e"单元格作为下一个目的地...
因此，第 3 步是在“e”之后插入“u”: de U 布莱坎

继续“p”、“e”单元格，
再次“对角线”单元格不合格
选择 [left] "e", "e"单元格作为下一个目的地...
因此，第 2 步是在“e”之后插入“p”: de 电话 乌布利坎

继续“e”，“e”单元格，
选择 [对角线] "r", "d"单元格作为下一个目标...
请注意，新单元格与当前单元格的值相同 ==> 无需操作。

继续“r”、“d”单元格，
选择[对角线]“开始”单元格作为下一个目的地...
请注意，新单元格比当前单元格小 1
因此，第 1 步将“d”替换为“r”: R 共和党人

您已到达值为 0 的单元格:您的工作已完成!