ML & NLP home

Computing Minimum Edit Distance - D(n,m)

Using Dynamic Programming

Consider 2 strings X (length=m), Y (length=n)
The psuedo-code can be written as:

For each i in X: For each j in Y: D(i,j) = min( D(i-1,j) + 1 , D(1,j-1) + 1 , D(i-1,j-1) + 2 )