英文:
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 <= 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()];
}
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 < levi.length; k++)
levi_1[k] = levi[k];
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论