Алгоритм Вагнера Фишера + шаги отображения
Я сделал реализацию алгоритма Вагнера Фишера в java с входной стоимостью, но я хочу отобразить все шаги.
Я ищу, но не могу найти никакой идеи.После долгого времени я пытался сохранить каждое преобразование в матрице наряду с затратами и вернуться к первому решению, а затем повернуть его вспять... является ли это хорошей идеей, если это так, как я должен установить условие?
kitten -> sitting
1.replace k with s
2.keep i
3.keep t
4.keep t
5.replace t
6.add gЯ пытался сделать функцию для отображения шагов и не могу понять, как ее решить.
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: %sn", 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);
}
}
}
Вывод для котенка к сидению:
[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) 2 ответов:
Я не разбираюсь в Java, но вот иллюстрация в 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])); }
В целом ваша идея верна. Все гораздо проще. Вам не нужно хранить дополнительную информацию.
Можно вернуться назад (начиная с конца заданных строк) и использовать значения динамического программирования следующим образом:
Если один из индексов равен 0,то есть только один путь.
В противном случае вы можете посмотреть на 3 возможных перехода "назад" (от (i, j) к (i-1, j-1), (i-1, j) и (i, j - 1)) и выбрать тот, который дает действительное значение для (i, j). Если есть несколько возможных вариантов, вы можете выбрать любой из них.
Как только вы знаете, куда идти из данной пары позиций, операция определяется однозначно.
Comments