def simple_make_table(s1, s2):
"""
Retourne le tableau des distances d'édition entres les préfixes de s1 et s2:
la case (i, j) contient la distance entre s1[0:i] et s2[0:j].
"""
n1 = len(s1)+1
n2 = len(s2)+1
table = [None] * n1
for i in range(0, n1):
table[i] = [0] * n2
for i in range(1, n1):
table[i][0] = i
for j in range(1, n2):
table[0][j] = j
for i in range(1, n1):
for j in range(1, n2):
if s1[i-1] == s2[j-1]:
e = 0
else:
e = 1
table[i] = min(table[i-1][j]+1, table[i][j-1]+1, table[i-1][j-1]+e)
return table
def simple_distance(s1, s2):
return simple_make_table(s1, s2)[len(s1)][len(s2)]
def make_table(s1, s2):
"""
Retourne le tableau des des tuples (d, p) où à la case (i, j) d est la distance
d'édition de s1[0:i] à s2[0:j] et p est une suite optimale d'opérations menant
de s1[0:i] à s2[0:j].
Les opérations sont codés sur trois caractères : "Oxy" ou O est le nom de
l'opération (I pour Insert, D pour Delete et M pour Mutation, N pour Noop,
aucune opération), x et y sont les paramètres de l'opération.
"""
n1 = len(s1)+1
n2 = len(s2)+1
table = [None] * n1
for i in range(0, n1):
table[i] = [0] * n2
table[0][0] = (0, [])
for i in range(1, n1):
o = "D%s " % s1[i-1]
table[i][0] = (i, [o])
for j in range(1, n2):
o = "I%s " % s2[j-1]
table[0][j] = (j, [o])
for i in range(1, n1):
c1 = s1[i-1]
for j in range(1, n2):
c2 = s2[j-1]
t = table[i-1][j-1]
if c1 == c2:
d = t[0]
o = "N "
p = t[1] + [o]
else:
d = t[0] + 1
o = "M%s%s" % (c1, c2)
p = t[1] + [o]
t = table[i-1][j]
d1 = t[0] + 1
if d1 < d:
d = d1
o = "D%s " % c1
p = t[1] + [o]
t = table[i][j-1]
d2 = t[0] + 1
if d2 < d:
d = d2
o = "I%s " % c2
p = t[1] + [o]
table[i][j] = (d, p)
return table
def print_table(s1, s2):
"""
Calcul la table des distances en appelant make_table et affiche celle-ci ;
retourne la table calculée.
"""
table = make_table(s1, s2)
n1 = len(s1)
n2 = len(s2)
table[0][0] = (0, [" "])
sep_line = "+" + ("-" * n1) + ("+" + "-" * max(n2, 6)) * (n2+1) + "+"
pad = " " * max(0, 6 - n2)
head_line = "|" + "|".join([" " * (n1)]
+ ["%s%s%s" % (pad, s2[0:j], " " * (n2-j))
for j in range(0, n2+1)]) + "|"
print sep_line
print head_line
print sep_line
pad = " " * max(n2 - 6, 0)
for i in range(0, n1+1):
line = "|" + "|".join(["%s%s" % (s1[0:i], " " * (n1-i))]
+ ["%s%s %2d" % (pad, table[i][j][1][-1],
table[i][j][0])
for j in range(0, n2+1)]) + "|"
print line
print sep_line
return table
def apply_ops(s, ops):
"""
Applique la liste d'opérations d'édition ops à la chaîne s ; si ops a été
calculée par make_table(s, s') alors ceci doit rendre s'.
"""
i = 0
goal = list(s)
for op in ops:
if op[0] == "M":
if goal[i] != op[1]:
raise ValueError("Invalid mutation: %s" % op)
goal[i] = op[2]
i += 1
elif op[0] == "D":
if goal[i] != op[1]:
raise ValueError("Invalid deletion: %s" % op)
goal[i:] = goal[i+1:]
elif op[0] == "I":
goal.insert(i, op[1])
i += 1
elif op[0] == "N":
i += 1
else:
raise ValueError("Invalid operation: %s" % op)
return "".join(goal)
while True:
s1 = raw_input("Entrer une chaîne : ")
s2 = raw_input("Et une autre : ")
if len(s1) == 0 or len(s2) == 0:
print
print "Entrer des chaînes non vides"
print
continue
print "Table des distances entre '%s' et '%s' :" % (s1, s2)
table = print_table(s1, s2)
ops = table[len(s1)][len(s2)][1]
print
print "Opérations à appliquer à '%s' pour obtenir '%s' :" % (s1, s2)
for op in ops[:-1]:
print "%s, " % op.strip(),
print ops[-1].strip()
print
print "Application des opérations à '%s'," % s1,
s3 = apply_ops(s1, ops)
print "ce qui donne : '%s'" % s3
print
answer = raw_input("Continuer (o/n) ? ")
if answer == "n" or answer == "N":
break