具有替换、删除和插入计数的 Levenshtein 距离

Question

这里 https://davedelong.com/blog/2015/12/01/edit-distance-and-edit-steps/ 有一篇关于 Levenshtein 距离的很棒的博客 post。我正在尝试实现这一点，以便在返回 Levenshtein 距离时也包括 subs、dels 和 ins 的计数。只是运行对我的算法进行气味检查。

def get_levenshtein_w_counts(s1: str, s2: str):
    row_dim = len(s1) + 1  # +1 for empty string
    height_dim = len(s2) + 1

    # tuple = [ins, del, subs]
    # Moving across row is insertion
    # Moving down column is deletion
    # Moving diagonal is sub
    matrix = [[[n, 0, 0] for n in range(row_dim)] for m in range(height_dim)]

    for i in range(1, height_dim):
        matrix[i][0][1] = i

    for y in range(1, height_dim):
        for x in range(1, row_dim):
            left_scores = matrix[y][x - 1].copy()
            above_scores = matrix[y - 1][x].copy()
            diagonal_scores = matrix[y - 1][x - 1].copy()

            scores = [sum_list(left_scores), sum_list(diagonal_scores), sum_list(above_scores)]
            min_idx = scores.index(min(scores))

            if min_idx == 0:
                matrix[y][x] = left_scores
                matrix[y][x][0] += 1
            elif min_idx == 1:
                matrix[y][x] = diagonal_scores
                matrix[y][x][2] += (s1[x-1] != s2[y-1])
            else:
                matrix[y][x] = above_scores
                matrix[y][x][1] += 1

    return matrix[-1][-1]

所以根据博客 post 如果你制作一个矩阵，其中行是第一个单词 + 和空 str，列是第二个单词加一个空字符串。您将编辑距离存储在每个索引处。然后你从左边、上面和对角线得到最小的。如果最小值是对角线那么你知道你只是添加了 1 个子，如果最小值是从左边开始那么你只是添加了 1 个插入。如果最小值来自上方，那么您只是删除了 1 个字符。

我想我做错了，因为 get_levenshtein_w_counts("Frank", "Fran") 返回了 [3, 2, 2]

Answer 1

问题是 Python 确实为对象传递地址，所以我应该将列表克隆到变量而不是直接引用。

具有替换、删除和插入计数的 Levenshtein 距离

Levenshtein distance with substitution, deletion and insertion count

levenshtein-distance

edit-distance