莱文斯坦算法在Java中

huangapple go评论74阅读模式
英文:

Levenshtein algorithm in Java

问题

以下是翻译好的代码部分:

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

    // 初始化列 i=0
    for (int j = 0; j <= token2.length(); j++)
        levi_1[j] = j;

    // 列 i=1 -> i=len(token1)
    for (int i = 1; i <= token1.length(); i++) {
        // lev_a,b(i,0) = i
        levi[0] = i;
        // 更新列 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)));
        }

        // 保存列 i 以更新列 i+1
        levi_1 = levi;
    }

    return levi[token2.length()];
}

在字符串 "Maus" 和 "Haus" 上测试时,得到的结果是 4,这是错误的。你能告诉我你在哪里出错了吗?

英文:

I am trying to implement Levenshtein's algorithm in Java, inspired from this 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 &lt;= token2.length(); j++)
        levi_1[j] = j;

    // columns i=1 -&gt; i=len(token1)
    for (int i = 1; i &lt;= token1.length(); i++) {
        // lev_a,b(i,0) = i
        levi[0] = i;
        // update rest of column i
        for (int j = 1; j &lt;= 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()];
}

But testing this on string "Maus" and "Haus" gives me an incorrect answer of 4. Can you help me with what I am doing wrong?

答案1

得分: 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];
英文:

The problem comes from this line:

levi_1 = levi;

This line doesn't change every value from the levi_1 array, it only changes its reference; the values are still the same when you call levi_1[0], levi_1[1], etc.

I would suggest you to write those lines instead:

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

huangapple
  • 本文由 发表于 2020年9月22日 16:29:23
  • 转载请务必保留本文链接:https://go.coder-hub.com/64005880.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定