Distance d'édition (Levenshtein)

Soit $D(i,j)$ la distance entre $X[\mathrm{0..}i]$ et $Y[\mathrm{0..}j]$. Si les derniers caractères sont égaux, $D(i,j)=D(i-1,j-1)$ ; sinon on prend le minimum des trois opérations, augmenté de 1.

def distance_edition(X, Y):
    n, m = len(X), len(Y)
    table = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        table[i][0] = i
    for j in range(m + 1):
        table[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if X[i - 1] == Y[j - 1]:
                table[i][j] = table[i - 1][j - 1]
            else:
                table[i][j] = 1 + min(
                    table[i - 1][j],      # suppression
                    table[i][j - 1],      # insertion
                    table[i - 1][j - 1]   # substitution
                )
    return table[n][m]

La complexité est $O(n\times m)$.