In [ ]:
 
In [1]:
import numpy as np
In [116]:
def min_edit_distance(source, target):
    
    n = len(source)
    m = len(target)
    
    D = np.zeros((n+1, m+1))
    
    D[:, 0] = range(n+1)
    D[0, :] = range(m+1)
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            dc = D[i-1, j] + 1
            ic = D[i, j-1] + 1
            if source[i-1] == target[j-1]:
                sc = D[i-1, j-1]
            else:
                sc = D[i-1, j-1] + 2
            D[i, j] = min(dc, ic, sc)
    print(D)
    return D[n, m]
In [117]:
s = "intention"
t = "execution"
In [118]:
min_edit_distance(s, t)
[[ 0.  1.  2.  3.  4.  5.  6.  7.  8.  9.]
 [ 1.  2.  3.  4.  5.  6.  7.  6.  7.  8.]
 [ 2.  3.  4.  5.  6.  7.  8.  7.  8.  7.]
 [ 3.  4.  5.  6.  7.  8.  7.  8.  9.  8.]
 [ 4.  3.  4.  5.  6.  7.  8.  9. 10.  9.]
 [ 5.  4.  5.  6.  7.  8.  9. 10. 11. 10.]
 [ 6.  5.  6.  7.  8.  9.  8.  9. 10. 11.]
 [ 7.  6.  7.  8.  9. 10.  9.  8.  9. 10.]
 [ 8.  7.  8.  9. 10. 11. 10.  9.  8.  9.]
 [ 9.  8.  9. 10. 11. 12. 11. 10.  9.  8.]]
Out[118]:
8.0
In [ ]:
 
In [ ]: