2018-09-25 - Distance entre mots

Links: notebook, html, python, slides, GitHub

La distance proposée est naïve puisqu’elle considère uniquement les lettres communes entre deux mots.

Un indice pour l’implémenter : il peut être utile de passer par les dictionnaires.

def compte(mot):
    d = {}
    for c in mot:
        d[c] = d.get(c, 0) + 1
    return d

compte("aza")

{'a': 2, 'z': 1}

def distance_simple(h1, h2):
    d = 0
    tout = set(h1).union(set(h2))
    for c in tout:
        d += abs(h1.get(c, 0) - h2.get(c, 0))
    return d

distance_simple(compte("journal"), compte("journaux"))

3

distance_simple(compte("journal"), compte("naljour"))

0

La distance ne tient pas compte de l’ordre des lettres, on en tient compte de façon locale en considèrent les couples de lettres consécutives plutôt que les lettres.

def decoupe(mot):
    couples = []
    for i in range(1, len(mot)):
        couples.append(mot[i-1:i+1])
    return [mot[:1]] + couples + [mot[-1:]]
decoupe("journal")

['j', 'jo', 'ou', 'ur', 'rn', 'na', 'al', 'l']

Mais ce n’est pas une distance à proprement parler comme en témoigne le contre-exemple suivant :

distance_simple(compte(decoupe("ninon")),
                compte(decoupe("nonin")))

0

distance_simple(compte(decoupe("journal")),
                compte(decoupe("jourinal")))

3

distance_simple(compte(decoupe("journal")),
                compte(decoupe("naljour")))

6

On passe alors à la distance d’édition :

def distance_edition(m1, m2):
    mat = [[len(m1) + len(m2) for j in range(len(m2))] for i in range(len(m1))]
    drt = [["n" for j in range(len(m2))] for i in range(len(m1))]
    mat[0][0] = 0 if m1[0] == m2[0] else 1
    for i in range(len(m1)):
        for j in range(len(m2)):
            if i > 0 and mat[i][j] > mat[i-1][j] + 1:
                mat[i][j] = mat[i-1][j] + 1
                drt[i][j] = "^"
            if j > 0 and mat[i][j] > mat[i][j-1] + 1:
                mat[i][j] = mat[i][j-1] + 1
                drt[i][j] = "<"
            if i > 0 and j > 0:
                c = 0 if m1[i] == m2[j] else 1
                if mat[i][j] > mat[i-1][j-1] + c:
                    mat[i][j] = mat[i-1][j-1] + c
                    drt[i][j] = "=" if c == 0 else "\\"
    return mat[len(m1)-1][len(m2)-1], drt

d, drt = distance_edition("jourinal", "joirnal")
d

2

Pour retrouver le chemin, il suffit de remonter le chemin suivant depuis l’arrivée jusqu’au point de départ.

for l in drt:
    print(" ".join(l))

n < < < < < <
^ = < < < < <
^ ^ < < < <
^ ^ ^ = < < <
^ ^ = ^ < <
^ ^ ^ ^ = < <
^ ^ ^ ^ ^ = <
^ ^ ^ ^ ^ ^ =