levenshtein_distance.py

def levenshtein(chaine1, chaine2):
    n = len(chaine1)
    m = len(chaine2)
    d = [[0 for j in range(m + 1)] for i in range(n + 1)]
    for i in range(0, n + 1):
        d[i][0] = i
    for j in range(0, m + 1):
        d[0][j] = j
    for i in range(0, n):
        for j in range(0, m):
            if chaine1[i] == chaine2[j]:
                cout_sub = 0
            else:
                cout_sub = 1
            d[i + 1][j + 1] = min(
                d[i][j + 1] + 1,
                d[i + 1][j] + 1,
                d[i][j] + cout_sub,
            )
    return d[n][m]