最小编辑距离重建 - python

我知道在堆栈上和在线上都可以找到类似的答案,但是我感觉自己缺少一些东西。给定以下代码,我们需要重建导致最小编辑距离的事件序列。对于下面的代码,我们需要编写一个输出函数:

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 suggests!

大图景

在我看来,这类似于Wagner-Fischer algorithm的实现。基本思想是计算“附近”前缀之间的距离,取最小值,然后从中计算出当前字符串对的距离。例如,假设您有两个字符串'i''h'。让我们沿着矩阵的垂直和水平轴进行布局,如下所示:

  _ h
_ 0 1
i 1 1

在这里,'_'表示一个空字符串,矩阵中的每个单元格对应于一个将输入('''i')输入到输出('''h')的编辑序列。

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

从那里,您可以通过从上,左和左上值中取最小值,然后加上一个值来计算任何位置的值;或者,如果字符串中该点的字母相同,则取上一个值-left值不变。对于上表中(1, 1)的值,最小值是0(0, 0),因此(1, 1)的值是1,这是'i''h'的最小编辑距离(一个替换)。因此,通常,最小编辑距离始终位于矩阵的右下角。

现在让我们再做一次,比较ishi。同样,矩阵中的每个单元格都对应于一个将输入('''i''is')输入到输出('''h''hi')的编辑序列。

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

我们首先放大矩阵,将#用作尚不知道的值的占位符,然后通过递增扩展第一行和第一列。这样,我们就可以开始计算上面标记为#的位置的结果。让我们从(2, 1)(在(行,列),即行为主的表示法)开始。在上,左上和左值中,最小值为1。表中对应的字母不同-sh-因此我们在该最小值上加一个以获得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 #

在最后一个空单元格之后,一切恢复正常。对应的字母是si,因此我们再次取最小值并加一个,得到2:

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

如果我们继续此过程以ishi开头的两个更长的单词,这是我们得到的表格-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, nEqual, 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'))。您将增加长度,并追加与从最小先前状态开始的移动相对应的操作。这消除了回溯,从而降低了代码的复杂性;但是会占用额外的内存。如果执行此操作,则最终编辑序列将与最终编辑距离一起出现在矩阵的右下角。

    python JSON对象必须是str,bytes或bytearray,而不是'dict - python

    在Python 3中,要加载以前保存的json,如下所示:json.dumps(dictionary)输出是这样的{"('Hello',)": 6, "('Hi',)": 5}当我使用json.loads({"('Hello',)": 6,…

    Python 3运算符>>打印到文件 - python

    我有以下Python代码编写项目的依赖文件。它可以在Python 2.x上正常工作,但是在使用Python 3进行测试时会报告错误。depend = None if not nmake: depend = open(".depend", "a") dependmak = open(".depend.mak&#…

    快速返回没有Python中特定元素的列表的方法 - python

    如果我有任意顺序的卡片套装列表,如下所示:suits = ["h", "c", "d", "s"] 我想返回一个没有'c'的列表noclubs = ["h", "d", "s"] 有没有简单的方法可以…

    Python pytz时区函数返回的时区为9分钟 - python

    由于某些原因,我无法从以下代码中找出原因:>>> from pytz import timezone >>> timezone('America/Chicago') 我得到:<DstTzInfo 'America/Chicago' LMT-1 day, 18:09:00 STD…

    如何将Python字节字符串表示形式转换为字节? - python

    我在文本文件中存储了许多Python字节对象,这些Python打印的内容类似于"b'\x80\x03}q\x00.'"如何将每个对象转换回字节对象?换句话说,我正在尝试找到一个执行convert("b'\x80\x03}q\x00.'") == b'\x80\x03}q…