编辑距离Java [英] Edit Distance Java

问题描述

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

I wrote this algorithm to calculate the sum of the number of deletion and insert (so, of the edits) to make the first string equals to the second one. But it doesn't work.

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:"cara" edit_distance = 2(1个删除+ 1个插入)

Example String 1: "casa" String 2: "cara" edit_distance=2 (1 deletion + 1 insert)

这些是起作用的字符串: 字符串1:"casa"，字符串2:"cassa"，edit_distance = 1； 字符串1:"pioppo"，字符串2:"pioppo"，edit_distance = 0;

These are the strings that work: String 1: "casa", String 2: "cassa", edit_distance=1; String 1:"pioppo", String 2: "pioppo", edit_distance=0;

这些是行不通的: 字符串1:"casa"，字符串2:"cara"，edit_distance = 2； (在我的代码中= 0) 字符串1:"tassa"，字符串2:"passato"，edit_distance = 4； (以我的代码= 2)

These are the one which doesn't work: String 1: "casa", String 2: "cara", edit_distance=2; (in my code=0) String 1: "tassa", String 2: "passato", edit_distance=4; (in my code=2)

推荐答案

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

I think that the implementation is almost correct and you missed the stop conditions. They should be:

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"的结果:

Here is the result for "tassa" and "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);
}

如果运行此命令，则会得到:

If you run this you get:

4

这篇关于编辑距离Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！