Aller au contenu principal
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.

  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.
  2. Modifier le programme pour qu'il retourne également une liste contenant les indices des lettres à changer du mot1.
  3. Tester la fonction avec les mots :
    • CANTINE / PANTINE
    • CASSURE / FISSURE
    • CHANTER / CHANGER
    • CIRCUITS / VERTUES

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 : distance=(1−nombre de lettres communesnombre total de lettres)∗100\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 :
distance=(1−412)∗100\text{distance} = (1 - \frac{4}{12}) * 100
distance=66,7\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.

  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.
  2. Tester la fonction avec les mots :
    • JARDINS / JARGONS
    • PLATEAU / BATEAUX
    • MARCHER / MANGER
    • SILENCE / LICENSE

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 ...
  1. Recopier et compléter la fonction.
  2. Tester la fonction avec les mots croix et croise. Quelles opérations faut-il effectuer ?
  3. Tester la fonction avec les mots noix et croise. Quelles opérations faut-il effectuer ?
  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.

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 :

GRISE
012345
R1
O2
S3
E4

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
GRISE
012345
R111234
O2
S3
E4
  • 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
  1. Compléter les lignes manquantes. La distance se trouvera dans la case en bas à droite.

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

  1. É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.
  2. À l'aide de boucles for, parcourir la matrice, et implémenter les règles énumérées plus haut.
  3. Retourner la valeur dans la dernière case.
  4. Rajouter un compteur en variable globale pour compter le nombre de tours de boucle effectués.
  5. Tester la fonction avec les mêmes mots de la partie d'avant, et comparer les résultats.
  6. Utiliser la bibliothèque time pour comparer les temps d'exécution de ces 2 fonctions avec les mots informatique et automatique.