{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# Algo - distance d'\u00e9diction\n", "\n", "La distance d'\u00e9dition ou distance de [Levenshtein](https://en.wikipedia.org/wiki/Levenshtein_distance) permet de calculer une distance entre deux mots et par extension entre deux s\u00e9quences."]}, {"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": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": ["%matplotlib inline"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Enonc\u00e9\n"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q1 : Distance simple entre deux mots de m\u00eame longueur\n", "\n", "Une distance entre deux mots... c'est plus simple si les deux mots ont la m\u00eame longueur, on calcule le nombre de diff\u00e9rences."]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q2 : Distance simple entre deux mots de longueur diff\u00e9rente\n", "\n", "On construit cette distance comme la diff\u00e9rence des longueurs + la distance entre le mot le plus court et toutes les sous-s\u00e9quences de m\u00eame longueur issues de la cha\u00eene la plus longue."]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q3 : Distance alambiqu\u00e9e...\n", "\n", "Cette fois-ci, on coupe chacun des deux mots en deux, au hasard. On applique la distance pr\u00e9c\u00e9dente sur chacun des deux tron\u00e7ons. On fait la somme. Il ne reste plus qu'\u00e0 minimiser cette somme sur l'ensemble des coupures possibles."]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q4 : impl\u00e9menter l'algorithme de la page wikipedia\n", "\n", "[Levenshtein](https://fr.wikipedia.org/wiki/Distance_de_Levenshtein)"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## R\u00e9ponses"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q1 : Distance simple entre deux mots de m\u00eame longueur\n", "\n", "Une distance entre deux mots... c'est plus simple si les deux mots ont la m\u00eame longueur, on calcule le nombre de diff\u00e9rences."]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"data": {"text/plain": ["2"]}, "execution_count": 9, "metadata": {}, "output_type": "execute_result"}], "source": ["def distance_meme_longueur(m1, m2):\n", "    if len(m1) != len(m2):\n", "        raise ValueError(\"m1 et m2 sont de longueurs diff\u00e9rentes\")\n", "    d = 0\n", "    for c1, c2 in zip(m1, m2):\n", "        if c1 != c2:\n", "            d += 1\n", "    return d\n", "\n", "distance_meme_longueur('abcef', 'abcde')"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On v\u00e9rifie que la fonctionne jette bien une exception lorsque les cha\u00eenes de caract\u00e8res sont de longueurs diff\u00e9rentes."]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["m1 et m2 sont de longueurs diff\u00e9rentes\n"]}], "source": ["try:\n", "    distance_meme_longueur('a', 'bb')\n", "except Exception as e:\n", "    print(e)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q2 : Distance simple entre deux mots de longueur diff\u00e9rente\n", "\n", "On construit cette distance comme la diff\u00e9rence des longueurs + la distance entre le mot le plus court et toutes les sous-s\u00e9quences de m\u00eame longueur issues de la cha\u00eene la plus longue."]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [{"data": {"text/plain": ["(0, 1, 3)"]}, "execution_count": 11, "metadata": {}, "output_type": "execute_result"}], "source": ["def distance(m1, m2):\n", "    if len(m1) < len(m2):\n", "        return distance(m2, m1)\n", "    if len(m1) == len(m2):\n", "        return distance_meme_longueur(m1, m2)\n", "    d = len(m1) - len(m2)\n", "    mind = [distance_meme_longueur(m1[i:i+len(m2)], m2)\n", "            for i in range(0, d)]\n", "    return d + min(mind)\n", "        \n", "distance('aa', 'aa'), distance('aa', 'aaa'),  distance('aa', 'bbb')"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q3 : Distance alambiqu\u00e9e...\n", "\n", "Cette fois-ci, on coupe chacun des deux mots en deux, au hasard. On applique la distance pr\u00e9c\u00e9dente sur chacun des deux tron\u00e7ons. On fait la somme. Il ne reste plus qu'\u00e0 minimiser cette somme sur l'ensemble des coupures possibles."]}, {"cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [{"data": {"text/plain": ["(2, 1, 1.5, 0)"]}, "execution_count": 12, "metadata": {}, "output_type": "execute_result"}], "source": ["def distance_alambiquee(m1, m2):\n", "    mini = None\n", "    for i in range(len(m1)):\n", "        for j in range(len(m2)):\n", "            d = distance(m1[:i], m2[:j]) + distance(m1[i:], m2[j:])\n", "            if mini is None or d < mini:\n", "                mini = d\n", "            # Option verlan\n", "            d = distance(m1[:i], m2[j:]) + distance(m1[i:], m2[:j]) + 0.5\n", "            if d < mini:\n", "                mini = d\n", "    return mini\n", "\n", "(distance('abc', 'ac'),\n", " distance_alambiquee('abc', 'ac'),\n", " distance_alambiquee('abc', 'ca'),\n", " distance_alambiquee('b', 'b'))"]}, {"cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q4 : impl\u00e9menter l'algorithme de la page wikipedia\n", "\n", "[Levenshtein](https://fr.wikipedia.org/wiki/Distance_de_Levenshtein)\n", "\n", "La premi\u00e8re impl\u00e9mentation reprend l'algorithme d\u00e9crit sur la page wikip\u00e9dia."]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [{"data": {"text/plain": ["1"]}, "execution_count": 14, "metadata": {}, "output_type": "execute_result"}], "source": ["def levenstein(m1, m2):\n", "    d = {}\n", "    d[0,0] = 0\n", "    for i in range(len(m1) + 1):\n", "        d[i, 0] = i\n", "    for j in range(len(m2) + 1):\n", "        d[0, j] = j\n", "    for i in range(1, len(m1) + 1):\n", "        for j in range(1, len(m2) + 1):\n", "            d[i, j] = min(d[i-1,j] +1, d[i,j-1] +1,\n", "                d[i-1, j-1] + (1 if m1[i-1] != m2[j-1] else 0))\n", "    return d[len(m1), len(m2)]\n", "\n", "levenstein('abc', 'ac')"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La seconde version est plus alambiqu\u00e9e, elle modifie l\u00e9g\u00e8rement la version alambiqu\u00e9e. C'est une version r\u00e9cursive."]}, {"cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [{"data": {"text/plain": ["(3, 2, 2)"]}, "execution_count": 15, "metadata": {}, "output_type": "execute_result"}], "source": ["def distance_alambiquee_levenstein(m1, m2):\n", "    mini = None\n", "    for i in range(len(m1)):\n", "        for j in range(len(m2)):\n", "            if i > 0 and i < len(m1) - 1 and j > 0 and j < len(m2) - 1:\n", "                d1 = distance_alambiquee_levenstein(m1[:i], m2[:j])\n", "                d2 = distance_alambiquee_levenstein(m1[i:], m2[j:])\n", "            else:\n", "                d1 = distance(m1[:i], m2[:j])\n", "                d2 = distance(m1[i:], m2[j:])\n", "            d = d1 + d2\n", "            if mini is None or d < mini:\n", "                mini = d\n", "    return mini\n", "\n", "(distance_alambiquee('abcde', 'ace'),\n", " levenstein('abcde', 'ace'),\n", " distance_alambiquee_levenstein('abcde', 'ace'))"]}, {"cell_type": "code", "execution_count": 15, "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.7.2"}}, "nbformat": 4, "nbformat_minor": 2}