{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.algo - La distance d'\u00e9dition\n", "\n", "La distance d'\u00e9dition ou de [Levenshtein](https://fr.wikipedia.org/wiki/Distance_de_Levenshtein) calcule une distance entre deux s\u00e9quences. L'algorithme utilise la programmation dynamique."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["\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": ["## Introduction\n", "\n", "On veut mesurer la proximit\u00e9 entre deux mots et un moyen simple est de construire une distance : $d(m_1,m_2) = d(m_2, m_1) = ?$."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Premier essai de distance : Hamming\n", "\n", "La [distance de Hamming](https://fr.wikipedia.org/wiki/Distance_de_Hamming) consiste \u00e0 comparer les caract\u00e8res les unes \u00e0 la suite des autres.\n", "\n", "$\\begin{array}{c|ccccc} A & c & l & o & s & e \\\\ \\hline B & c & l & o & u & e \\\\ \\hline d(A,B) & 0 & 0 & 0 & 1 & 0 \\end{array}$\n", "\n", "La distance est alors la somme des petites distances :"]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"data": {"text/plain": ["1"]}, "execution_count": 3, "metadata": {}, "output_type": "execute_result"}], "source": ["def dist_hamming(m1,m2):\n", " d = 0\n", " for a,b in zip(m1,m2):\n", " if a != b : \n", " d += 1\n", " return d\n", "\n", "dist_hamming(\"close\", \"cloue\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 1 : comment prendre en compte diff\u00e9rentes tailles de mots ?"]}, {"cell_type": "code", "execution_count": 3, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Les petits d\u00e9fauts de Hamming\n", "\n", "Que pensez-vous de ces deux distances (on suppose que la fonction ``dist_hamming`` est celle provenant de l'exercice 1)."]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"data": {"text/plain": ["6"]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}], "source": ["dist_hamming(\"longmot\", \"liongmot\")"]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"data": {"text/plain": ["1"]}, "execution_count": 6, "metadata": {}, "output_type": "execute_result"}], "source": ["dist_hamming(\"longmot\", \"longmoit\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La lettre **i** a \u00e9t\u00e9 ajout\u00e9e \u00e0 deux endroits diff\u00e9rents : vers le d\u00e9but dans le premier cas et vers la fin dans le second. La distance est tr\u00e8s diff\u00e9rente dans les deux cas."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Une propri\u00e9t\u00e9 souhaitable de la distance\n", "\n", "La distance de Hamming n'est sans doute pas une distance id\u00e9ale, elle n'est pas tr\u00e8s robuste pour prendre en compte les d\u00e9calages. Que pourrait-on faire pour l'am\u00e9liorer ?\n", "\n", "* On pourrait essayer de faire une sorte de m\u00e9lange Jaccard-Hamming et dire que si la distance de Hamming est trop grande, on bascule sur la distance de Jaccard. On prendrait le minimum des deux distances.\n", "* On pourrait essayer de diff\u00e9rencier les mots longs et les mots courts mais comment distinguer les deux ?\n", "* On pourrait essayer de traiter sp\u00e9cifiquement les cas d'insertion de lettres. Que faire alors si on en ins\u00e8re deux ?\n", "\n", "Toutes ces id\u00e9es proposent des am\u00e9liorations mais il est difficile de pr\u00e9dire si elles n'auront pas un dr\u00f4le de comportement dans certains cas pr\u00e9cis.\n", "\n", "Plut\u00f4t que de chercher des id\u00e9es d'am\u00e9liorations, pourquoi ne pas se demander plut\u00f4t quelles propri\u00e9t\u00e9s cette distance devrait v\u00e9rifier. On peut d\u00e9couper un mot en deux mots plus petits et \u00e9crire :\n", "\n", "$d(longmot,longmoit) = d(long,long) + d(mot, moit)$\n", "\n", "Est-ce une propri\u00e9t\u00e9 souhaitable pour notre distance ? Cela para\u00eet raisonnable et on voit tout de suite que la distance de Hamming ne v\u00e9rifie pas cette propri\u00e9t\u00e9."]}, {"cell_type": "markdown", "metadata": {}, "source": ["Si on poursuit le raisonnement, on devrait pouvoir aussi avoir :\n", "\n", "$d(longmot,longmoit) = d(longmo,longmo) + d(t, it)$\n", "\n", "Et si on \u00e9crivait plut\u00f4t :\n", "\n", "$d(longmot,longmoit) = \\min \\left\\{ d(longmo,longmo) + d(t, it), d(long,long) + d(mot, moit) \\right\\}$\n", "\n", "Mais peut-\u00eatre que ce qui suit para\u00eet un peu plus juste :\n", "\n", "$d(longmot,longmoit) \\leqslant \\min \\left\\{ d(longmo,longmo) + d(t, it), d(long,long) + d(mot, moit) \\right\\}$"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Cette in\u00e9galit\u00e9 implique deux d\u00e9coupages d'un mot. Mais il existe plein de fa\u00e7ons de d\u00e9couper un mot en deux. Plus exactement, si le mot a $n$ lettres, il existe $n-1$ fa\u00e7on de le couper en deux. On note $m[[1..n]]$ un mot $n$ caract\u00e8res :\n", "\n", "$d( m_1[[1..n_1]], m_2[[1..n_2]] ) \\leqslant \\min_{ 1 \\leqslant i \\leqslant n_1-1, 1 \\leqslant j \\leqslant n_2-1 } \\left\\{ d( m_1[[1..i]], m_2[[1..j]] ) + d( m_1[[i+1..n_1]], m_2[[j+1..n_2]] ) \\right\\}$ \n", "\n", "Mais au fait, n'aurait-on pas envisager toutes les fa\u00e7ons de d\u00e9couper un mot en deux. Donc le minimum se trouve parmi l'un de ses d\u00e9coupages :\n", "\n", "$d( m_1[[1..n_1]], m_2[[1..n_2]] ) = \\min_{ 1 \\leqslant i \\leqslant n_1-1, 1 \\leqslant j \\leqslant n_2-1 } \\left\\{ d( m_1[[1..i]], m_2[[1..j]] ) + d( m_1[[i+1..n_1]], m_2[[j+1..n_2]] ) \\right\\}$\n", "\n", "On simplifie l'\u00e9criture en \u00e9crivant $m[[i..j]] = m[i:j]$. Cela donne :\n", "\n", "$d( m_1[1:n_1], m_2[1:n_2] ) = \\min_{ 1 \\leqslant i \\leqslant n_1-1, 1 \\leqslant j \\leqslant n_2-1 } \\left\\{ d( m_1[1:i], m_2[1:j] ) + d( m_1[i+1:n_1], m_2[j+1:n_2] ) \\right\\}$\n", "\n", "On sait maintenant exprimer la distance entre deux mots longs \u00e0 partir de mots plus courts qui les composent. Comme toute d\u00e9finition r\u00e9currente, il faut d\u00e9finir la distance pour les mots les plus courts : 1 \u00e0 2 lettres. Dans ce cas, on prendra distance de Hamming."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 2 : impl\u00e9menter une distance \u00e0 partir de cette \u00e9galit\u00e9"]}, {"cell_type": "code", "execution_count": 6, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {"collapsed": true}, "source": ["## Distance d'\u00e9dition\n", "\n", "D'apr\u00e8s l'\u00e9galit\u00e9, il existe un d\u00e9couage optimal $(i^*, j^*)$ tel que $d( m_1[1:n_1], m_2[1:n_2] ) = d( m_1[1:i^*], m_2[1:j^*] ) + d( m_1[i^*:n_1], m_2[j^*:n_2] ) $. Mais on peut recommencer \u00e0 d\u00e9couper de f-a\u00e7on optimale : $d( m_1[i^*:n_1], m_2[j^*:n_2] ) = d( m_1[i^*:k^*], m_2[j^*:l^*] ) + d( m_1[k^*:n_1], m_2[l^*:n_2] )$. On peut d\u00e9couper comme cela jusqu'\u00e0 obtenir un d\u00e9coupage optimal o\u00f9 on n'a plus que des mots courts de 1 ou 2 caract\u00e8res. Mais alors... pourquoi ne pas utiliser ces petits mots ins\u00e9cables lors de l'expression de la distance.\n", "\n", "$d( m_1[1:n_1], m_2[1:n_2] ) = \\min \\left\\{ \\begin{array}{l} d( m_1[1:n_1-2], m_2[1:n_2-1] ) + hamming(m_1[n_1-1:n_1], m_2[n_2:n_2]) ) \\\\ d( m_1[1:n_1-1], m_2[1:n_1-2] ) + hamming(m_1[n_1:n_1], m_2[n_2-1:n_2]) ) \\\\ d( m_1[1:n_1-1], m_2[1:n_1-1] ) + hamming(m_1[n_1:n_1], m_2[n_2:n_2]) ) \\end{array} \\right.$\n", "\n", "Ces trois options sont les seules possibles en partant de la fin du mot."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 3 : impl\u00e9menter la distance d'\u00e9dition"]}, {"cell_type": "code", "execution_count": 7, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 4 : diff\u00e9rence avec l'algorithme de Wikip\u00e9dia"]}, {"cell_type": "code", "execution_count": 8, "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}