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
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.
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.
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.
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
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)
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)
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)