From 5213d148a9fadbd0b7425e8c08298e9e74785d9f Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Tue, 6 Aug 2013 00:27:14 +0200 Subject: Adding some comments --- string_utils.py | 38 ++++++++++++++++++++++++-------------- 1 file changed, 24 insertions(+), 14 deletions(-) diff --git a/string_utils.py b/string_utils.py index 64bd7b0..3db0a47 100644 --- a/string_utils.py +++ b/string_utils.py @@ -86,22 +86,32 @@ def align(l1, l2): for i in xrange(1, n + 1): a[i][0] = i * del_cost1, [-1] * i + for j in xrange(1, m + 1): - s1, a1 = a[i-1][j-1] + l = [] # contains the different options + + # mapping l1[i-1] to l2[j-1] + s, b = a[i-1][j-1] d = levenshtein(l1[i-1], l2[j-1]) - s2, a2 = a[i-1][j] - s3, a3 = a[i][j-1] - l = [(s1 + w * d, a1 + [j-1]), - (s2 + del_cost1, a2 + [-1]), - (s3 + del_cost2, a3)] - if (j >= 2): - s4, a4 = a[i-1][j-2] - d2 = levenshtein(l1[i-1], join_words(l2[j-2:j])) - l += [(s4 + w * d2, a4 + [(j-2, j-1)])] - if (i >= 2): - s5, a5 = a[i-2][j-1] - d3 = levenshtein(join_words(l1[i-2:i]), l2[j-1]) - l += [(s5 + w * d3, a5 + [j-1, j-1])] + l.append((s + w * d, b + [j-1])) + + # deleting l1[i-1] + s, b = a[i-1][j] + l.append((s + del_cost1, b + [-1])) + + # deleting l2[j-1] + s, b = a[i][j-1] + l.append((s + del_cost2, b)) + + if (j >= 2): # mapping l1[i-1] to l2[j-2] + l2[j-1] + s, b = a[i-1][j-2] + d = levenshtein(l1[i-1], join_words(l2[j-2:j])) + l.append((s + w * d, b + [(j-2, j-1)])) + + if (i >= 2): # mapping l1[i-2]+l1[i-1] to l2[j-1] + s, b = a[i-2][j-1] + d = levenshtein(join_words(l1[i-2:i]), l2[j-1]) + l.append((s + w * d, b + [j-1, j-1])) a[i][j] = min(l, key=lambda x: x[0]) -- cgit v1.2.3-70-g09d2