<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Algo - distance d'édiction
La distance d'édition ou distance de Levenshtein permet de calculer une distance entre deux mots et par extension entre deux séquences.
Step1:  Enoncé
Q1 
Step2:  On vérifie que la fonctionne jette bien une exception lorsque les chaînes de caractères sont de longueurs différentes.
Step3:  Q2 
Step4:  Q3 
Step5:  Q4 
Step6:  La seconde version est plus alambiquée, elle modifie légèrement la version alambiquée. C'est une version récursive.
<ASSISTANT_TASK:>
Python Code:
from jyquickhelper import add_notebook_menu
add_notebook_menu()
%matplotlib inline
Explanation: Algo - distance d'édiction
La distance d'édition ou distance de Levenshtein permet de calculer une distance entre deux mots et par extension entre deux séquences.
End of explanation
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')
Explanation: 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
Levenshtein
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.
End of explanation
try:
    distance_meme_longueur('a', 'bb')
except Exception as e:
    print(e)
Explanation: On vérifie que la fonctionne jette bien une exception lorsque les chaînes de caractères sont de longueurs différentes.
End of explanation
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')
Explanation: 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.
End of explanation
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'))
Explanation: 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.
End of explanation
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')
Explanation: Q4 : implémenter l'algorithme de la page wikipedia
Levenshtein
La première implémentation reprend l'algorithme décrit sur la page wikipédia.
End of explanation
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'))
Explanation: La seconde version est plus alambiquée, elle modifie légèrement la version alambiquée. C'est une version récursive.
End of explanation
<END_TASK>