Here is a program assignment in JAVA. This program will implement the edit dista

Question

Here is a program assignment in JAVA. This program will implement the edit distance algorithm and apply it to the strings read from a file. And in the probelm, you need to implement substitution, insertion, deletion and transposition(wp---pw). They are all going have the cost equal to 1.(Transposition has a cost of 2 in the original algorithm, a deletion followed by an insertion, but it can make sense for a transposition to have a cost of 1) The program should read read lines from a file that can be specified as a command line argument. Each line from the file should be converted to an array of chars. You can store the the char arrays in arraylist. Then for each pair of char arrays, you can output the edit distance for the two arrays.

Substitution - Replace a single character from pattern P with a different character in text T, such as changing "shot" to "spot." Insertion Insert a single character into pattern P to help it match text T such as changing "ago" to "agog." Deletion - Delete a single character from pattern P to help it match text T, such as changing "hour" to "our."

Explanation / Answer

import java.util.*;
import java.io.*;  
class Editdistance
{
static int min(int x,int y,int z)
{
if (x<=y && x<=z) return x;
if (y<=x && y<=z) return y;
else return z;
}

static int editDist(String str1 , String str2 , int m ,int n)  
{
  
if (m == 0) return n;
  
  
if (n == 0) return m;
  

if (str1.charAt(m-1) == str2.charAt(n-1)) //calculating Editdistance
return editDist(str1, str2, m-1, n-1);
  

return 1 + min ( editDist(str1, str2, m, n-1), // Insert
editDist(str1, str2, m-1, n), // Remove
editDist(str1, str2, m-1, n-1) // Replace
);
}

public static void main(String args[]) throws Exception
{
File infile=null;
if(0<args.length){
infile=new File(args[0]);
}   
Scanner sc=new Scanner(infile).useDelimiter("\Z");

  

String def= sc.nextLine(); //reads 1st line in file and itself containing whole line
String def1=sc.nextLine(); //reads 2nd line in file.
int ans=editDist(def,def1,def.length(),def1.length());
System.out.println("edit distance is:"+ans);

  

}}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.