Edit Distance Problem
Source: http://people.csail.mit.edu/bdean/6.046/dp/
Problem:
Problem:
Given two text strings A of length n and B of length m, you want to transform A into B with a minimum number of operations of the following types: delete a character from A, insert a character into A, or change some character in A into a new character. The minimal number of such operations required to transform A into B is called the edit distance between A and B.
Given two strings A and B, what is the path from A to B with minimum edit distance?
Given two strings A and B, what is the path from A to B with minimum edit distance?
I think it will be Levenshtein distance if the distance for insertion is same for all character pairs[replacing A with B has same cost as replacing A with G] else Dynamic Time Warp Distance.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteInitial Condition: Edit distance for m = 0 , n= 0 is 0 ie (0,0) = 0
ReplyDeletefor each (i,j) where i belongs to m and j belongs to n
check = min { i.(i - 1 , j- 1) + cost of replacement of ith and jth element(here if a[i] == b[j] then the cost will be zero)
ii.(i,j-1) + cost of insertion of the jth element
iii.(i-1,j) + cost of the insertion of the ith element
}
This problem if solved recursively will take exponential time however can be done in O(m*n) by using dynamic programming with additional O(m*n) spaces.
eg: APPLE and CAPE
Considering the cost of addition, deletion or replacement is each 1.
A P P L E
C 1 2 3 4 5
A 1 2 3 4 5
P 2 1 2 3 4
E 3 3 2 3 3
Space Optimization:
The problem can be further optimized for space by using only the last array. Thus, only additional space required will be 2* min(m,n).