Java 中的 Levenshtein 算法

Question

我正在尝试在 Java 中实现 Levenshtein 的算法，灵感来自于此 Wikipedia article

public static int indicator(char a, char b) {
    return (a == b) ? 0 : 1;
}

public static int levenshtein(String token1, String token2) {
    int[] levi = new int[token2.length() + 1];
    int[] levi_1 = new int[token2.length() + 1];

    // initialize column i=0
    for (int j = 0; j <= token2.length(); j++)
        levi_1[j] = j;

    // columns i=1 -> i=len(token1)
    for (int i = 1; i <= token1.length(); i++) {
        // lev_a,b(i,0) = i
        levi[0] = i;
        // update rest of column i
        for (int j = 1; j <= token2.length(); j++) {
            levi[j] = Math.min(Math.min(levi_1[j] + 1, levi[j - 1] + 1),
                               levi_1[j - 1] + indicator(token1.charAt(i - 1), token2.charAt(j - 1)));
        }

        // save column i to update column i+1
        levi_1 = levi;
    }

    return levi[token2.length()];
}

但是在字符串“Maus”和“Haus”上测试这个给出了 4 的错误答案。你能帮我解决我做错的地方吗？

Answer 1

问题来自这一行：

levi_1 = levi;

此行不会更改 levi_1 数组中的每个值，它只会更改其引用；当您调用 levi_1[0]、levi_1[1] 等

时，值仍然相同

我建议您改写这些行：

for (int k = 0; k < levi.length; k++)
    levi_1[k] = levi[k];

Java 中的 Levenshtein 算法

Levenshtein algorithm in Java

java

levenshtein-distance