Objectifs

• Comprendre le fonctionnement d'une recherche textuelle ;
• Mettre en place une solution algorithmique de calculs de distances entre 2 mots ;
• Utiliser la programmation dynamique pour faire des programmes efficaces.

Activité 2 - Calcul de distances

Notion de distance

Une distance détermine la différence qui existe entre 2 mots et, de façon plus globale, le nombre d'opérations à effectuer sur un mot pour le changer en un autre mot.

Distance de Hamming

Fonctionnement

La distance de Hamming utilise 2 mots de longueurs identiques, et compte les différences entre les lettres de ces 2 mots, aux mêmes indices.

Exemple : LAMPE et JAMBE, il y a une distance de 2, car il faudrait changer le L en J et le P en B.

✏️Exercices

1
Écrire une fonction distance_Hamming(mot1, mot2) prenant en paramètres 2 mots, et retourne la distance entre ces 2 mots, suivant la distance de Hamming.
Fait
2
Modifier le programme pour qu'il retourne également une liste contenant les indices des lettres à changer du mot1.
Fait
3
Tester la fonction avec les mots :
• CANTINE / PANTINE
• CASSURE / FISSURE
• CHANTER / CHANGER
• CIRCUITS / VERTUES
Fait

Distance de Jaccard

Fonctionnement

En statistiques, la distance de Jaccard permet de mesurer la similarité entre 2 ensembles donnés. Ici, elle permet de connaître le pourcentage de similitude entre 2 mots.
Elle est calculable par cette formule : $\text{distance} = (1 - \frac{\text{nombre de lettres communes}}{\text{nombre total de lettres}}) * 100$

Exemple : CHAMBRE et JAMBE, il y a 12 lettres au total, dont 4 lettres communes (A, M, B, E). On aurait :
$\text{distance} = (1 - \frac{4}{12}) * 100$
$\text{distance} = 66,7$

Remarque

Plus le pourcentage obtenu est bas, plus les 2 mots seront similaires. À contrario, plus la valeur sera élevée, plus les mots seront différents.

✏️Exercices

1
Écrire une fonction distance_Jaccard(mot1, mot2) prenant en paramètres 2 mots, et retourne la distance entre ces 2 mots, suivant la distance de Jaccard.
Fait
2
Tester la fonction avec les mots :
• JARDINS / JARGONS
• PLATEAU / BATEAUX
• MARCHER / MANGER
• SILENCE / LICENSE
Fait

Distance de Levenshtein

Fonctionnement

La distance de Levenshtein compte le nombre minimum d'opérations à effectuer pour passer d'un mot à un autre.
Parmi ces opérations, on compte :

• La substitution d'une lettre ;
• L'ajout d'une lettre ;
• La suppression d'une lettre.

Exemple : CROIX et CROISE : on substitue X en S et on ajoute E à la fin du mot, on a 2 opérations.

Algorithme naïf

On donne la fonction suivante :

def distance_levenshtein_naif(mot1, mot2):
    # Si l'un des mots est vide, la distance est la longueur de l'autre mot
    if ... :
        return ...
    if ... :
        return ...
    
    # Si les premiers caractères des deux mots sont les mêmes
    if ... :
        # On recommence avec la sous-chaine sans le premier caractère de chaque mot
        return ...
    
    # Sinon, calculer les trois possibilités (insertion, suppression, substitution)
    insertion = ...  # Insertion dans mot1
    suppression = ...  # Suppression dans mot1
    substitution = ...  # Substitution
    
    # Retourner la distance minimale des trois opérations
    return ...

✏️Exercices

1
Recopier et compléter la fonction.
Fait
2
Tester la fonction avec les mots croix et croise. Quelles opérations faut-il effectuer ?
Fait
3
Tester la fonction avec les mots noix et croise. Quelles opérations faut-il effectuer ?
Fait
4
On souhaite compter le nombre d'appels récursifs réalisés. Ajouter une variable globale cpt, et afficher pour les 2 tests précédents, le nombre d'appels qu'il y a eu.
Fait

Programmation dynamique

Pour éviter d'avoir à calculer plusieurs fois des opérations déjà réalisées, nous allons les mémoïser dans une matrice.
Pour les mots GRISE et ROSE, nous pourrions avoir cet exemple :

		G	R	I	S	E
	0	1	2	3	4	5
R	1
O	2
S	3
E	4

Cette matrice se complète ligne par ligne, et se remplit avec le nombre d'opérations pour transformer R en G, puis après R en GR et ainsi de suite jusqu'à R en GRISE.
Par la suite, on recommence en transformant RO, puis ROS et enfin ROSE.

Algorithme pour remplir la grille

• Si la lettre de la rangée est égale à la lettre de la colonne, alors :
  • On ajoute 1 à la valeur de la case à gauche ;
  • On ajoute 1 à la valeur de la case au dessus ;
  • On prend le minimum entre la case à gauche, la case du dessus, et la case en haut à gauche.
• Sinon :
  • On prend le minimum entre la case à gauche, la case du dessus, et la case en haut à gauche ;
  • On ajoute 1 à cette valeur.

Exemple sur la première rangée

		G	R	I	S	E
	0	1	2	3	4	5
R	1	1	1	2	3	4
O	2
S	3
E	4

• R != G : min(1,1,0) + 1 = 1
• R == R : min(1+1, 2+1, 1) = 1
• R != I : min(1,3,2) + 1 = 2
• R != S : min(2,4,3) + 1 = 3
• R != E : min(3,5,4) + 1 = 4

✏️Exercices

1
Compléter les lignes manquantes. La distance se trouvera dans la case en bas à droite.
Fait

Pour programmer cette nouvelle fonction, nous allons avoir besoin d'une mémoire.

2
Écrire l'entête de la fonction distance_levenshtein_mem(mot1,mot2), puis initialiser une mémoire, qui sera préremplie de 0, dont la première rangée et colonne seront complétées, comme dans l'exemple, des valeurs de 0 jusqu'à la taille des mots.
Fait
3
À l'aide de boucles for, parcourir la matrice, et implémenter les règles énumérées plus haut.
Fait
4
Retourner la valeur dans la dernière case.
Fait
5
Rajouter un compteur en variable globale pour compter le nombre de tours de boucle effectués.
Fait
6
Tester la fonction avec les mêmes mots de la partie d'avant, et comparer les résultats.
Fait
7
Utiliser la bibliothèque time pour comparer les temps d'exécution de ces 2 fonctions avec les mots informatique et automatique.
Fait