2023-10-09

Edit Distance

Questions

[!question]- Define Edit Distance Minimum number of insert/delete/replace operation needed to convert one string to the other

[!question]- What are the possible operations in calculating edit distance Insert, delete, substitute

[!question]- Give the algorithm for Levenshtein distance

int edit_distance(string a, string b)
{
 char mat[len(a)][len(b)];
 mat[0][0] = 0;
 for i = 1 to len(a){
 	mat[i][0] = i;
 }
 for i = 1 to len(a){
 	mat[0][i] = i;
 }
 for i = 1  to len(a){
 	for j = 1 to len(b) {
 		mat[i][j] = min(
 					mat[i-1][j-1] + 0 if (a[i] == b[j]) else 1,
 					mat[i-1][j]+1,
 					mat[i][j-1]+1
 		)
 	}
 }
 return mat[len(a)][len(b)]
}