Нахождение Левенштейна на две строки

Question

Я пытаюсь реализовать в Eclipse, Java Levenshtein distance на следующих двух строк:

Я взял идею из Википедии, но я не знаю, почему мой выход не так, мне нужна помощь найти мою ошибку/с.

1. "Крускала"

2. "причинный"

   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 

Answer 1

Если вы перечитывали спецификации, вы найдете там две ошибки:

• на википедии, они используют индексы, начиная от 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); 
    } 
}