在两个字符串上查找 Levenshtein 距离
Finding Levenshtein distance on two string
我正在尝试在 Eclipse Java Levenshtein distance 中实现以下两个字符串:
我的想法来自维基百科,但我不知道为什么我的输出是错误的,我需要帮助才能找到我的 mistake/s。
- "kruskal"
"causal"
package il.ac.oranim.alg2016;
public class OPT {
public static void main(String[] args)
{
char[] t={'k','r','u','s','k','a','l'};
char[] s={'c','a','u','s','a','l'};
for (int i=0;i<=s.length;i++)
{
for (int j=0;j<=t.length;j++)
System.out.print(LevenshteinDistance(s,t)[i][j]+" ");
System.out.println();
}
}
private static int[][] LevenshteinDistance(char s[], char t[])
{
// d is a table with m+1 rows and n+1 columns
int[][] d=new int[s.length+1][t.length+1];
for (int i=0;i<=s.length;i++)
d[i][0] = i; // deletion
for (int j=0;j<=t.length;j++)
d[0][j] = j; // insertion
for (int j=1;j<t.length;j++)
{
for (int i=1;i<s.length;i++)
{
if (s[i] ==t[j])
d[i][j]=d[i-1][j-1];
else
d[i][j] = Math.min(Math.min((d[i-1][ j] + 1),
(d[i][j-1] + 1)),
(d[i-1][j-1] + 1)) ;
}
}
return d;
}
}
我的输出:
0 1 2 3 4 5 6 7
1 1 2 3 4 4 5 0
2 2 1 2 3 4 5 0
3 3 2 1 2 3 4 0
4 4 3 2 2 2 3 0
5 5 4 3 3 3 2 0
6 0 0 0 0 0 0 0
输出应该是:
0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 2 2 3 4 5 5 6
3 3 3 2 3 4 5 6
4 4 4 3 2 3 4 5
5 5 5 4 3 3 3 4
6 6 6 5 4 4 4 3
如果您重新阅读规格,您会发现有两个错误:
- 在维基百科上,他们使用的索引范围从
1
到(包括 n
),根据维基百科,字符串从索引 i=1
开始,它是 i=0
在 Java 中;和
权重未正确更新:
if (s[i] ==t[j])
d[i][j]=d[i-1][j-1];
在规范中,这应该是 d[i-1][j]+1
、d[i][j-1]+1
和 d[i-1][j-1]
中的最小值。不能保证d[i-1][j-1]
是最低值,所以你应该有效地计算它。
如果考虑到这些错误,可以修改 table 更新算法(更改评论 //
):
for (int j=1;j<=t.length;j++) { //use <= instead of <
for (int i=1;i<=s.length;i++) { //use <= instead of <
if (s[i-1] ==t[j-1]) //use i-1 and j-1
d[i][j] = Math.min(Math.min(d[i-1][j]+1,d[i][j-1]+1),d[i-1][j-1]); //use the correct update
else
d[i][j] = Math.min(Math.min(d[i-1][j]+1,d[i][j-1]+1),d[i-1][j-1]+1);
}
}
我正在尝试在 Eclipse Java Levenshtein distance 中实现以下两个字符串:
我的想法来自维基百科,但我不知道为什么我的输出是错误的,我需要帮助才能找到我的 mistake/s。
- "kruskal"
"causal"
package il.ac.oranim.alg2016; public class OPT { public static void main(String[] args) { char[] t={'k','r','u','s','k','a','l'}; char[] s={'c','a','u','s','a','l'}; for (int i=0;i<=s.length;i++) { for (int j=0;j<=t.length;j++) System.out.print(LevenshteinDistance(s,t)[i][j]+" "); System.out.println(); } } private static int[][] LevenshteinDistance(char s[], char t[]) { // d is a table with m+1 rows and n+1 columns int[][] d=new int[s.length+1][t.length+1]; for (int i=0;i<=s.length;i++) d[i][0] = i; // deletion for (int j=0;j<=t.length;j++) d[0][j] = j; // insertion for (int j=1;j<t.length;j++) { for (int i=1;i<s.length;i++) { if (s[i] ==t[j]) d[i][j]=d[i-1][j-1]; else d[i][j] = Math.min(Math.min((d[i-1][ j] + 1), (d[i][j-1] + 1)), (d[i-1][j-1] + 1)) ; } } return d; }
}
我的输出:
0 1 2 3 4 5 6 7
1 1 2 3 4 4 5 0
2 2 1 2 3 4 5 0
3 3 2 1 2 3 4 0
4 4 3 2 2 2 3 0
5 5 4 3 3 3 2 0
6 0 0 0 0 0 0 0
输出应该是:
0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 2 2 3 4 5 5 6
3 3 3 2 3 4 5 6
4 4 4 3 2 3 4 5
5 5 5 4 3 3 3 4
6 6 6 5 4 4 4 3
如果您重新阅读规格,您会发现有两个错误:
- 在维基百科上,他们使用的索引范围从
1
到(包括n
),根据维基百科,字符串从索引i=1
开始,它是i=0
在 Java 中;和 权重未正确更新:
if (s[i] ==t[j]) d[i][j]=d[i-1][j-1];
在规范中,这应该是 d[i-1][j]+1
、d[i][j-1]+1
和 d[i-1][j-1]
中的最小值。不能保证d[i-1][j-1]
是最低值,所以你应该有效地计算它。
如果考虑到这些错误,可以修改 table 更新算法(更改评论 //
):
for (int j=1;j<=t.length;j++) { //use <= instead of <
for (int i=1;i<=s.length;i++) { //use <= instead of <
if (s[i-1] ==t[j-1]) //use i-1 and j-1
d[i][j] = Math.min(Math.min(d[i-1][j]+1,d[i][j-1]+1),d[i-1][j-1]); //use the correct update
else
d[i][j] = Math.min(Math.min(d[i-1][j]+1,d[i][j-1]+1),d[i-1][j-1]+1);
}
}