6
मैंने इनपुट लागत के साथ जावा में वैगनर फिशर एल्गोरिदम का कार्यान्वयन किया, लेकिन मैं सभी चरणों को प्रदर्शित करना चाहता हूं। मैं खोजता हूं लेकिन कोई विचार नहीं ढूंढ सकता। लंबे समय बाद मैंने लागत के साथ मैट्रिक्स में प्रत्येक परिवर्तन को रखने की कोशिश की और पहले समाधान पर वापस जाने की कोशिश की, फिर इसे उलट दें ... क्या यह एक अच्छा विचार है, अगर यह है, तो यह कैसे है क्या मुझे शर्त तय करनी चाहिए?वैगनर फिशर एल्गोरिदम + डिस्प्ले चरण
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: %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);
}
}
}
आउटपुट:
[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)
Offtopic: आप जावा नामकरण सम्मेलनों के बारे में पढ़ना चाहते हैं - चर नाम CamelCase जाना; केवल वर्ग के नाम अपरकेस शुरू करते हैं। आप "अमूर्तता की एकल परत" सिद्धांत के बारे में भी पढ़ना चाहते हैं; आप कोड से बहुत फायदा उठा सकते हैं। लेकिन इसके अलावा: अच्छा पहला सवाल; विशेष रूप से तथ्य यह है कि आपने अपने सभी कोड को स्वरूपित/इंडेंट किया है ... हालांकि मुझे यह महसूस हो रहा है कि लोगों को यह प्रश्न बहुत व्यापक लगेगा ... – GhostCat
सलाह के लिए धन्यवाद, मैं इसे ध्यान में रखूंगा – Jarlio