Algorytm Wagnera Fischera + etapy wyświetlania

Question

Wprowadziłem implementację algorytmu Wagnera Fischera w java z kosztem wejściowym, ale chcę wyświetlić wszystkie kroki. Szukam, ale nie mogę znaleźć żadnego pomysłu. Po długim czasie starałem się zachować każdą transformację w macierzy wraz z kosztami i przejść do pierwszego rozwiązania, a następnie odwrócić ... czy to dobry pomysł, jeśli tak, to jak czy powinienem ustawić warunek?

kitten -> sitting 
 
1.replace k with s 
 
2.keep i 
 
3.keep t 
 
4.keep t 
 
5.replace t 
 
6.add g

Próbowałem zrobić funkcję wyświetlania na schodach i nie może dowiedzieć się, jak go rozwiązać.

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.Scanner; 

public class Principal { 
    static int c1, c2, c3; 
    static String word1, word2; 

    public static void main(String[] args) throws FileNotFoundException { 
     Scanner data_in = new Scanner(new File("data.in")); 
     word1 = data_in.next(); 
     word2 = data_in.next(); 
     c1 = data_in.nextInt(); 
     c2 = data_in.nextInt(); 
     c3 = data_in.nextInt(); 

     System.out.printf("\nInsert: %s, Delete: %s, Replace: %s\n", c1, c2, c3); 

     System.out.printf("\nLevenstheinDistance: %s", LevenshteinDistance(word1, word2, c1, c2, c3)); 
    } 

    private static int LevenshteinDistance(String str1, String str2, int InsCost, int DelCost, int ReplCost) 
    { 
     if(word1.length() == 0) 
      return InsCost*str1.length(); 
     if(word2.length() == 0) 
      return DelCost*str2.length(); 

     int substitutionCost = ReplCost; 
     if(ReplCost > InsCost + DelCost) 
      ReplCost = InsCost + DelCost; 

     Solution[][] ManageSol = new Solution[str1.length()+1][str2.length()+1]; 

     for(int i = 0; i <= str1.length(); i++) 
     { 
      for(int j = 0; j <= str2.length(); j++){ 
       ManageSol[i][j] = new Solution(); 
      } 
     } 

     System.out.printf("\nLungime str1: %s", str1.length()); 
     System.out.printf("\nLungime str2: %s", str2.length()); 

     for(int i = 0; i <= str1.length(); i++) 
     { 
      for (int j = 0; j <= str2.length(); j++) 
      { 
       if (i == 0) 
        ManageSol[i][j].solution = j; 
       else if (j == 0) 
        ManageSol[i][j].solution = i; 
       else if (str1.charAt(i - 1) == str2.charAt(j - 1)) 
       { 
        substitutionCost = 0; 
        ManageSol[i][j].ecqualTo(minimum(
          ManageSol[i][j - 1].solution + InsCost, 
          ManageSol[i - 1][j].solution + DelCost, 
          ManageSol[i - 1][j - 1].solution + substitutionCost)); 
        System.out.printf("\nManagerSol[%s, %s]: ch1: %s, ch2: %s", i, j, str1.charAt(i - 1), str2.charAt(j - 1)); 
       } 
       else 
       { 
        substitutionCost = 1; 
        ManageSol[i][j].ecqualTo(minimum(
          ManageSol[i][j - 1].solution + InsCost, 
          ManageSol[i - 1][j].solution + DelCost, 
          ManageSol[i - 1][j - 1].solution + substitutionCost)); 
        System.out.printf("\nManagerSol[%s, %s]: ch1: %s, ch2: %s", i, j, str1.charAt(i - 1), str2.charAt(j - 1)); 
       } 
      } 
     } 

     System.out.printf("\n"); 
     path(ManageSol, str1.length(), str2.length(), str1, str2); 
     System.out.printf("\n"); 

     for(int i = 0; i <= str1.length(); i++) 
     { 
      for (int j = 0; j <= str2.length(); j++) 
      { 
       System.out.printf("[%s,%s]:(%s,%s) ", i, j, ManageSol[i][j].solution, ManageSol[i][j].operation); 
      } 
      System.out.printf("\n"); 
     } 

     return ManageSol[str1.length()][str2.length()].solution; 
    } 

    static int minimum(int x, int y) 
    { 
     if(x >= y) 
      return x; 
     return y; 
    } 

    static Solution minimum(int Ins, int Del, int Replace) 
    { 

     Solution solution = null; 
     if(Ins <= Del && Ins <= Replace) 
     { 
      solution = new Solution(); 
      solution.operation = 1; 
      solution.solution = Ins; 
      return solution; 
     } 
     else if(Del <= Ins && Del <= Replace) 
     { 
      solution = new Solution(); 
      solution.operation = 2; 
      solution.solution = Del; 
      return solution; 
     } 
     else 
     { 
      solution = new Solution(); 
      solution.solution = Replace; 
      solution.operation = 0; 
      return solution; 
     } 
    } 

    //my failure, function that should display steps 
    static void path(Solution[][] ManagerSol, int i, int j, String str1, String str2) 
    { 
     if(ManagerSol[i][j].operation == 0) 
     { 
      System.out.printf("\nReplace %s -> %s", str1.charAt(i-1), str2.charAt(j-1)); 
      if(i > 1 && j > 1) 
       path(ManagerSol, i-1,j-1, str1, str2); 
     } 
     if(ManagerSol[i][j].operation == 1) 
     { 
      System.out.printf("\nAdd %s on position %s", str2.charAt(j-1), i-1); 
      if(j > 1) 
       path(ManagerSol, i,j-1, str1, str2); 
     } 
     if(ManagerSol[i][j].operation == 2) 
     { 
      System.out.printf("\nDelete %s", str1.charAt(i-1)); 
      if(j > 1) 
       path(ManagerSol, i-1,j, str1, str2); 
     } 
    } 
} 

Wyjście dla kociaka do posiedzenia:

[0,0]:(0,3) [0,1]:(1,3) [0,2]:(2,3) [0,3]:(3,3) [0,4]:(4,3) [0,5]:(5,3) [0,6]:(6,3) [0,7]:(7,3) 
 
[1,0]:(1,3) [1,1]:(1,0) [1,2]:(2,1) [1,3]:(3,1) [1,4]:(4,1) [1,5]:(5,1) [1,6]:(6,1) [1,7]:(7,1) 
 
[2,0]:(2,3) [2,1]:(2,2) [2,2]:(1,0) [2,3]:(2,1) [2,4]:(3,1) [2,5]:(4,1) [2,6]:(5,1) [2,7]:(6,1) 
 
[3,0]:(3,3) [3,1]:(3,2) [3,2]:(2,2) [3,3]:(1,0) [3,4]:(2,1) [3,5]:(3,1) [3,6]:(4,1) [3,7]:(5,1) 
 
[4,0]:(4,3) [4,1]:(4,2) [4,2]:(3,2) [4,3]:(2,2) [4,4]:(1,0) [4,5]:(2,1) [4,6]:(3,1) [4,7]:(4,1) 
 
[5,0]:(5,3) [5,1]:(5,2) [5,2]:(4,2) [5,3]:(3,2) [5,4]:(2,2) [5,5]:(2,0) [5,6]:(3,1) [5,7]:(4,1) 
 
[6,0]:(6,3) [6,1]:(6,2) [6,2]:(5,2) [6,3]:(4,2) [6,4]:(3,2) [6,5]:(3,2) [6,6]:(2,0) [6,7]:(3,1)

Answer 1

Nie jestem biegły w języku Java, ale tutaj jest ilustracją w JavaScript:

var a = 'kitten', 
 
    b = 'sitting'; 
 

 
var m = new Array(a.length + 1); 
 

 
for (var i=0; i<m.length; i++){ 
 
    m[i] = new Array(b.length + 1); 
 
    
 
    for (var j=0; j<m[i].length; j++){ 
 
    if (i === 0) m[i][j] = j; 
 
    if (j === 0) m[i][j] = i; 
 
    } 
 
} 
 

 
for (var i=1; i<=a.length; i++){ 
 
    for (var j=1; j<=b.length; j++){ 
 

 
    // no change needed 
 
    if (a[i - 1] === b[j - 1]){ 
 
     m[i][j] = m[i - 1][j - 1]; 
 
    
 
    // choose deletion or insertion 
 
    } else { 
 
     m[i][j] = Math.min(m[i - 1][j], m[i][j - 1], m[i - 1][j - 1]) + 1; 
 
    } 
 
    } 
 
} 
 

 
console.log('a: ' + JSON.stringify(a)); 
 
console.log('b: ' + JSON.stringify(b)); 
 

 
var i = a.length, 
 
    j = b.length, 
 
    steps = ''; 
 
    
 
while (i !== 0 && j !== 0){ 
 
    if (a[i - 1] === b[j - 1]){ 
 
    steps = 'no change; ' + steps; 
 
    i--; 
 
    j--; 
 
    
 
    } else if (m[i - 1][j] < m[i][j - 1]){ 
 
    steps = 'delete \'' + a[i - 1] + '\'; ' + steps; 
 
    i--; 
 
    
 
    } else if (m[i - 1][j] === m[i][j - 1]){ 
 
    steps = 'replace \'' + a[i - 1] + '\' with \'' + b[j - 1] + '\'; ' + steps; 
 
    i--; 
 
    j--; 
 
    
 
    } else { 
 
    steps = 'insert \'' + b[j - 1] + '\'; ' + steps; 
 
    j--; 
 
    } 
 
} 
 

 
if (i === 0 && j > 0){ 
 
    steps = 'insert first ' + j + ' elements from b; ' + steps; 
 
    
 
} else if (j === 0 && i > 0){ 
 
    steps = 'delete first ' + i + ' elements from a; ' + steps; 
 
} 
 

 
console.log('\n' + steps[0].toUpperCase() + steps.substr(1)); 
 

 
console.log('\nMatrix:\n'); 
 

 
for (var i in m){ 
 
    console.log(JSON.stringify(m[i])); 
 
}

Answer 2

Generalnie Twój pomysł jest poprawne. To jeszcze prostsze. Nie musisz przechowywać żadnych dodatkowych informacji.

można cofnąć (począwszy od końca podanych ciągów) i korzystać z dynamicznych wartości programowania w następujący sposób:

1. Jeśli jeden ze wskaźników ma wartość 0, istnieje tylko jeden sposób, aby udać się.

2. W przeciwnym razie można spojrzeć na 3 możliwe przejścia "w tył" (od (i, j) do (i - 1, j - 1), (i - 1, j) i (i, j - 1)) i wybierz ten, który daje faktyczną wartość dla (i, j). Jeśli istnieje kilka możliwych opcji, możesz wybrać dowolne z nich.

Gdy już wiesz, gdzie przejść z danej pary pozycji, operacja jest jednoznacznie określona.