Levenshtein distance (Edit distance)

The edit distance of two strings, s1 and s2, is defined as the minimum number of point mutations required to change s1 into s2, where a point mutation is one of:

  1. replace a letter,
  2. insert a letter, or
  3. delete a letter

void Main()
{

}

class EditDistanceAlgo
{
 static int[,] m;
 public static char diagCh;
 public static int LevenshteinDistance(string first, string second)
 {
  int[,] map = new int[first.Length + 1, second.Length + 1];
  for (int i = 0; i <= first.Length; i++)
   map[i, 0] = i;
  for (int j = 0; j <= second.Length; j++)
   map[0, j] = j;
  for (int j = 1; j <= second.Length; j++)
   for (int i = 1; i <= first.Length; i++)
    if (first[i - 1] == second[j - 1])
     map[i, j] = map[i - 1, j - 1];  //no operation
    else
     map[i, j] = Math.Min(Math.Min(
      map[i - 1, j] + 1,    //a deletion
      map[i, j - 1] + 1),   //an insertion
      map[i - 1, j - 1] + 1 //a substitution
      );
  TraceBack("", "", "", map, first.Length, second.Length, first, second);
  return map[first.Length, second.Length];
 }
 public static void TraceBack(string row1, string row2, string row3, int[,] mm, int i, int j, string s1, string s2)
 {
  string result = "";
  if (i > 0 && j > 0)
  {
   var diag = mm[i - 1, j - 1];
   diagCh = '|';
   if (s1[i - 1] != s2[j - 1])
   {
    diag++; diagCh = ' ';
   }
   if (mm[i, j] == diag)
    TraceBack(s1[i - 1] + row1, diagCh + row2, s2[j - 1] + row3, mm, i - 1, j - 1, s1, s2);    // change or match
   else if (mm[i, j] == mm[i - 1, j] - 0 + 1) // delete
    TraceBack(s1[i - 1] + row1, ' ' + row2, '-' + row3, mm, i - 1, j, s1, s2);
   else
    TraceBack('-' + row1, ' ' + row2, s2[j - 1] + row3, mm, i, j - 1, s1, s2);      // insertion
  }
  else if (i > 0)
   TraceBack(s1[i - 1] + row1, ' ' + row2, '-' + row3, mm, i - 1, j, s1, s2);
  else if (j > 0)
   TraceBack('-' + row1, ' ' + row2, s2[j - 1] + row3, mm, i, j - 1, s1, s2);
  else // i==0 and j==0
   result += row1 + '\n' + row2 + '\n' + row3 + '\n';
  Console.WriteLine(result);
 }//traceBack
}
Reactions

Post a Comment

0 Comments

Close Menu