Algo - distance d’édiction#
Links: notebook, html, python, slides, GitHub
La distance d’édition ou distance de Levenshtein permet de calculer une distance entre deux mots et par extension entre deux séquences.
from jyquickhelper import add_notebook_menu
add_notebook_menu()
%matplotlib inline
Enoncé#
Q1 : Distance simple entre deux mots de même longueur#
Une distance entre deux mots… c’est plus simple si les deux mots ont la même longueur, on calcule le nombre de différences.
Q2 : Distance simple entre deux mots de longueur différente#
On construit cette distance comme la différence des longueurs + la distance entre le mot le plus court et toutes les sous-séquences de même longueur issues de la chaîne la plus longue.
Q3 : Distance alambiquée…#
Cette fois-ci, on coupe chacun des deux mots en deux, au hasard. On applique la distance précédente sur chacun des deux tronçons. On fait la somme. Il ne reste plus qu’à minimiser cette somme sur l’ensemble des coupures possibles.
Q4 : implémenter l’algorithme de la page wikipedia#
Réponses#
Q1 : Distance simple entre deux mots de même longueur#
Une distance entre deux mots… c’est plus simple si les deux mots ont la même longueur, on calcule le nombre de différences.
def distance_meme_longueur(m1, m2):
if len(m1) != len(m2):
raise ValueError("m1 et m2 sont de longueurs différentes")
d = 0
for c1, c2 in zip(m1, m2):
if c1 != c2:
d += 1
return d
distance_meme_longueur('abcef', 'abcde')
2
On vérifie que la fonctionne jette bien une exception lorsque les chaînes de caractères sont de longueurs différentes.
try:
distance_meme_longueur('a', 'bb')
except Exception as e:
print(e)
m1 et m2 sont de longueurs différentes
Q2 : Distance simple entre deux mots de longueur différente#
On construit cette distance comme la différence des longueurs + la distance entre le mot le plus court et toutes les sous-séquences de même longueur issues de la chaîne la plus longue.
def distance(m1, m2):
if len(m1) < len(m2):
return distance(m2, m1)
if len(m1) == len(m2):
return distance_meme_longueur(m1, m2)
d = len(m1) - len(m2)
mind = [distance_meme_longueur(m1[i:i+len(m2)], m2)
for i in range(0, d)]
return d + min(mind)
distance('aa', 'aa'), distance('aa', 'aaa'), distance('aa', 'bbb')
(0, 1, 3)
Q3 : Distance alambiquée…#
Cette fois-ci, on coupe chacun des deux mots en deux, au hasard. On applique la distance précédente sur chacun des deux tronçons. On fait la somme. Il ne reste plus qu’à minimiser cette somme sur l’ensemble des coupures possibles.
def distance_alambiquee(m1, m2):
mini = None
for i in range(len(m1)):
for j in range(len(m2)):
d = distance(m1[:i], m2[:j]) + distance(m1[i:], m2[j:])
if mini is None or d < mini:
mini = d
# Option verlan
d = distance(m1[:i], m2[j:]) + distance(m1[i:], m2[:j]) + 0.5
if d < mini:
mini = d
return mini
(distance('abc', 'ac'),
distance_alambiquee('abc', 'ac'),
distance_alambiquee('abc', 'ca'),
distance_alambiquee('b', 'b'))
(2, 1, 1.5, 0)
Q4 : implémenter l’algorithme de la page wikipedia#
La première implémentation reprend l’algorithme décrit sur la page wikipédia.
def levenstein(m1, m2):
d = {}
d[0,0] = 0
for i in range(len(m1) + 1):
d[i, 0] = i
for j in range(len(m2) + 1):
d[0, j] = j
for i in range(1, len(m1) + 1):
for j in range(1, len(m2) + 1):
d[i, j] = min(d[i-1,j] +1, d[i,j-1] +1,
d[i-1, j-1] + (1 if m1[i-1] != m2[j-1] else 0))
return d[len(m1), len(m2)]
levenstein('abc', 'ac')
1
La seconde version est plus alambiquée, elle modifie légèrement la version alambiquée. C’est une version récursive.
def distance_alambiquee_levenstein(m1, m2):
mini = None
for i in range(len(m1)):
for j in range(len(m2)):
if i > 0 and i < len(m1) - 1 and j > 0 and j < len(m2) - 1:
d1 = distance_alambiquee_levenstein(m1[:i], m2[:j])
d2 = distance_alambiquee_levenstein(m1[i:], m2[j:])
else:
d1 = distance(m1[:i], m2[:j])
d2 = distance(m1[i:], m2[j:])
d = d1 + d2
if mini is None or d < mini:
mini = d
return mini
(distance_alambiquee('abcde', 'ace'),
levenstein('abcde', 'ace'),
distance_alambiquee_levenstein('abcde', 'ace'))
(3, 2, 2)