algorithm - 编辑距离说明

Question

我看过很多代码来解决这个问题，但我不明白为什么他们使用矩阵来表示两个单词之间的距离。谁能给我解释一下？

这是我找到的示例代码:

public static int minDistance(String word1, String word2)
{
    int l1 = word1.length(), l2 = word2.length();

    int[][] d = new int[l1 + 1][l2 + 1];

    // the edit distance between an empty string and the prefixes of
    // word2
    for (int i = 0; i < l2 + 1; i++) {
        d[0][i] = i;
    }

    // the edit distance between an empty string and the prefixes of
    // word1
    for (int j = 0; j < l1 + 1; j++) {
        d[j][0] = j;
    }

    for (int i = 1; i < l1 + 1; i++) {
        for (int j = 1; j < l2 + 1; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                d[i][j] = d[i - 1][j - 1];
            } else {
                d[i][j] = min(1 + d[i][j - 1], 1 + d[i - 1][j],
                1 + d[i - 1][j - 1]); // min of insertion,
                // deletion, replacement
            }
        }
    }

    return d[l1][l2];
}

Answer 1

您的代码正在计算 Levenshtein distance使用 dynamic programming .

数组 d 最终将包含各种子问题的解决方案，其中 d[i][j] 是第一个 i 第一个单词的字母和第二个单词的前 j 个字母。 d[i][j]和条目d[i-1][j]之间存在关系，d[i][j-1 ] 和 d[i-1][j-1]。该算法以已经计算出所需子问题的方式计算表的条目(这是动态规划部分)。