最小编辑距离重建

Question

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

Equal, L, L
Delete, E
Equal, A, A
Substitute, D, S
Insert, T

编辑:代码更新我的(部分正确)解决方案

这是代码,我的部分解决方案.它的作用例如我被给予("引导" - >"最后"),但不适用于下面的例子("提示" - >"不是").我怀疑这是因为第一个字符相同,这就是抛弃我的代码.任何正确方向的提示或指示都会很棒!

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建议的那样!

大图

这看起来像是Wagner-Fischer算法的实现.基本思想是计算"附近"前缀之间的距离,取最小值,然后计算当前字符串对的距离.因此,例如,假设你有两个字符串'i'和'h'.让我们沿着矩阵的垂直和水平轴放置它们,如下所示:

  _ h
_ 0 1
i 1 1

这里,'_'表示空字符串,并且矩阵中的每个单元对应于将输入(''或'i')作为输出(''或'h')的编辑序列.

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

从那里,您可以通过从上,左和左上角值中选择最小值并添加一个来计算任何位置的值,或者,如果字符串中的该字母相同,则取上面的值-left值不变.对于在值(1, 1)在上表中,最小是0在(0, 0),因此该值在(1, 1)IS 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)记住如果当前值与最小值相同,那么我们必须转到左上角的单元格,因为这是唯一一种不会增加编辑距离的移动.

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

1. 看看左上角的相邻单元格.如果它不存在,请转到步骤3.如果单元格确实存在,请记下存储在那里的值.
2. 左上角单元格中的值是否等于当前单元格中的值？如果是,请执行以下操作:
   • 记录空操作(即Equal).在这种情况下不需要编辑,因为此位置的字符是相同的.
   • 更新当前单元格,向上和向左移动.
   • 返回第1步.
3. 这里有很多分支:
   • 如果左侧没有单元格且上方没有单元格,则表示您位于左上角,算法已完成.
   • 如果左侧没有单元格,请转到步骤4.(这将继续循环,直到您到达左上角.)
   • 如果上面没有单元格,请转到步骤5.(这将继续循环,直到您到达左上角.)
   • 否则,在左边的单元格,左上角的单元格和上面的单元格之间进行三向比较.选择价值最小的那个.如果有多个候选人,您可以随机选择一个; 它们在这个阶段都是有效的.(它们对应于具有相同总编辑距离的不同编辑路径.)
     • 如果您选择了上面的单元格,请转到步骤4.
     • 如果您选择了左侧的单元格,请转到步骤5.
     • 如果您选择了左上方的单元格,请转到步骤6.
4. 你正在向上移动.请执行下列操作:
   • 在当前单元格中记录输入字符的删除.
   • 更新当前单元格,向上移动.
   • 返回第1步.
5. 你向左移动.请执行下列操作:
   • 在当前单元格中记录输出字符的插入.
   • 向左移动,更新当前单元格.
   • 返回第1步.
6. 你正在对角线移动.请执行下列操作:
   • 记录当前单元格中输入字符的替换,以代替当前单元格的输出字符.
   • 更新当前单元格,向上和向左移动.
   • 返回第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')).您将增加长度,并附加与最小先前状态的移动相对应的操作.这消除了回溯,因此降低了代码的复杂性; 但它占用了额外的内存.如果执行此操作,最终编辑序列将与矩阵右下角的最终编辑距离一起显示.

Answer 2

我建议你看一下python-Levenshtein模块.可能会在那里找到很长的路要走:

>>> import Levenshtein
>>> Levenshtein.editops('LEAD','LAST')
[('replace', 1, 1), ('replace', 2, 2), ('replace', 3, 3)]

您可以处理编辑操作的输出以创建详细说明.