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

    } 
} 

你還需要檢查你的跟蹤狀態它們不正確使用循環錯誤狀態。