最小编辑距离重建
我知道在堆栈上和在线上都可以找到类似的答案，但是我觉得我缺少了一些东西。给定下面的代码，我们需要重建导致最小编辑距离的事件序列。对于下面的代码，我们需要编写一个输出函数：
Equal, L, L
Delete, E
Equal, A, A
Substitute, D, S
Insert, T
编辑：使用我的（部分正确的）解决方案更新了代码
这是代码，还有我的部分解决方案。例如，它可以给我（“ lead”->“ last”），但不适用于下面的示例（“ hint”->“
isnt”）。我怀疑这是因为第一个字符相等，这使我的代码无效。正确方向上的任何提示或指示都将很棒！
def printMatrix(M):
for row in M:
print row
print
def med(s, t):
k = len(s) + 1
l = len(t) + 1
M = [[0 for i in range(k)] for j in range(l)]
MTrace = [["" for i in range(k)] for j in range(l)]
M[0][0] = 0
for i in xrange(0, k):
M[i][0] = i
MTrace[i][0] = s[i-1]
for j in xrange(0, l):
M[0][j] = j
MTrace[0][j] = t[j-1]
MTrace[0][0] = "DONE"
for i in xrange(1, k):
for j in xrange(1, l):
sub = 1
sub_op = "sub"
if s[i-1] == t[j-1]:
# equality
sub = 0
sub_op = "eq"
# deletion
min_value = M[i-1][j] + 1
op = "del"
if min_value > M[i][j-1] + 1:
# insertion
min_value = M[i][j-1] + 1
op = "ins"
if min_value > M[i-1][j-1] + sub:
# substitution
min_value = M[i-1][j-1] + sub
op = sub_op
M[i][j] = min_value
MTrace[i][j] = op
print "final Matrix"
printMatrix(M)
printMatrix(MTrace)
############ MY PARTIAL SOLUTION
def array_append(array,x,y):
ops_string = MTrace[x][y]
if ops_string == 'ins':
array.append(("Insert",MTrace[0][y]))
elif ops_string == 'sub':
array.append(("Substitute",MTrace[x][0],MTrace[0][y]))
elif ops_string == 'eq':
array.append(("Equal",MTrace[x][0],MTrace[0][y]))
elif ops_string == 'del':
array.append(("Delete",MTrace[x][0]))
i = len(s)
j = len(t)
ops_array = []
base = M[i][j]
array_append(ops_array,i,j)
while MTrace[i][j] != "DONE":
base = M[i][j]
local_min = min(M[i][j-1],M[i-1][j],M[i-1][j-1])
if base == local_min:
i = i - 1
j = j - 1
array_append(ops_array,i,j)
elif M[i][j-1] < M[i-1][j]:
j = j -1
array_append(ops_array,i,j)
elif M[i-1][j] < M[i][j-1]:
i = i - 1
array_append(ops_array,i,j)
else:
i = i - 1
j = j - 1
array_append(ops_array,i,j)
print ops_array
#########
return M[k-1][l-1]
print med('lead', 'last')
-
我认为在这种情况下，更深入地了解算法很重要。除了向您提供一些伪代码外，我还将向您介绍该算法的基本步骤，并向您展示所需的数据如何在最终的矩阵中“编码”。当然，如果您不需要滚动自己的算法，那么您显然应该使用其他人的算法，如MattH建议的那样！
大图景
在我看来，这类似于Wagner-
Fischer算法的实现。基本思想是计算“附近”前缀之间的距离，取最小值，然后从中计算出当前字符串对的距离。例如，假设您有两个字符串'i'和'h'。让我们沿着矩阵的垂直和水平轴进行布局，如下所示：_ h _ 0 1 i 1 1此处，
'_'表示空字符串，矩阵中的每个单元格对应于一个将输入（''或'i'）输入到输出（''或'h'）的编辑序列。空字符串到长度为L的任何字符串的距离为L（需要插入L个字符）。从任何长度为L的字符串到空字符串的距离也为L（需要删除L个字符）。这覆盖了第一行和第一列中的值，这些值只是递增。
从那里，您可以通过从上，左和左上值中取最小值，然后加上一个值来计算任何位置的值，或者，如果字符串中该点的字母相同，则取上一个值-
left值不变。对于上(1, 1)表中的at值，最小值是0at(0, 0)，所以at值(1, 1)是1，这是从'i'到的最小编辑距离'h'（一次替换）。因此，通常，最小编辑距离始终位于矩阵的右下角。现在，与做比较
is，再做一次hi。这里再一次，矩阵中的每个单元对应于取得输入（编辑序列''，'i'或'is'）到输出（''，'h'，或'hi'）。_ h i _ 0 1 2 i 1 1 # s 2 # #我们首先放大矩阵，将其
#用作尚不知道的值的占位符，然后通过递增来扩展第一行和第一列。这样，我们就可以开始计算#上面标记位置的结果。让我们从(2, 1)（行（列），即行主要表示法）开始。在上，左上和左值中，最小值为1。表中对应的字母不同-s和h-因此我们在该最小值上加一个以获得2并继续。_ h i _ 0 1 2 i 1 1 # s 2 2 #让我们继续到的值
(1, 2)。现在情况有所不同，因为表中的对应字母是相同的-它们都是i。这意味着我们可以选择在左上角的单元格中取值
而无需添加一个
。这里的指导直觉是，我们不必增加计数，因为在此位置将相同的字母添加到两个字符串中。而且由于两根弦的长度都增加了一个，所以我们沿对角线移动。_ h i _ 0 1 2 i 1 1 1 s 2 2 #在最后一个空单元格之后，一切恢复正常。对应的字母是
s和i，因此我们再次取最小值并加一个，得到2：_ h i _ 0 1 2 i 1 1 1 s 2 2 2如果我们继续此过程并以
is和hi-开头的两个较长单词isnt（忽略标点符号）和hint：_ h i n t _ 0 1 2 3 4 i 1 1 1 2 3 s 2 2 2 2 3 n 3 3 3 2 3 t 4 4 4 3 2这个矩阵稍微复杂一点，但是这里的最终最小编辑距离仍然是
2，因为这两个字符串的最后两个字母相同。方便！重新创建编辑顺序
那么我们如何从该表中提取编辑类型呢？关键是要意识到桌子上的移动对应于特定的编辑类型。因此，例如，从
(0, 0)到的向右移动(0, 1)会将我们从_ -> _，不需要编辑，到_ -> h，需要一个编辑，插入。同样，从(0, 0)到的向下移动(1, 0)会将我们从_ -> _，不需要任何编辑，到i -> _，需要一个编辑，删除。最后，从(0, 0)到的对角线运动(1, 1)使我们从_ -> _，不需要任何编辑，到i -> h，需要一个编辑，一次替换。因此，现在我们要做的就是反转步骤，从上，左和左上单元格中追踪局部最小值回到原点，请
(0, 0)记住，如果当前值与最小值相同，则我们必须移至左上角的单元格，因为这是唯一一种不会增加编辑距离的移动。这是您可以采取的步骤的详细说明。从完成的矩阵的右下角开始，重复以下操作，直到到达左上角：
- 查看左上方的相邻单元格。如果不存在，请转到步骤3。如果该单元格确实存在，请记下该位置存储的值。
- 左上单元格中的值等于当前单元格中的值吗？如果是这样，请执行以下操作：
- 记录一个空操作（即
Equal）。在这种情况下，不需要编辑，因为此位置的字符相同。 - 更新当前单元格，向上和向左移动。
- 返回步骤1。
- 记录一个空操作（即
- 这里有很多分支：
- 如果左侧没有单元格，而上方没有单元格，则您位于左上角，算法已完成。
- 如果左侧没有单元格，请转到步骤4。（此操作将继续循环直到您到达左上角。）
- 如果上方没有单元格，请转到步骤5。（此操作将循环进行，直到到达左上角。）
- 否则，请在左侧的单元格，左上方的单元格和上方的单元格之间进行三向比较。选择一个值最小的。如果有多个候选人，则可以随机选择一个。它们在此阶段 均 有效。（它们对应于具有相同总编辑距离的不同编辑路径。）
- 如果选择了上面的单元格，请转到步骤4。
- 如果您选择左侧的单元格，请转到步骤5。
- 如果您在左上方选择单元格，请转到步骤6。
- 你正在上升。请执行下列操作：
- 在当前单元格上记录输入字符的删除。
- 更新当前单元格，向上移动。
- 返回步骤1。
- 您正在向左移动。请执行下列操作：
- 记录当前单元格上输出字符的插入。
- 更新当前单元格，向左移动。
- 返回步骤1。
- 您正在对角移动。请执行下列操作：
- 在当前单元格上记录输入字符的替换，以代替当前单元格上的输出字符。
- 更新当前单元格，向上和向左移动。
- 返回步骤1。
把它放在一起
在上面的示例中，有两种可能的路径：
(4, 4) -> (3, 3) -> (2, 2) -> (1, 2) -> (0, 1) -> (0, 0)和
(4, 4) -> (3, 3) -> (2, 2) -> (1, 1) -> (0, 0)扭转它们，我们得到
(0, 0) -> (0, 1) -> (1, 2) -> (2, 2) -> (3, 3) -> (4, 4)和
(0, 0) -> (1, 1) -> (2, 2) -> (3, 3) -> (4, 4)因此，对于第一个版本，我们的第一个操作是向右移动，即插入。插入的字母是
h，因为我们要从isnt移到hint。（这与Insert, h您的详细输出相对应。）我们的下一个操作是对角线移动，即替换或无操作。在这种情况下，这是无操作的，因为两个位置的编辑距离是相同的（即字母是相同的）。这样Equal, i, i。然后向下移动，对应于删除。删除的字母是s，因为我们再次从isnt移到hint。（通常，要插入的字母来自输出字符串，而要删除的字母来自输入字符串。）所以是Delete, s。然后两个对角线运动，其值没有变化：Equal, n, n和Equal, t, t。结果：
Insert, h Equal, i, i Delete, s Equal, n, n Equal, t, t在以下位置执行这些说明
isnt：isnt (No change) hisnt (Insertion) hisnt (No change) hint (Deletion) hint (No change) hint (No change)总编辑距离为2。
我将保留第二条最小路径作为练习。请记住，两条路径是完全等效的。它们可能有所不同，但是它们将导致相同的最小编辑距离2，因此可以完全互换。在向后浏览矩阵的任何时候，如果您看到两个不同的局部最小值，则可以取其中一个，并且保证最终结果是正确的
一旦您掌握了所有这些内容，就不难编写代码了。在这种情况下，关键是要首先 深刻理解算法 。完成此操作后，对其进行编码就很容易了。
积累与重建
最后一点，您可以选择在填充矩阵时 累积 编辑内容。在这种情况下，矩阵中的每个单元格都可以是一个元组：
(2, ('ins', 'eq', 'del', 'eq', 'eq'))。您将增加长度， 并
追加与从最小先前状态开始的移动相对应的操作。这样就消除了回溯，从而降低了代码的复杂性；但是会占用额外的内存。如果执行此操作，则最终编辑序列将与最终编辑距离一起出现在矩阵的右下角。
