Wagner Fisher Algorithm + Display Steps

Question

I implemented the Wagner Fisher algorithm in java with input cost, but I want to show all the steps. I am looking, but can not find any idea. After a long time, I tried to save each transformation in the matrix along with the costs and move on to the first solution and then cancel it ... is it a good idea, if so, how should I set the condition?

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

I tried to make a function for the display steps and cannot figure out how to solve it.

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

Conclusion for sitting a kitten:

 [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

I do not understand Java, but here is an illustration in 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

In general, your idea is true. It is even easier. You do not need to store additional information.

You can go back (starting at the end of the line) and use your dynamic programming values ​​as follows:

• If one of the indices is 0, there is only one way.

• Otherwise, you can look at 3 possible transitions "back" (from (i, j) to (i - 1, j - 1), (i - 1, j) and (i, j - 1)) and select the one which gives the actual value for (i, j). If there are several possible options, you can choose any of them.

As soon as you know where to go from a given pair of positions, the operation is uniquely determined.