La distance d'édition (Levenshtein)

(a) Soit $D(i,j)$ la distance entre le préfixe de taille $i$ de $u$ et le préfixe de taille $j$ de $v$. $$D(i,0)=i,D(0,j)=j$$ $$D(i,j)=\min \{\begin{array}{ll}D(i-1,j)+1& \text{(suppression du caracteˋre de }u\text{)}\\ D(i,j-1)+1& \text{(insertion d’un caracteˋre dans }u\text{)}\\ D(i-1,j-1)+\text{cout}& \text{(substitution, avec cout = 0 si }{u}_i=v_j\text{, 1 sinon)}\end{array}$$ (b)

def levenshtein(u: str, v: str) -> int:
    n, m = len(u), len(v)
    D = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        D[i][0] = i
    for j in range(m + 1):
        D[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cout = 0 if u[i - 1] == v[j - 1] else 1
            D[i][j] = min(D[i - 1][j] + 1,      # suppression
                          D[i][j - 1] + 1,      # insertion
                          D[i - 1][j - 1] + cout) # substitution
    return D[n][m]

assert levenshtein("CHAT", "CHIEN") == 3

Les 3 opérations minimales sont : substitution de A par I, substitution de T par E, et insertion de N. (c) Utilisée dans les correcteurs orthographiques (recherche de mots proches d'une saisie erronée) et en bio-informatique (alignement de séquences d'ADN pour mesurer la parenté entre deux gènes).