{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# Distance entre deux mots de m\u00eame longueur et tests unitaires\n", "\n", "Calculer une distance entre deux mots n'est pas le plus intuitif des probl\u00e8mes. Dans ce notebook, on se permet de t\u00e2tonner pour faire \u00e9voluer quelques id\u00e9es autour du sujet. C'est l'occasion aussi de montrer \u00e0 quoi servent les tests unitaires et pourquoi ils sont utiles lorsqu'on t\u00e2tonne."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["<div id=\"my_id_menu_nb\">run previous cell, wait for 2 seconds</div>\n", "<script>\n", "function repeat_indent_string(n){\n", "    var a = \"\" ;\n", "    for ( ; n > 0 ; --n)\n", "        a += \"    \";\n", "    return a;\n", "}\n", "// look up into all sections and builds an automated menu //\n", "var update_menu_string = function(begin, lfirst, llast, sformat, send, keep_item, begin_format, end_format) {\n", "    var anchors = document.getElementsByClassName(\"section\");\n", "    if (anchors.length == 0) {\n", "        anchors = document.getElementsByClassName(\"text_cell_render rendered_html\");\n", "    }\n", "    var i,t;\n", "    var text_menu = begin;\n", "    var text_memo = \"<pre>\\nlength:\" + anchors.length + \"\\n\";\n", "    var ind = \"\";\n", "    var memo_level = 1;\n", "    var href;\n", "    var tags = [];\n", "    var main_item = 0;\n", "    var format_open = 0;\n", "    for (i = 0; i <= llast; i++)\n", "        tags.push(\"h\" + i);\n", "\n", "    for (i = 0; i < anchors.length; i++) {\n", "        text_memo += \"**\" + anchors[i].id + \"--\\n\";\n", "\n", "        var child = null;\n", "        for(t = 0; t < tags.length; t++) {\n", "            var r = anchors[i].getElementsByTagName(tags[t]);\n", "            if (r.length > 0) {\n", "child = r[0];\n", "break;\n", "            }\n", "        }\n", "        if (child == null) {\n", "            text_memo += \"null\\n\";\n", "            continue;\n", "        }\n", "        if (anchors[i].hasAttribute(\"id\")) {\n", "            // when converted in RST\n", "            href = anchors[i].id;\n", "            text_memo += \"#1-\" + href;\n", "            // passer \u00e0 child suivant (le chercher)\n", "        }\n", "        else if (child.hasAttribute(\"id\")) {\n", "            // in a notebook\n", "            href = child.id;\n", "            text_memo += \"#2-\" + href;\n", "        }\n", "        else {\n", "            text_memo += \"#3-\" + \"*\" + \"\\n\";\n", "            continue;\n", "        }\n", "        var title = child.textContent;\n", "        var level = parseInt(child.tagName.substring(1,2));\n", "\n", "        text_memo += \"--\" + level + \"?\" + lfirst + \"--\" + title + \"\\n\";\n", "\n", "        if ((level < lfirst) || (level > llast)) {\n", "            continue ;\n", "        }\n", "        if (title.endsWith('\u00b6')) {\n", "            title = title.substring(0,title.length-1).replace(\"<\", \"&lt;\")\n", "         .replace(\">\", \"&gt;\").replace(\"&\", \"&amp;\");\n", "        }\n", "        if (title.length == 0) {\n", "            continue;\n", "        }\n", "\n", "        while (level < memo_level) {\n", "            text_menu += end_format + \"</ul>\\n\";\n", "            format_open -= 1;\n", "            memo_level -= 1;\n", "        }\n", "        if (level == lfirst) {\n", "            main_item += 1;\n", "        }\n", "        if (keep_item != -1 && main_item != keep_item + 1) {\n", "            // alert(main_item + \" - \" + level + \" - \" + keep_item);\n", "            continue;\n", "        }\n", "        while (level > memo_level) {\n", "            text_menu += \"<ul>\\n\";\n", "            memo_level += 1;\n", "        }\n", "        text_menu += repeat_indent_string(level-2);\n", "        text_menu += begin_format + sformat.replace(\"__HREF__\", href).replace(\"__TITLE__\", title);\n", "        format_open += 1;\n", "    }\n", "    while (1 < memo_level) {\n", "        text_menu += end_format + \"</ul>\\n\";\n", "        memo_level -= 1;\n", "        format_open -= 1;\n", "    }\n", "    text_menu += send;\n", "    //text_menu += \"\\n\" + text_memo;\n", "\n", "    while (format_open > 0) {\n", "        text_menu += end_format;\n", "        format_open -= 1;\n", "    }\n", "    return text_menu;\n", "};\n", "var update_menu = function() {\n", "    var sbegin = \"\";\n", "    var sformat = '<a href=\"#__HREF__\">__TITLE__</a>';\n", "    var send = \"\";\n", "    var begin_format = '<li>';\n", "    var end_format = '</li>';\n", "    var keep_item = -1;\n", "    var text_menu = update_menu_string(sbegin, 2, 4, sformat, send, keep_item,\n", "       begin_format, end_format);\n", "    var menu = document.getElementById(\"my_id_menu_nb\");\n", "    menu.innerHTML=text_menu;\n", "};\n", "window.setTimeout(update_menu,2000);\n", "            </script>"], "text/plain": ["<IPython.core.display.HTML object>"]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Distance na\u00efve\n", "\n", "Na\u00eff... mais beaucoup d'id\u00e9es na\u00efves finissent par aboutir \u00e0 des pyramides complexes."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Distance tr\u00e8s na\u00efve\n", "\n", "On se restraint au cas o\u00f9 les deux mots \u00e0 comparer ont la m\u00eame longueur. Et dans ce cas, le plus simple est de compter le nombre de caract\u00e8res diff\u00e9rents \u00e0 chaque position."]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"data": {"text/plain": ["1"]}, "execution_count": 3, "metadata": {}, "output_type": "execute_result"}], "source": ["def distance1(m1, m2):\n", "    d = 0\n", "    for i in range(0, len(m1)):\n", "        if m1[i] != m2[i]:\n", "            d += 1\n", "    return d\n", "\n", "distance1(\"info\", \"imfo\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Distance entre deux mots de longueur diff\u00e9rente mais pas si diff\u00e9rente\n", "\n", "On consid\u00e8re le cas o\u00f9 les deux mots ont des longueurs \u00e9gales ou diff\u00e9rentes de un caract\u00e8res. Dans le premier cas, on utilise la distance pr\u00e9c\u00e9dente, dans le second cas, on ajoute un espace au mot le plus court et on appelle la distance pr\u00e9c\u00e9dente. Mais o\u00f9 ins\u00e9rer cet espace ? A toutes les positions bien s\u00fbr, la distance sera le minimum de toutes les distances calcul\u00e9es.\n", "\n", "Pour simplifier, on commence par d\u00e9cider que le premier mot doit \u00eatre le plus court des deux. Si ce n'est pas le cas, on les permute."]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"data": {"text/plain": ["1"]}, "execution_count": 4, "metadata": {}, "output_type": "execute_result"}], "source": ["def distance2(m1, m2):\n", "    if len(m1) == len(m2):\n", "        return distance1(m1, m2)\n", "    if len(m2) < len(m1):\n", "        m1, m2 = m2, m1\n", "    meilleur = len(m2)\n", "    for i in range(len(m1) + 1):\n", "        m1_e = m1[:i] + ' ' + m1[i:]\n", "        d = distance1(m1_e, m2)\n", "        if d < meilleur:\n", "            meilleur = d\n", "    return meilleur\n", "\n", "distance2(\"cab\", \"ab\")"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"data": {"text/plain": ["5"]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}], "source": ["distance2(\"abcd\", \"bcdef\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Parfois on aime bien comprendre un peu plus en d\u00e9tail. On ajoute alors un param\u00e8tre `verbose` qui affiche des informations sans pour autant affecter le r\u00e9sultat."]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["i=0 m1_e=' ab' m2='cab' d=1 meilleur=1\n", "i=1 m1_e='a b' m2='cab' d=2 meilleur=1\n", "i=2 m1_e='ab ' m2='cab' d=3 meilleur=1\n"]}, {"data": {"text/plain": ["1"]}, "execution_count": 6, "metadata": {}, "output_type": "execute_result"}], "source": ["def distance2_verbose(m1, m2, verbose=False):\n", "    if len(m1) == len(m2):\n", "        return distance1(m1, m2)\n", "    if len(m2) < len(m1):\n", "        m1, m2 = m2, m1\n", "    meilleur = len(m2)\n", "    for i in range(len(m1) + 1):\n", "        m1_e = m1[:i] + ' ' + m1[i:]\n", "        d = distance1(m1_e, m2)\n", "        if d < meilleur:\n", "            meilleur = d\n", "        if verbose:\n", "            print(\"i=%r m1_e=%r m2=%r d=%d meilleur=%d\" % (\n", "                i, m1_e, m2, d, meilleur))\n", "    return meilleur\n", "\n", "distance2_verbose(\"cab\", \"ab\", True)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le param\u00e8tre **verbose** est une sorte de r\u00e8gle commun\u00e9ment partag\u00e9e, une convention... C'est ce que qu'en disent les [pirates](https://www.youtube.com/watch?v=WJVBvvS57j0)."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Distance entre deux mots de longueur diff\u00e9rente\n", "\n", "On suit la m\u00eame id\u00e9e et on ins\u00e8re des espaces dans le mot le plus petit de fa\u00e7on r\u00e9cursive jusqu'\u00e0 pouvoir utiliser la distance pr\u00e9c\u00e9dente. Le code ressemble beaucoup \u00e0 la fonction pr\u00e9c\u00e9dente."]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"data": {"text/plain": ["3"]}, "execution_count": 7, "metadata": {}, "output_type": "execute_result"}], "source": ["def distance3(m1, m2):\n", "    if abs(len(m1) - len(m2)) <= 1:\n", "        return distance2(m1, m2)\n", "    if len(m2) < len(m1):\n", "        m1, m2 = m2, m1\n", "    meilleur = len(m2)\n", "    for i in range(len(m1) + 1):\n", "        m1_e = m1[:i] + ' ' + m1[i:]\n", "        d = distance3(m1_e, m2)\n", "        if d < meilleur:\n", "            meilleur = d\n", "    return meilleur\n", "\n", "distance3(\"info\", \"pimfos\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Test unitaires\n", "\n", "Quand on d\u00e9veloppe un algorithme, on l'applique sur quelques exemples pour v\u00e9rifier qu'il marche... Puis, on l'am\u00e9liore et on v\u00e9rifie qu'il fonctionne sur de nouveaux exemples plus complexes... V\u00e9rifie-t-on que cela marche fonctionne encore pour les premiers cas... Le plus souvent non... car c'est fastideux... J'en conviens... Alors pourquoi ne pas noter tous ces cas dans une fonction qui les v\u00e9rifie... La fonction ne prend aucun param\u00e8tres, elle r\u00e9ussit si la fonction retourne tous les r\u00e9sultats d\u00e9sir\u00e9s, elle \u00e9choue dans le cas contraire."]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": ["def test_dist_equal(d):\n", "    assert d(\"\", \"\") == 0\n", "    assert d(\"a\", \"a\") == 0\n", "    assert d(\"a\", \"b\") == 1\n", "    \n", "def test_distance1():\n", "    test_dist_equal(distance1)\n", "    \n", "test_distance1()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Pas d'erreur... On continue avec la seconde distance en ajoutant des cas pour lesquels elle a \u00e9t\u00e9 programm\u00e9e. Pour les tests, on utilise un caract\u00e8re `'_'` diff\u00e9rent des espaces `' '` utilis\u00e9 par les fonctions distance."]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": ["def test_dist_diff1(d):\n", "    assert d(\"\", \"a\") == 1\n", "    assert d(\"a\", \"\") == 1\n", "    assert d(\"_a\", \"a\") == 1\n", "    assert d(\"a_\", \"a\") == 1\n", "    assert d(\"a\", \"a_\") == 1\n", "    assert d(\"a\", \"_a\") == 1\n", "\n", "def test_distance2():\n", "    test_dist_equal(distance2)\n", "    test_dist_diff1(distance2)\n", "    \n", "test_distance2()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Toujours pas d'erreur... La vie est magnifique... On continue avec la troisi\u00e8me distance en ajoutant des cas pour lesquels elle a \u00e9t\u00e9 programm\u00e9e."]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": ["def test_dist_diff2(d):\n", "    assert d(\"\", \"ab\") == 2\n", "    assert d(\"ab\", \"\") == 2\n", "    assert d(\"_ab\", \"a\") == 2\n", "    assert d(\"ab_\", \"ab\") == 1\n", "    assert d(\"ab\", \"ab_\") == 1\n", "    assert d(\"ab\", \"_ab\") == 1\n", "    assert d(\"ab\", \"ab\") == 0\n", "    assert d(\"ab\", \"a_b\") == 1\n", "    assert d(\"a_b\", \"ab\") == 1\n", "\n", "def test_distance3():\n", "    test_dist_equal(distance3)\n", "    test_dist_diff1(distance3)\n", "    test_dist_diff2(distance3)\n", "    \n", "test_distance3()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Toujours pas d'erreur... Magnifique... Et maintenant... Il est vrai qu'on ne s'est pas pench\u00e9 sur les co\u00fbts de chaque fonction mais la fonction ``distance3`` est incroyablement longue. On note $N = \\max(len(m1), len(m2))$.\n", "\n", "* co\u00fbt `distance1`: $O(N)$ \n", "* co\u00fbt `distance2`: $O(N^2)$ \n", "* co\u00fbt `distance3`: $O(N^{\\delta+1})$ o\u00f9 $\\delta = |len(m1), len(m2)|$.\n", "\n", "Je vous laisse quelques minutes pour v\u00e9rifier. J'interpr\u00e8te : c'est beaucoup trop."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Distance d'\u00e9dition\n", "\n", "On impl\u00e9mente l'algorithme de la distance de [Levenstein](https://en.wikipedia.org/wiki/Levenshtein_distance)."]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["edit 1.0\n"]}], "source": ["import numpy\n", "\n", "def edit_distance(m1, m2):\n", "    mat = numpy.zeros((len(m1) + 1, len(m2) + 1))\n", "    for i in range(len(m1) + 1):\n", "        mat[i, 0] = i\n", "    for j in range(len(m2) + 1):\n", "        mat[0, j] = j\n", "    for i in range(1, len(m1) + 1):\n", "        for j in range(1, len(m2) + 1):\n", "            c1 = mat[i-1, j] + 1\n", "            c2 = mat[i, j-1] + 1\n", "            if m1[i-1] == m2[j-1]:\n", "                c = 0\n", "            else:\n", "                c = 1\n", "            c3 = mat[i-1, j-1] + c\n", "            mat[i, j] = min([c1, c2, c3])\n", "    return mat[-1, -1]\n", "\n", "print(\"edit\", edit_distance('agrafe', 'agrae'))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On utilise les tests unitaires pour v\u00e9rifier qu'elle retourne les m\u00eames r\u00e9sultats, ceux qu'on souhaite."]}, {"cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": ["def test_edit_distance():\n", "    test_dist_equal(edit_distance)\n", "    test_dist_diff1(edit_distance)\n", "    test_dist_diff2(edit_distance)\n", "    \n", "test_edit_distance()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Ca marche..."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### m et n sont tr\u00e8s proches, et alors ?"]}, {"cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [{"data": {"text/plain": ["2.0"]}, "execution_count": 13, "metadata": {}, "output_type": "execute_result"}], "source": ["edit_distance(\"r\u00e9mun\u00e9rer\", \"r\u00e9num\u00e9rer\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Comme beaucoup de gens font l'erreur, on voudrait que le co\u00fbt soit r\u00e9duit de moiti\u00e9. On veut alors que la confusion entre `m` et `n` ait un co\u00fbt de `0.5`."]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["edit 1.0\n"]}], "source": ["def edit_distance2(m1, m2):\n", "    mat = numpy.zeros((len(m1) + 1, len(m2) + 1))\n", "    cmp_char = {('m','n') : 0.5, ('n','m') : 0.5}\n", "    for i in range(len(m1) + 1):\n", "        mat[i, 0] = i\n", "    for j in range(len(m2) + 1):\n", "        mat[0, j] = j\n", "    for i in range(1, len(m1) + 1):\n", "        for j in range(1, len(m2) + 1):\n", "            c1 = mat[i-1, j] + 1\n", "            c2 = mat[i, j-1] + 1\n", "            if m1[i-1] == m2[j-1]:\n", "                c = 0\n", "            else:\n", "                c = cmp_char.get((m1[i-1], m2[j-1]), 1)\n", "            c3 = mat[i-1, j-1] + c\n", "            mat[i, j] = min([c1, c2, c3])\n", "            \n", "            if i >= 2:\n", "                cc = cmp_char.get((m1[i-2:i], m2[j-1]), 1)\n", "                c4 = mat[i-2, j-1] + cc\n", "                mat[i, j] = min(mat[i, j], c4)\n", "            if j >= 2:\n", "                cc = cmp_char.get((m1[i-1], m2[j-2:j]), 1)\n", "                c4 = mat[i-1, j-2] + cc\n", "                mat[i, j] = min(mat[i, j], c4)\n", "            \n", "    return mat[-1, -1]\n", "\n", "print(\"edit\", edit_distance2('r\u00e9mun\u00e9rer', 'r\u00e9num\u00e9rer'))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Et toujours les tests unitaires."]}, {"cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": ["def test_special(d):\n", "    assert d('r\u00e9mun\u00e9rer', 'r\u00e9num\u00e9rer') == 1\n", "\n", "def test_edit_distance2():\n", "    test_dist_equal(edit_distance2)\n", "    test_dist_diff1(edit_distance2)\n", "    test_dist_diff2(edit_distance2)\n", "    test_special(edit_distance2)\n", "    \n", "test_edit_distance2()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### ff, f, ph, f... plus personne ne sait \u00e9crire"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Tout marche. Et maintenant on aimerait que :\n", "\n", "* `distance('agraffe', 'agrafe') == 0.5`\n", "* `distance('agrafe', 'agrae') == 1`\n", "* `distance('\u00e9l\u00e9phant', '\u00e9l\u00e9fant') == 0.5`\n", "\n", "Nouvelle distance encore."]}, {"cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["edit 1.0\n"]}], "source": ["def edit_distance3(m1, m2):\n", "    mat = numpy.zeros((len(m1) + 1, len(m2) + 1))\n", "    cmp_char = {('m','n') : 0.5, ('n','m') : 0.5,\n", "                ('ff', 'f'): 0.5, ('f', 'ff'): 0.5,\n", "                ('ph', 'f'): 0.4, ('ph', 'f'): 0.4}\n", "    ins_char = {}\n", "    for i in range(len(m1) + 1):\n", "        mat[i, 0] = i\n", "    for j in range(len(m2) + 1):\n", "        mat[0, j] = j\n", "    for i in range(1, len(m1) + 1):\n", "        for j in range(1, len(m2) + 1):\n", "            c1 = mat[i-1, j] + ins_char.get(m1[i-1], 1)\n", "            c2 = mat[i, j-1] + ins_char.get(m2[j-1], 1)\n", "            if m1[i-1] == m2[j-1]:\n", "                c = 0\n", "            else:\n", "                c = cmp_char.get((m1[i-1], m2[j-1]), 1)\n", "            c3 = mat[i-1, j-1] + c\n", "            mat[i, j] = min([c1, c2, c3])\n", "            \n", "            if i >= 2:\n", "                cc = cmp_char.get((m1[i-2:i], m2[j-1]), 1)\n", "                c4 = mat[i-2, j-1] + cc\n", "                mat[i, j] = min(mat[i, j], c4)\n", "            if j >= 2:\n", "                cc = cmp_char.get((m1[i-1], m2[j-2:j]), 1)\n", "                c4 = mat[i-1, j-2] + cc\n", "                mat[i, j] = min(mat[i, j], c4)\n", "            \n", "    return mat[-1, -1]\n", "\n", "print(\"edit\", edit_distance('agrafe', 'agrae'))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Test unitaire [again](https://www.youtube.com/watch?v=dBN86y30Ufc)."]}, {"cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [], "source": ["def test_special(d):\n", "    assert d('r\u00e9mun\u00e9rer', 'r\u00e9num\u00e9rer') == 1\n", "    assert d('agrafe', 'agrae') == 1\n", "    assert d('agraffe', 'agrafe') == 0.5\n", "    assert d('\u00e9l\u00e9phant', '\u00e9l\u00e9fant') == 0.4\n", "\n", "def test_edit_distance3():\n", "    test_dist_equal(edit_distance3)\n", "    test_dist_diff1(edit_distance3)\n", "    test_dist_diff2(edit_distance3)\n", "    test_special(edit_distance3)\n", "    \n", "test_edit_distance3()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["[This is the end](https://www.youtube.com/watch?v=VScSEXRwUqQ)."]}, {"cell_type": "code", "execution_count": 17, "metadata": {}, "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.9.5"}}, "nbformat": 4, "nbformat_minor": 2}