La distance proposée est naïve puisqu'elle considère uniquement les lettres communes entre deux mots.
$m =\{ c_1, ..., c_n\}$
$C = m_1 \cap m_2$
$d(m_1,m_2)=\#\{c \in m_1 \backslash C\} + \#\{c \in m_2 \backslash C\}$
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 < < < < < < ^ = < < < < < ^ ^ \ < < < < ^ ^ ^ = < < < ^ ^ = ^ \ < < ^ ^ ^ ^ = < < ^ ^ ^ ^ ^ = < ^ ^ ^ ^ ^ ^ =