1A.algo - distance de Jaccard (dictionnaires)#

Links: notebook, html, python, slides, GitHub

Le notebook part du problème qui consiste à construire une distance entre deux chaînes de caractères en partant d’une idée naïve pour aller jusque la distance d’édition. distance de Jaccard.

from jyquickhelper import add_notebook_menu
add_notebook_menu()

Description du problème#

On cherche à construire un correcteur orthographique statistique. Il s’appuie sur l’hypothèse que la plupart du temps, un mot est écrit de façon correcte. Il fonctionne comme suit :

  • On agrège différents textes écrits par plusieurs personnes différentes.

  • On regroupe les différentes formes d’un même mot.

  • Au sein d’un groupe de mot, le mot le plus fréquent est le mot bien orthographié.

Au sein d’un texte sur l’hôpital, on a remarqué que le mot hôpital est orthographié de manières différentes : hôpital (3 fois), hopital (1 fois), hospital (1 fois). En appliquant la règle décrite plus haut, l’écriture correcte serait hôpital.

Comment aborder ce problème ? Il faut réussir à le formuler de telles sortes qu’on arrive à le décrire sous forme informatique.

Découpage du problème#

L’étape 2 suppose qu’on regroupe différents mots qui se ressemblent. Que veut dire que deux mots se ressemblent ? Ont-ils la plupart des lettres en commun ? Si on part de ce principe, on va essayer de construire une distancd entre deux mots : on compte le nombre de lettres supprimées puis ajoutées pour passer d’un mot w_1 à un mot w_2. Ceci ressemble à la distance de Jaccard. On suppose que chaque mot est un ensemble de lettres, il suffit de compter les lettres qui ne sont pas partie de l’intersection de ces deux ensembles.

Exemples :

  • distance entre hôpital et hopital : 3 (suppression de ô, s, ajout de o)

  • distance entre marie et aimer : 0 (même ensemble de lettres)

  • distance entre lettre et etre : 2 (suppression d’un l et d’un t)

Exercice 1 : Constuire l’ensemble des lettres supprimées et ajoutées#

Exercice 2 : écrire une fonction qui calcule la distance de Jaccard#

Retour vers le correcteur orthographique#

Comment utiliser cette distance pour repérer les mots qui se ressemblent ? Une idée est de se fixer un seuil, 2 par exemple, puis pour un mot donné w, extraire tous les mots x qui vérifient : distance(w, x) \leqslant 2. Une fois qu’on a découpé un texte en une séquence de mots (w_1, ..., w_n), on constuire une matrice de distances entre tous les couples de mots possibles.

Comment représenter cette matrice ? (avec les types standard de Python)

Exercice 3 : calculer la matrice des distances#