python - 最小编辑距离重建

Question

我知道在堆栈上和在线上都有类似的答案，但我觉得我错过了一些东西。给定下面的代码，我们需要重建导致最小编辑距离的事件序列。对于下面的代码，我们需要编写一个输出的函数:

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')

Answer 1

我认为在这种情况下更深入地理解算法很重要。与其给你一些伪代码，我将引导你完成算法的基本步骤，并向你展示你想要的数据是如何在产生的最终矩阵中“编码”的。当然，如果您不需要推出自己的算法，那么您显然应该使用别人的，如 MattH suggests !

大图

在我看来，这就像 Wagner-Fischer algorithm 的实现。基本思想是计算“附近”前缀之间的距离，取最小值，然后从中计算当前字符串对的距离。例如，假设您有两个字符串 'i' 和 'h' 。让我们沿着矩阵的纵轴和横轴布置它们，如下所示:

  _ h
_ 0 1
i 1 1

这里，'_' 表示一个空字符串，矩阵中的每个单元格对应一个编辑序列，该序列将输入( '' 或 'i' )转换为输出( 0x25181224131 或 2031313 )。

从空字符串到任何长度为 L 的字符串的距离是 L，(需要 L 次插入)。从任何长度为 L 的字符串到空字符串的距离也是 L(需要 L 个删除)。这涵盖了第一行和第一列中的值，它们只是递增。

从那里，您可以通过从上、左和左上值中取最小值并加一来计算任何位置的值，或者，如果字符串中该点的字母相同，则取上- 左值不变。在''在上面的表中的值，最小值为'h'在(1, 1)，所以在0值为(0, 0)，这就是从(1, 1)到1(一个取代)的最小编辑距离。所以一般来说，最小编辑距离总是在矩阵的右下角。

现在让我们再做一个，比较 'i' 和 'h' 。这里再一次，矩阵中的每个单元对应于取得输入(is，hi，或'')到输出('i'，'is'，或'')的编辑序列。

  _ h i
_ 0 1 2
i 1 1 #
s 2 # #

我们首先扩大矩阵，使用 'h' 作为我们还不知道的值的占位符，并通过递增扩展第一行和第一列。完成后，我们可以开始计算上面标记为 'hi' 的位置的结果。让我们从 # 开始(在(行，列)中，即行主要表示法)。在上、左上和左值中，最小值为 # 。表中对应的字母不同—— (2, 1) 和 1 —— 所以我们在最小值上加一得到 s ，然后继续。

  _ h i
_ 0 1 2
i 1 1 #
s 2 2 #

让我们继续讨论 h 处的值。现在情况有所不同，因为表中相应的字母是相同的——它们都是 2 。这意味着我们可以选择在不加一的情况下取左上角单元格中的值。这里的指导直觉是我们不必增加计数，因为相同的字母被添加到这个位置的两个字符串中。由于两个字符串的长度都增加了 1，我们沿对角线移动。

  _ h i
_ 0 1 2
i 1 1 1
s 2 2 #

随着最后一个空单元格，事情恢复正常。对应的字母是 (1, 2) 和 i ，所以我们再次取最小值并加一，得到 s :

  _ h i
_ 0 1 2
i 1 1 1
s 2 2 2

如果我们对两个以 i 和 2 开头的更长单词继续这个过程，我们得到的表格是——is(忽略标点符号)和 0x251812241313:

  _ 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

这个矩阵稍微复杂一些，但是这里最终的最小编辑距离仍然只是 hi ，因为这两个字符串的最后两个字母是相同的。方便的!

重新创建编辑序列

那么我们如何从这个表中提取编辑类型呢？关键是要意识到 table 上的移动对应于特定类型的编辑。因此，例如，从 isnt 到 hint 的向右移动会将我们从 2 ，不需要编辑，到 (0, 0) ，需要一次编辑。同样，从 (0, 1) 到 _ -> _ 的向下移动将我们从 _ -> h ，不需要编辑，到 (0, 0) ，需要一次编辑，一次删除。最后，从 (1, 0) 到 _ -> _ 的对角线移动将我们从 i -> _ ，不需要编辑，到 (0, 0) ，需要一个编辑，替换。

所以现在我们要做的就是反转我们的步骤，从上、左和左上角的单元格中追踪局部最小值回到原点 (1, 1) ，请记住，如果当前值与最小值相同，那么我们必须转到左上角的单元格，因为这是唯一一种不会增加编辑距离的移动。

以下是您可以采取的步骤的详细说明。从完整矩阵的右下角开始，重复以下操作，直到到达左上角:

查看左上角的相邻单元格。如果它不存在，请转到第 3 步。如果该单元格确实存在，请注意存储在那里的值。

左上角单元格中的值是否等于当前单元格中的值？如果是这样，请执行以下操作:

记录一个空操作(即 _ -> _ )。在这种情况下不需要编辑，因为这个位置的字符是相同的。

更新当前单元格，向上和向左移动。

返回步骤 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)

所以对于第一个版本，我们的第一个操作是向右移动，即插入。插入的字母是 i -> h ，因为我们从 (0, 0) 移动到 Equal 。 (这对应于详细输出中的 h。)我们的下一个操作是对角线移动，即替换或空操作。在这种情况下，这是一个空操作，因为两个位置的编辑距离相同(即字母相同)。所以 isnt 。然后向下移动，对应于删除。删除的字母是 hint ，因为我们再次从 Insert, h 移动到 Equal, i, i 。 (通常，要插入的字母来自输出字符串，而要删除的字母来自输入字符串。)所以这是 s 。然后是两个没有变化的对角线运动: isnt 和 hint 。

结果:

Insert, h
Equal, i, i
Delete, s
Equal, n, n
Equal, t, t

在 Delete, s 上执行这些指令:

isnt   (No change)
hisnt  (Insertion)
hisnt  (No change)
hint   (Deletion)
hint   (No change)
hint   (No change)

总编辑距离为 2。

我将保留第二个最小路径作为练习。请记住，两条路径是完全等效的；它们可能不同，但它们将导致相同的最小编辑距离 2，因此完全可以互换。在逆向处理矩阵的任何时候，如果您看到两个不同的可能局部最小值，您可以选择其中一个，并且最终结果保证是正确的

一旦你理解了这一切，编码就不难了。在这种情况下，关键是首先要深入了解算法。一旦你这样做了，编码就很容易了。

积累与重建

最后要注意的是，您可能会选择在填充矩阵时累积编辑。在这种情况下，矩阵中的每个单元格都可以是一个元组: Equal, n, n 。您将增加长度，并附加与从最小先前状态开始的移动相对应的操作。这消除了回溯，因此降低了代码的复杂性；但它会占用额外的内存。如果这样做，最终编辑序列将与最终编辑距离一起出现在矩阵的右下角。