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 
à un mot 
.
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 :
. Une fois qu’on a découpé un texte en
une séquence de mots 
, on constuire une matrice
de distances entre tous les couples de mots possibles.
Comment représenter cette matrice ? (avec les types standard de Python)