Bureau d'étude PEIP - IS

TP5 - Distance entre deux mots

Comment définir la distance entre deux mots ? C'est à dire mesurer la similartié entre deux mots, définir à quel points ils sont semblables ? Dans ce TP, on s'intéresse à ce problème.

Distance Euclidienne

La façon la plus simple de calculer la distance entre deux vecteurs (si on suppose qu'on peut représenter les mots par des vecteurs) est d'utiliser la distance euclidienne. Elle se définit comme la racine de la somme des différences des coordonnées des vecteurs au carré :

Implémentez une fonction prenant en paramètre deux vecteurs x et y et renvoyant leur distance euclienne.

Distance cosinus

Il se trouve que la distance euclidienne est loin d'être la plus pertinente en traitement automatique de langue. On préfère souvent utiliser la distance cosinus. La similarité cosinus donne la similarité de deux vecteurs à n dimensions en déterminant le cosinus de leur angle. Soit deux vecteurs A et B, le cosinus de leur angle θ s'obtient en prenant leur produit scalaire divisé par le produit de leurs normes :

Implémentez une fonction qui calcule la norme d'un vecteur, puis une autre qui calcule le produit scalaire de deux vecteurs. Proposez ensuite une fonction prenant en paramètre deux vecteurs x et y et renvoyant leur distance cosinus.

Distance de Levenshtein

On appelle distance de Levenshtein entre deux chaînes M et P le coût minimal pour transformer M en P en effectuant les seules opérations élémentaires (au niveau d'un caractère) suivantes (on agit exclusivement sur M et successivement sur ses transformés) :

• - substitution (remplacer un caractère par un autre)
• - insertion
• - suppression

Par exemple, pour transformer "niche" en "chien", il faut supprimer le 'n' et le 'i', puis insérer le 'i' et le 'n'. La distance est donc de 2.

Comment déterminer les différentes opérations à réaliser pour passer d'un mot M à un mot P ? On va construire pour cela une matrice d'opérations D, et une matrice de coûts C.

La matrice C représente les coûts de substituion. C'est une matrice de n lignes et m colonnes (n étant la taille du premier mot M, m celle du deuxième P). Elle répond à la règle suivante :

• - Si M[i] = P[j], C[i][j] = 0
• - Sinon (M[i] != P[j]), alors C[i][j] = 1

La matrice D est une matrice de n+1 lignes et m+1 colonnes. On, initialise la première ligne par [0, 1, …, m-1, m] et la première colonne par [0, 1, ..., n - 1, n]. Ensuite, en parcourant les lignes de D de 1 à n et les colonnes de D de 1 à m, on remplit D de la manière suivante : D[i,j] est égal au minimum entre

• - D[i-1,j]+1 (effacement)
• - D[i,j-1]+1 (insertion)
• - D[i-1,j-1] + C[i-1,j-1] (substitution)

On commence ainsi par la première ligne de D de gauche à droite, puis la seconde... à la fin du traitement, D[n,m] contient la distance de Levenshtein.

L'algorithme est donc le suivant :

Proposez une implémentation de la distance de Levenshtein entre deux mots.