# # Edit Distance # # # Dynamic programming solution: basic, recursive implementation # def edit_distance(A,B): return ED(A,B,0,0) def ED(A, B, i, j): if i == len(A): return len(B) - j if j == len(B): return len(A) - i if A[i] == B[j]: c = 0 else: c = 1 return min(ED(A, B, i + 1, j + 1) + c, # change ED(A, B, i, j + 1) + 1, # insert ED(A, B, i + 1, j) + 1) # delete # # Efficient recursive implementation using "memoization" # def edit_distance_mem(A,B): return ED_mem(A,B,0,0,{}) def ED_mem(A,B,i,j,M): if (i,j) in M: # If we have the solution in cache (M) return M[(i,j)] # that is what we return. Otherwise if i == len(A): # we compute the solution. return len(B) - j if j == len(B): return len(A) - i d = min(ED_mem(A, B, i + 1, j + 1, M) + (0 if A[i] == B[j] else 1), # change ED_mem(A, B, i, j + 1, M) + 1, # insert ED_mem(A, B, i + 1, j, M) + 1) # delete M[(i,j)] = d # we "memoize" the solution return d # # Efficient, iterative solution # def edit_distance_itr(A, B): n = len(A) m = len(B) D = [0]*(n+1) # Distances at level j in B D_prev = [0]*(n+1) # Distances at level j - 1 in B for i in range(n+1): D[i] = i for j in range(1, m+1): D, D_prev = D_prev, D D[0] = D_prev[0] + 1 for i in range(1, n + 1): D[i] = min(D_prev[i] + 1, D[i - 1] + 1, D_prev[i - 1] + (0 if A[i-1] == B[j-1] else 1)) return D[n]