.. _2020editrst:

==========================
Algo - distance d’édiction
==========================


.. only:: html

    **Links:** :download:`notebook <2020_edit.ipynb>`, :downloadlink:`html <2020_edit2html.html>`, :download:`python <2020_edit.py>`, :downloadlink:`slides <2020_edit.slides.html>`, :githublink:`GitHub|_doc/notebooks/td1a_home/2020_edit.ipynb|*`


La distance d’édition 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équences.

.. code:: ipython3

    from jyquickhelper import add_notebook_menu
    add_notebook_menu()






.. contents::
    :local:





.. code:: ipython3

    %matplotlib inline

Enoncé
------

Q1 : Distance simple entre deux mots de même longueur
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Une distance entre deux mots… c’est plus simple si les deux mots ont la
même longueur, on calcule le nombre de différences.


Q2 : Distance simple entre deux mots de longueur différente
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

On construit cette distance comme la différence des longueurs + la
distance entre le mot le plus court et toutes les sous-séquences de même
longueur issues de la chaîne la plus longue.


Q3 : Distance alambiquée…
~~~~~~~~~~~~~~~~~~~~~~~~~

Cette fois-ci, on coupe chacun des deux mots en deux, au hasard. On
applique la distance précédente sur chacun des deux tronçons. On fait la
somme. Il ne reste plus qu’à minimiser cette somme sur l’ensemble des
coupures possibles.


Q4 : implémenter l’algorithme de la page wikipedia
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

`Levenshtein <https://fr.wikipedia.org/wiki/Distance_de_Levenshtein>`__



Réponses
--------

Q1 : Distance simple entre deux mots de même longueur
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Une distance entre deux mots… c’est plus simple si les deux mots ont la
même longueur, on calcule le nombre de différences.

.. code:: ipython3

    def distance_meme_longueur(m1, m2):
        if len(m1) != len(m2):
            raise ValueError("m1 et m2 sont de longueurs différentes")
        d = 0
        for c1, c2 in zip(m1, m2):
            if c1 != c2:
                d += 1
        return d
    
    distance_meme_longueur('abcef', 'abcde')




.. parsed-literal::
    2



On vérifie que la fonctionne jette bien une exception lorsque les
chaînes de caractères sont de longueurs différentes.

.. code:: ipython3

    try:
        distance_meme_longueur('a', 'bb')
    except Exception as e:
        print(e)


.. parsed-literal::
    m1 et m2 sont de longueurs différentes


Q2 : Distance simple entre deux mots de longueur différente
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

On construit cette distance comme la différence des longueurs + la
distance entre le mot le plus court et toutes les sous-séquences de même
longueur issues de la chaîne la plus longue.

.. code:: ipython3

    def distance(m1, m2):
        if len(m1) < len(m2):
            return distance(m2, m1)
        if len(m1) == len(m2):
            return distance_meme_longueur(m1, m2)
        d = len(m1) - len(m2)
        mind = [distance_meme_longueur(m1[i:i+len(m2)], m2)
                for i in range(0, d)]
        return d + min(mind)
            
    distance('aa', 'aa'), distance('aa', 'aaa'),  distance('aa', 'bbb')




.. parsed-literal::
    (0, 1, 3)



Q3 : Distance alambiquée…
~~~~~~~~~~~~~~~~~~~~~~~~~

Cette fois-ci, on coupe chacun des deux mots en deux, au hasard. On
applique la distance précédente sur chacun des deux tronçons. On fait la
somme. Il ne reste plus qu’à minimiser cette somme sur l’ensemble des
coupures possibles.

.. code:: ipython3

    def distance_alambiquee(m1, m2):
        mini = None
        for i in range(len(m1)):
            for j in range(len(m2)):
                d = distance(m1[:i], m2[:j]) + distance(m1[i:], m2[j:])
                if mini is None or d < mini:
                    mini = d
                # Option verlan
                d = distance(m1[:i], m2[j:]) + distance(m1[i:], m2[:j]) + 0.5
                if d < mini:
                    mini = d
        return mini
    
    (distance('abc', 'ac'),
     distance_alambiquee('abc', 'ac'),
     distance_alambiquee('abc', 'ca'),
     distance_alambiquee('b', 'b'))




.. parsed-literal::
    (2, 1, 1.5, 0)




Q4 : implémenter l’algorithme de la page wikipedia
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

`Levenshtein <https://fr.wikipedia.org/wiki/Distance_de_Levenshtein>`__

La première implémentation reprend l’algorithme décrit sur la page
wikipédia.

.. code:: ipython3

    def levenstein(m1, m2):
        d = {}
        d[0,0] = 0
        for i in range(len(m1) + 1):
            d[i, 0] = i
        for j in range(len(m2) + 1):
            d[0, j] = j
        for i in range(1, len(m1) + 1):
            for j in range(1, len(m2) + 1):
                d[i, j] = min(d[i-1,j] +1, d[i,j-1] +1,
                    d[i-1, j-1] + (1 if m1[i-1] != m2[j-1] else 0))
        return d[len(m1), len(m2)]
    
    levenstein('abc', 'ac')




.. parsed-literal::
    1



La seconde version est plus alambiquée, elle modifie légèrement la
version alambiquée. C’est une version récursive.

.. code:: ipython3

    def distance_alambiquee_levenstein(m1, m2):
        mini = None
        for i in range(len(m1)):
            for j in range(len(m2)):
                if i > 0 and i < len(m1) - 1 and j > 0 and j < len(m2) - 1:
                    d1 = distance_alambiquee_levenstein(m1[:i], m2[:j])
                    d2 = distance_alambiquee_levenstein(m1[i:], m2[j:])
                else:
                    d1 = distance(m1[:i], m2[:j])
                    d2 = distance(m1[i:], m2[j:])
                d = d1 + d2
                if mini is None or d < mini:
                    mini = d
        return mini
    
    (distance_alambiquee('abcde', 'ace'),
     levenstein('abcde', 'ace'),
     distance_alambiquee_levenstein('abcde', 'ace'))




.. parsed-literal::
    (3, 2, 2)