4

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

这是我找到的示例代码：

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];
}
4

3 回答 3

5

您的代码正在使用动态编程计算Levenshtein 距离。

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

于 2012-12-20T21:46:08.657 回答
4

该矩阵包含 [在末尾] 的所有前缀word1和 的所有前缀之间的编辑距离word2。

d[i][j] = edit distance between word1[0..(i-1)] and word2[0..(j-1)]

您对d[l1][l2]. 一般来说，要计算d[i][j]，您需要查看三个较小的邻居d[i-1][j]和。因此，传递性要求所有条目，其中至少一个坐标小于resp （而另一个不大于）。例外情况是两个字符和相等，在这种情况下，您只需要对角线较小的邻居。d[i-1][j-1]d[i][j-1]d[i][j]ijword1[i-1]word2[j-1]

如果您首先用 填充矩阵以-1指示尚未评估前缀之间的相应编辑距离，然后递归地计算矩阵的区域可能保持不变。如果有很多对相等的字符，则可能是大区域[如果两个单词相等，则仅评估对角线]，如果有少量相等字符对，则只有小区域。d[l1][l2]d[i][j]

在一般情况下，计算 需要大部分矩阵d[l1][l2]，因此使用简单算法完全计算矩阵比递归并仅计算实际需要的值要快。

如果您不存储较短前缀的值，因为它们需要传递到 compute ，因此必须为从 到达d[i][j]的每种方式重新计算它们。由于可以通过多种方式从 到达，这将导致大量重新计算，从而导致算法效率极低。d[i-a][j-b]d[i][j]d[i-a][j-b]d[i][j]

由于每一行的计算只使用前一行，你可以只使用两个长度数组min{l1, l2} + 1来节省一些内存，但除非单词真的很长，否则差别不大，而且代码更简单全阵列。

于 2012-12-20T21:37:12.683 回答
3

代码可能难以理解，但这里有一些提示：

  1. 两个字符串中任意一对字符之间的编辑距离至少是之前比较过的所有字符对的编辑距离。例如，在比较两个字符串abc和ade时，当您到达比较c和e的阶段时，您确定两个字符串的编辑距离至少是迄今为止找到的最小编辑距离（在这种情况下为 1）

  2. 如果比较的两个字符不相等，则编辑距离将增加一，表示替换。所以如果你在比较之前知道字符串的编辑距离，你可以根据字符是否相等给它加1。

有了这两个事实，

position[i, j] 是考虑的编辑距离

如果第 i 行元素不存在，则 position[i-1,j] 将是到目前为止字符串的总编辑距离（表示插入成本）

如果第 j 列元素被删除，位置 [i,j-1] 将是到目前为止字符串的总编辑距离（表示删除成本）

position[ii,j-1] 将是迄今为止为所有先前元素计算的最小编辑距离

position[i,j] 然后通过取所有三种可能性中的最小值并添加当前决策来计算。

于 2014-06-22T16:24:21.410 回答