{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.algo - distance de Jaccard (dictionnaires)\n", "\n", "Le notebook part du probl\u00e8me qui consiste \u00e0 construire une distance entre deux cha\u00eenes de caract\u00e8res en partant d'une id\u00e9e na\u00efve pour aller jusque la distance d'\u00e9dition. distance de [Jaccard](https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard)."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["
run previous cell, wait for 2 seconds
\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Description du probl\u00e8me\n", "\n", "On cherche \u00e0 construire un correcteur orthographique statistique. Il s'appuie sur l'hypoth\u00e8se que la plupart du temps, un mot est \u00e9crit de fa\u00e7on correcte. Il fonctionne comme suit :\n", "\n", "* On agr\u00e8ge diff\u00e9rents textes \u00e9crits par plusieurs personnes diff\u00e9rentes.\n", "* On regroupe les diff\u00e9rentes formes d'un m\u00eame mot.\n", "* Au sein d'un groupe de mot, le mot le plus fr\u00e9quent est le mot bien orthographi\u00e9.\n", "\n", "Au sein d'un texte sur l'h\u00f4pital, on a remarqu\u00e9 que le mot ``h\u00f4pital`` est orthographi\u00e9 de mani\u00e8res diff\u00e9rentes : *h\u00f4pital* (3 fois), *hopital* (1 fois), *hospital* (1 fois). En appliquant la r\u00e8gle d\u00e9crite plus haut, l'\u00e9criture correcte serait *h\u00f4pital*.\n", "\n", "Comment aborder ce probl\u00e8me ? Il faut r\u00e9ussir \u00e0 le formuler de telles sortes qu'on arrive \u00e0 le d\u00e9crire sous forme informatique."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## D\u00e9coupage du probl\u00e8me\n", "\n", "L'\u00e9tape 2 suppose qu'on regroupe diff\u00e9rents 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\u00e9es puis ajout\u00e9es pour passer d'un mot $w_1$ \u00e0 un mot $w_2$. Ceci ressemble \u00e0 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. \n", "\n", "Exemples :\n", "\n", "* distance entre *h\u00f4pital* et *hopital* : 3 (suppression de *\u00f4*, *s*, ajout de *o*)\n", "* distance entre *marie* et *aimer* : 0 (m\u00eame ensemble de lettres)\n", "* distance entre *lettre* et *etre* : 2 (suppression d'un *l* et d'un *t*)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 1 : Constuire l'ensemble des lettres supprim\u00e9es et ajout\u00e9es"]}, {"cell_type": "code", "execution_count": 2, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 2 : \u00e9crire une fonction qui calcule la distance de Jaccard"]}, {"cell_type": "code", "execution_count": 3, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Retour vers le correcteur orthographique\n", "\n", "Comment utiliser cette distance pour rep\u00e9rer les mots qui se ressemblent ? Une id\u00e9e est de se fixer un seuil, 2 par exemple, puis pour un mot donn\u00e9 *w*, extraire tous les mots *x* qui v\u00e9rifient : $distance(w, x) \\leqslant 2$. Une fois qu'on a d\u00e9coup\u00e9 un texte en une s\u00e9quence de mots $(w_1, ..., w_n)$, on constuire une matrice de distances entre tous les couples de mots possibles.\n", "\n", "**Comment repr\u00e9senter cette matrice ?** (avec les types standard de Python)\n"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 3 : calculer la matrice des distances"]}, {"cell_type": "code", "execution_count": 4, "metadata": {"collapsed": true}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}, "language_info": {"codemirror_mode": {"name": "ipython", "version": 3}, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.1"}}, "nbformat": 4, "nbformat_minor": 2}