Python 使用动态规划和二维数组编辑距离算法 - 输出不是最优的

Question

我遇到了编辑距离（Levenshtein distance）的问题。我查看了其他类似的 Whosebug 问题，并确定我的问题与它们不同——无论是使用的语言还是方法。

我使用了一个 2D 数组 来比较两个字符串，并使用 动态编程 来存储以前的值。如果字符串索引中的 i 和 j 匹配，它将输出 0，因为我们不需要做任何事情；否则，输出为1。如下图，橙色箭头表示匹配。

（根据答案的建议编辑以下代码）

def edit_distance(source, target):
    n = len(target)+1
    m = len(source)+1

    # let D denote the 2-dimensional array, m is the column, n is row
    D = [ [0]*m for _ in range(n)] 

    # the loop inside is the target string, we operate this
    # while the loop outside is the source string

    for j in range(0, m):
        for i in range(0, n):
            if target[i-1] == source[j-1]:
                # match, insertion and deletion, find the path with least move
                D[i][j] = min(D[i-1][j-1], D[i-1][j]+1, D[i][j-1]+1)

            else:
                # mismatch, insertion and deletion, find the path with least move
                D[i][j] = min(D[i-1][j-1]+1, D[i-1][j]+1, D[i][j-1]+1)
            
    return D[n-1][m-1]

print(edit_distance("distance", "editing"))

然而，我的代码最终输出的是8，而字符串“editing”和“distance”之间的最佳编辑距离应该是5，我很困惑。能不能从动态规划的角度帮忙解决一下？

Answer 1

你有 2 个错误。

首先是初始化。你用 0 填充所有内容，但是当你想填充 D[1][m] 时，你查看上面的单元格（它应该是 m）并找到一个 0。确保正确填充了边框。

其次，您的迭代已关闭。 range(1, n) over 'editing' 会给你 'diting'。要将 N 和 M 固定为 1 (n=len(target) + 1) 并在比较中使用 target[i-1] == source[j-1].

Answer 2

啊，看来我找到了解决办法，我现在必须回答我自己的问题了。（有些地方我还是很困惑，回答这个问题只是为了简单介绍一下新的实现方式，以节省其他好心人的时间）

所以首先，我在原代码中遗漏了一个条件，即如果两个字符串输入之一为空怎么办？然后我们必须插入其他字符串中的所有内容。从此以后，最佳编辑距离就是另一个字符串的长度。

    if i == 0:
        D[i][j] = j    
    elif j == 0:
        D[i][j] = i

另外，关于代码的原始for循环，我从GeeksforGeeks中吸取了错误。如果我的理解是正确的，他们是说如果两个指标（i和j）一致，我们需要做的就是在图（i-1和j）上沿对角线向上移动 -1) 不添加任何计数。

否则，如果索引不匹配，我们将移动到 i-1、j-1 的方向或依赖地对角线向上。我在这一点上是对的，除了计数是在移动之后添加的，而我是在移动过程中添加的。

我仍然有点不确定它是如何工作的，但是我将比较下面的两种算法，如果有人可以在评论中进一步解释它，我将不胜感激。

我原来的 for 循环（出现在问题中）

for j in range(0, m):
    for i in range(0, n):
        if target[i-1] == source[j-1]:
            D[i][j] = min(D[i-1][j-1], D[i-1][j]+1, D[i][j-1]+1)

        else:
            D[i][j] = min(D[i-1][j-1]+1, D[i-1][j]+1, D[i][j-1]+1)

下面是新的for循环，经测试输出正确：

        if target[i-1] == source[j-1]:
            D[i][j] = D[i-1][j-1]

        else:
            D[i][j] = 1 + min(D[i][j-1], D[i-1][j], D[i-1][j-1])

如果有人能进一步解释这是如何工作的，我将不胜感激，因为我对新代码的了解还很肤浅

最终代码：

def edit_distance(target, source):

    m = len(target)+1
    n = len(source)+1
    D = [[0 for x in range(n)] for x in range(m)]


    for i in range(m):
        for j in range(n):

            if i == 0:
                D[i][j] = j   
            elif j == 0:
                D[i][j] = i 

            elif target[i-1] == source[j-1]:
                D[i][j] = D[i-1][j-1]
            else:
                D[i][j] = 1 + min(D[i][j-1], D[i-1][j], D[i-1][j-1])    

    return D[m-1][n-1]

print(edit_distance("distance", "editing"))
# output = 5, which is correct

Python 使用动态规划和二维数组编辑距离算法 - 输出不是最优的

Python Edit distance algorithm with dynamic programming and 2D Array - Output is not optimal

python

algorithm

dynamic-programming

levenshtein-distance

edit-distance