.. _2018-09-25distanceentremotsrst:

================================
2018-09-25 - Distance entre mots
================================


.. only:: html

    **Links:** :download:`notebook <2018-09-25_distance_entre_mots.ipynb>`, :downloadlink:`html <2018-09-25_distance_entre_mots2html.html>`, :download:`python <2018-09-25_distance_entre_mots.py>`, :downloadlink:`slides <2018-09-25_distance_entre_mots.slides.html>`, :githublink:`GitHub|_doc/notebooks/notebook_eleves/2018-2019/2018-09-25_distance_entre_mots.ipynb|*`


La distance proposée est naïve puisqu’elle considère uniquement les
lettres communes entre deux mots.

:math:`m =\{ c_1, ..., c_n\}`

:math:`C = m_1 \cap m_2`

:math:`d(m_1,m_2)=\#\{c \in m_1 \backslash C\} + \#\{c \in m_2 \backslash C\}`

Un indice pour l’implémenter : il peut être utile de passer par les
dictionnaires.

.. code:: ipython3

    def compte(mot):
        d = {}
        for c in mot:
            d[c] = d.get(c, 0) + 1
        return d
    
    compte("aza")




.. parsed-literal::
    {'a': 2, 'z': 1}



.. code:: ipython3

    def distance_simple(h1, h2):
        d = 0
        tout = set(h1).union(set(h2))
        for c in tout:
            d += abs(h1.get(c, 0) - h2.get(c, 0))
        return d
    
    distance_simple(compte("journal"), compte("journaux"))




.. parsed-literal::
    3



.. code:: ipython3

    distance_simple(compte("journal"), compte("naljour"))




.. parsed-literal::
    0



La distance ne tient pas compte de l’ordre des lettres, on en tient
compte de façon locale en considèrent les couples de lettres
consécutives plutôt que les lettres.

.. code:: ipython3

    def decoupe(mot):
        couples = []
        for i in range(1, len(mot)):
            couples.append(mot[i-1:i+1])
        return [mot[:1]] + couples + [mot[-1:]]
    decoupe("journal")




.. parsed-literal::
    ['j', 'jo', 'ou', 'ur', 'rn', 'na', 'al', 'l']



Mais ce n’est pas une distance à proprement parler comme en témoigne le
contre-exemple suivant :

.. code:: ipython3

    distance_simple(compte(decoupe("ninon")),
                    compte(decoupe("nonin")))




.. parsed-literal::
    0



.. code:: ipython3

    distance_simple(compte(decoupe("journal")),
                    compte(decoupe("jourinal")))




.. parsed-literal::
    3



.. code:: ipython3

    distance_simple(compte(decoupe("journal")),
                    compte(decoupe("naljour")))




.. parsed-literal::
    6



On passe alors à la distance d’édition :

.. code:: ipython3

    def distance_edition(m1, m2):
        mat = [[len(m1) + len(m2) for j in range(len(m2))] for i in range(len(m1))]
        drt = [["n" for j in range(len(m2))] for i in range(len(m1))]
        mat[0][0] = 0 if m1[0] == m2[0] else 1
        for i in range(len(m1)):
            for j in range(len(m2)):
                if i > 0 and mat[i][j] > mat[i-1][j] + 1:
                    mat[i][j] = mat[i-1][j] + 1
                    drt[i][j] = "^"
                if j > 0 and mat[i][j] > mat[i][j-1] + 1:
                    mat[i][j] = mat[i][j-1] + 1
                    drt[i][j] = "<"
                if i > 0 and j > 0:
                    c = 0 if m1[i] == m2[j] else 1
                    if mat[i][j] > mat[i-1][j-1] + c:
                        mat[i][j] = mat[i-1][j-1] + c
                        drt[i][j] = "=" if c == 0 else "\\"
        return mat[len(m1)-1][len(m2)-1], drt
    
    d, drt = distance_edition("jourinal", "joirnal")
    d




.. parsed-literal::
    2



Pour retrouver le chemin, il suffit de remonter le chemin suivant depuis
l’arrivée jusqu’au point de départ.

.. code:: ipython3

    for l in drt:
        print(" ".join(l))


.. parsed-literal::
    n < < < < < <
    ^ = < < < < <
    ^ ^ \ < < < <
    ^ ^ ^ = < < <
    ^ ^ = ^ \ < <
    ^ ^ ^ ^ = < <
    ^ ^ ^ ^ ^ = <
    ^ ^ ^ ^ ^ ^ =