查找两个字符串Levenshtein距离(Finding Levenshtein distance

我试图在Eclipse的Java实现Levenshtein距离在以下两个字符串：

我把这个想法从维基百科，但我不知道为什么我的输出是错误的，我需要帮助，找到我的错误/秒。

“秩”

“因果”

  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]是最低值，所以你应该有效地计算。

如果把这些错误考虑进去，可以修改表更新算法（在评论的变化// ）：

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);
    }
}