在java中

Question

我试图使用维基百科参考

用Java实现的 Wagner-Fischer algorithm瓦格纳菲舍尔算法实现

wagner-fischer

Java代码：

public class StringDistance { 

public static void main(String[] args) { 
    int i, j, m, n, temp, tracker; 

    int[][] d = new int[50][50]; 

    String s = "kitten"; 
    String t = "sitting"; 

    char u[] = s.toCharArray(); 
    char v[] = t.toCharArray(); 

    m = u.length; 
    n = v.length; 

    for (i = 0; i <= m; i++) { 
     d[i][0] = i; 
    } 
    for (j = 0; j <= n; j++) { 
     d[0][j] = j; 
    } 

    for (j = 1; j <= m; j++) { 
     for (i = 1; i <= n; i++) { 
      if (u[i - 1] == v[j - 1]) { 
       tracker = 0; 
      } else { 
       tracker = 1; 
      } 

      temp = Math.min((d[i - 1][j] + 1), (d[i][j - 1] + 1)); 
      d[i][j] = Math.min(temp, (d[i - 1][j - 1] + tracker)); 

     } 
    } 

    System.out.println("The levenstien distance" + d[n][m]); 
} 
} 

但上面的代码为唯一的工作等长的琴弦。如果我想让这个工作不平等strings.Please让我知道如何克服这个问题。

我收到索引越界的错误：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6 
at StringDistance.main(StringDistance.java:32) 

Answer 1

让我们摆脱了一些局部变量，以使其更清晰为什么发生这种情况：

for (j = 1; j <= u.length; j++) { 
    for (i = 1; i <= v.length; i++) { 
     if (u[i - 1] == v[j - 1]) { 
      tracker = 0; 
     } else { 
      tracker = 1; 
     } 

您使用作为指向v的索引，将i - 1（其保证在范围v中）作为指标u和j - 1（其保证在范围u中）作为索引。

所以我怀疑这个表达式：

u[i - 1] == v[j - 1] 

应该只是

u[j - 1] == v[i - 1] 

我也强烈建议只在第一次使用的时候声明变量，在尽可能小的范围，并使用0基于索引而不是基于1的索引。而条件运算符也有帮助。所以，你的循环会变成：

for (int j = 0; j < u.length; j++) { 
    for (int i = 0; i < v.length; i++) { 
     int tracker = u[j] == v[i] ? 0 : 1; 
     int temp = Math.min(d[i][j + 1] + 1, d[i + 1][j] + 1); 
     d[i + 1][j + 1] = Math.min(temp, d[i][j] + tracker); 
    } 
} 

Answer 2

您已经根据wagner-fischer algorithm

for (j = 1; j <= n; j++) { 
    for (i = 1; i <= m; i++) { 
     if (u[i - 1] == v[j - 1]) { 
      tracker = 0; 
     } else { 
      tracker = 1; 
     } 

     temp = Math.min((d[i - 1][j] + 1), (d[i][j - 1] + 1)); 
     d[i][j] = Math.min(temp, (d[i - 1][j - 1] + tracker)); 

    } 
} 

你还需要检查你的跟踪状态它们不正确使用循环错误状态。