java - 编辑距离 Java

Question

我编写了这个算法来计算删除和插入(编辑)数量的总和，以使第一个字符串等于第二个字符串。但它不起作用。

public static int distance (String s1, String s2) {
    return distance(s1, s2, 0, 0);
}

private static int distance(String s1, String s2, int i, int j) {
    if (i == s1.length) return j;
    if (j == s2.length) return i;
    if (s1.charAt(i) == s2.charAt(j))
        return distance(s1, s2, i + 1, j + 1);
    int rep = distance(s1, s2, i + 1, j + 1) + 1;
    int del = distance(s1, s2, i, j + 1) + 1;
    int ins = distance(s1, s2, i + 1, j) + 1;
    return Math.min(del, Math.min(ins, rep));
}

编辑:示例 字符串 1:“casa” 字符串 2:“卡拉” edit_distance=2(1 次删除 + 1 次插入)

编辑2: 这些是有效的字符串: 字符串 1:“casa”，字符串 2:“cassa”，edit_distance=1； 字符串 1:“pioppo”，字符串 2:“pioppo”，edit_distance=0；

这些是不起作用的: 字符串 1:“casa”，字符串 2:“cara”，edit_distance=2； (在我的代码中=0) 字符串 1:“tassa”，字符串 2:“passato”，edit_distance=4； (在我的代码中=2)

Answer 1

我认为实现几乎是正确的，并且您错过了停止条件。他们应该是:

if (j == s2.length()) {
    return s1.length() - i;
}
if (i == s1.length()) {
    return s2.length() - j;
}

所以完整的实现应该是:

private static int distance(String s1, String s2, int i, int j) {
    if (j == s2.length()) {
        return s1.length() - i;
    }
    if (i == s1.length()) {
        return s2.length() - j;
    }
    if (s1.charAt(i) == s2.charAt(j))
        return distance(s1, s2, i + 1, j + 1);
    int rep = distance(s1, s2, i + 1, j + 1) + 2; // since Jim Belushi considers replacement to be worth 2.
    int del = distance(s1, s2, i, j + 1) + 1;
    int ins = distance(s1, s2, i + 1, j) + 1;
    return Math.min(del, Math.min(ins, rep));
}

更新

这是“tassa”和“passato”的结果:

代码:

private static int distance(String s1, String s2, int i, int j) {
    if (j == s2.length()) {
        return s1.length() - i;
    }
    if (i == s1.length()) {
        return s2.length() - j;
    }
    if (s1.charAt(i) == s2.charAt(j))
        return distance(s1, s2, i + 1, j + 1);
    int rep = distance(s1, s2, i + 1, j + 1) + 2;
    int del = distance(s1, s2, i, j + 1) + 1;
    int ins = distance(s1, s2, i + 1, j) + 1;
    return Math.min(del, Math.min(ins, rep));
}

public static void main(String[] args) {
    int dist = distance("tassa", "passato", 0, 0);
    System.out.println(dist);
}

如果你运行这个你会得到:

4