1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
| def min_edit_distance(source, target, ins_cost = 1, del_cost = 1, rep_cost = 2): ''' Input: source: a string corresponding to the string you are starting with target: a string corresponding to the string you want to end with ins_cost: an integer setting the insert cost del_cost: an integer setting the delete cost rep_cost: an integer setting the replace cost Output: D: a matrix of len(source)+1 by len(target)+1 containing minimum edit distances med: the minimum edit distance (med) required to convert the source string to the target ''' m = len(source) n = len(target) D = np.zeros((m+1, n+1), dtype=int) for row in range(1, m + 1): D[row,0] = D[row - 1, 0] + del_cost for col in range(1, n + 1): D[0,col] = D[0, col - 1] + ins_cost for row in range(1, m + 1): for col in range(1, n + 1): r_cost = rep_cost if source[row - 1] == target[col - 1]: r_cost = 0 D[row,col] = min(min(D[row, col - 1] + ins_cost, D[row - 1, col] + del_cost), D[row - 1, col - 1] + r_cost) med = D[m, n] return D, med
|