.. _td1acenoncesession45jaccardrst:

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


.. only:: html

    **Links:** :download:`notebook <td1a_cenonce_session4_5_jaccard.ipynb>`, :downloadlink:`html <td1a_cenonce_session4_5_jaccard2html.html>`, :download:`python <td1a_cenonce_session4_5_jaccard.py>`, :downloadlink:`slides <td1a_cenonce_session4_5_jaccard.slides.html>`, :githublink:`GitHub|_doc/notebooks/td1a_algo/td1a_cenonce_session4_5_jaccard.ipynb|*`


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 <https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard>`__.

.. code:: ipython3

    from jyquickhelper import add_notebook_menu
    add_notebook_menu()






.. contents::
    :local:





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 :math:`w_1` à un mot :math:`w_2`.
Ceci ressemble à la `distance de
Jaccard <https://fr.wikipedia.org/wiki/Indice_et_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 :
:math:`distance(w, x) \leqslant 2`. Une fois qu’on a découpé un texte en
une séquence de mots :math:`(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
----------------------------------------------