1A.algo - distance de Jaccard (dictionnaires) - correction

Links: notebook, html, PDF, python, slides, GitHub

De la distance de Jaccard à la distance de Levenshtein.

from jyquickhelper import add_notebook_menu
add_notebook_menu()

Exercice 1 : Constuire l’ensemble des lettres supprimées et ajoutées

Deux mots n’ont pas forcément la même longueur, il est donc difficile de les comparer lettre à lettre. De même, on ne doit pas tenir compte de l’ordre des lettres dans chaque mot. Cette contrainte peut paraître plus difficile à mettre en oeuvre. Pourtant, si on construit un résultat intermédiaire : le décompte de chaque lettre dans un mot.

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

compte_lettre("lettre"), compte_lettre("etre")
({'e': 2, 'l': 1, 'r': 1, 't': 2}, {'e': 2, 'r': 1, 't': 1})

Une lettre est ajoutée ou supprimée entre deux mots si son décompe est différent dans les deux dictionnaires. On s’en sert pour contruire la liste des lettres supprimées et ajoutées. Cela revient à construire la différence entre deux dictionnaires.

mot1 = "lettre"
mot2 = "etres"

d1 = compte_lettre(mot1)
d2 = compte_lettre(mot2)

suppression = {}
for l in d1:
    c1 = d1[l]
    c2 = d2.get(l, 0)  # la lettre l n'appartient pas forcément au second mot
    if c2 != c1:
        suppression[l] = c2 - c1

ajout = {}
for l in d2:
    if l not in d1:
        c1 = 0
        c2 = d2[l]
        if c2 != c1:
            ajout[l] = c2 - c1
    else:
        # on a déjà compté les lettres présentes dans les deux mots
        # lors de la première boucle
        pass

suppression, ajout
({'l': -1, 't': -1}, {'s': 1})

Exercice 2 : écrire une fonction qui calcule la distance de Jaccard

On copie et on colle le code précédent pour créer la distance.

def jaccard(mot1, mot2):
    d1 = compte_lettre(mot1)
    d2 = compte_lettre(mot2)

    suppression = {}
    for l in d1:
        c1 = d1[l]
        c2 = d2.get(l, 0)  # la lettre l n'appartient pas forcément au second mot
        if c2 != c1:
            suppression[l] = c2 - c1

    ajout = {}
    for l in d2:
        if l not in d1:
            c1 = 0
            c2 = d2[l]
            if c2 != c1:
                ajout[l] = c2 - c1
        else:
            # on a déjà compté les lettres présentes dans les deux mots
            # lors de la première boucle
            pass

    dist = sum(abs(x) for x in suppression.values()) + sum(abs(x) for x in ajout.values())
    return dist

jaccard("lettre", "etre"), jaccard("lettre", "etres")
(2, 3)
jaccard("marie", "aimer")
0
jaccard("hôpital", "hospital")
3

Exercice 3 : calculer la matrice des distances

Tout d’abord, on découpe un texte en mot. On remplace les tirets en espaces.

texte = "à combien sont ces six saucissons-ci, ces six saucisson-ci sont à six sous".replace("-", " ").split()
texte
['à',
 'combien',
 'sont',
 'ces',
 'six',
 'saucissons',
 'ci,',
 'ces',
 'six',
 'saucisson',
 'ci',
 'sont',
 'à',
 'six',
 'sous']

liste de listes

distl = [ [ jaccard(texte[i], texte[j]) for i in range(len(texte))] for j in range(len(texte))]
distl
[[0, 8, 5, 4, 4, 11, 4, 4, 4, 10, 3, 5, 0, 4, 5],
 [8, 0, 7, 6, 8, 9, 6, 6, 8, 8, 5, 7, 8, 8, 9],
 [5, 7, 0, 5, 5, 8, 7, 5, 5, 7, 6, 0, 5, 5, 4],
 [4, 6, 5, 0, 4, 9, 4, 0, 4, 8, 3, 5, 4, 4, 5],
 [4, 8, 5, 4, 0, 9, 4, 4, 0, 8, 3, 5, 4, 0, 5],
 [11, 9, 8, 9, 9, 0, 9, 9, 9, 1, 8, 8, 11, 9, 6],
 [4, 6, 7, 4, 4, 9, 0, 4, 4, 8, 1, 7, 4, 4, 7],
 [4, 6, 5, 0, 4, 9, 4, 0, 4, 8, 3, 5, 4, 4, 5],
 [4, 8, 5, 4, 0, 9, 4, 4, 0, 8, 3, 5, 4, 0, 5],
 [10, 8, 7, 8, 8, 1, 8, 8, 8, 0, 7, 7, 10, 8, 5],
 [3, 5, 6, 3, 3, 8, 1, 3, 3, 7, 0, 6, 3, 3, 6],
 [5, 7, 0, 5, 5, 8, 7, 5, 5, 7, 6, 0, 5, 5, 4],
 [0, 8, 5, 4, 4, 11, 4, 4, 4, 10, 3, 5, 0, 4, 5],
 [4, 8, 5, 4, 0, 9, 4, 4, 0, 8, 3, 5, 4, 0, 5],
 [5, 9, 4, 5, 5, 6, 7, 5, 5, 5, 6, 4, 5, 5, 0]]

dictionnaire

distd = { (w,y): jaccard(w,y) for w in texte for y in texte}
distd
{('ces', 'ces'): 0,
 ('ces', 'ci'): 3,
 ('ces', 'ci,'): 4,
 ('ces', 'combien'): 6,
 ('ces', 'saucisson'): 8,
 ('ces', 'saucissons'): 9,
 ('ces', 'six'): 4,
 ('ces', 'sont'): 5,
 ('ces', 'sous'): 5,
 ('ces', 'à'): 4,
 ('ci', 'ces'): 3,
 ('ci', 'ci'): 0,
 ('ci', 'ci,'): 1,
 ('ci', 'combien'): 5,
 ('ci', 'saucisson'): 7,
 ('ci', 'saucissons'): 8,
 ('ci', 'six'): 3,
 ('ci', 'sont'): 6,
 ('ci', 'sous'): 6,
 ('ci', 'à'): 3,
 ('ci,', 'ces'): 4,
 ('ci,', 'ci'): 1,
 ('ci,', 'ci,'): 0,
 ('ci,', 'combien'): 6,
 ('ci,', 'saucisson'): 8,
 ('ci,', 'saucissons'): 9,
 ('ci,', 'six'): 4,
 ('ci,', 'sont'): 7,
 ('ci,', 'sous'): 7,
 ('ci,', 'à'): 4,
 ('combien', 'ces'): 6,
 ('combien', 'ci'): 5,
 ('combien', 'ci,'): 6,
 ('combien', 'combien'): 0,
 ('combien', 'saucisson'): 8,
 ('combien', 'saucissons'): 9,
 ('combien', 'six'): 8,
 ('combien', 'sont'): 7,
 ('combien', 'sous'): 9,
 ('combien', 'à'): 8,
 ('saucisson', 'ces'): 8,
 ('saucisson', 'ci'): 7,
 ('saucisson', 'ci,'): 8,
 ('saucisson', 'combien'): 8,
 ('saucisson', 'saucisson'): 0,
 ('saucisson', 'saucissons'): 1,
 ('saucisson', 'six'): 8,
 ('saucisson', 'sont'): 7,
 ('saucisson', 'sous'): 5,
 ('saucisson', 'à'): 10,
 ('saucissons', 'ces'): 9,
 ('saucissons', 'ci'): 8,
 ('saucissons', 'ci,'): 9,
 ('saucissons', 'combien'): 9,
 ('saucissons', 'saucisson'): 1,
 ('saucissons', 'saucissons'): 0,
 ('saucissons', 'six'): 9,
 ('saucissons', 'sont'): 8,
 ('saucissons', 'sous'): 6,
 ('saucissons', 'à'): 11,
 ('six', 'ces'): 4,
 ('six', 'ci'): 3,
 ('six', 'ci,'): 4,
 ('six', 'combien'): 8,
 ('six', 'saucisson'): 8,
 ('six', 'saucissons'): 9,
 ('six', 'six'): 0,
 ('six', 'sont'): 5,
 ('six', 'sous'): 5,
 ('six', 'à'): 4,
 ('sont', 'ces'): 5,
 ('sont', 'ci'): 6,
 ('sont', 'ci,'): 7,
 ('sont', 'combien'): 7,
 ('sont', 'saucisson'): 7,
 ('sont', 'saucissons'): 8,
 ('sont', 'six'): 5,
 ('sont', 'sont'): 0,
 ('sont', 'sous'): 4,
 ('sont', 'à'): 5,
 ('sous', 'ces'): 5,
 ('sous', 'ci'): 6,
 ('sous', 'ci,'): 7,
 ('sous', 'combien'): 9,
 ('sous', 'saucisson'): 5,
 ('sous', 'saucissons'): 6,
 ('sous', 'six'): 5,
 ('sous', 'sont'): 4,
 ('sous', 'sous'): 0,
 ('sous', 'à'): 5,
 ('à', 'ces'): 4,
 ('à', 'ci'): 3,
 ('à', 'ci,'): 4,
 ('à', 'combien'): 8,
 ('à', 'saucisson'): 10,
 ('à', 'saucissons'): 11,
 ('à', 'six'): 4,
 ('à', 'sont'): 5,
 ('à', 'sous'): 5,
 ('à', 'à'): 0}

On compare le nombre de coefficients :

sum(len(_) for _ in distl)
225
len(distd)
100

Le dictionnaire paraît une meilleure option en terme de nombre de coefficients. Mais en terme d’espace mémoire occupé, le dictionnaire est largement plus conséquent.

import sys
sys.getsizeof(distl), sys.getsizeof(distd)
(192, 6240)

Pour ce petit exemple, la matrice paraît une bonne option mais lorsque les mots sont répétés un grand nombre de fois :

texte_grand = texte * 40

distl = [ [ jaccard(texte_grand[i], texte_grand[j]) for i in range(len(texte_grand))] for j in range(len(texte_grand))]
distd = { (w,y): jaccard(w,y) for w in texte_grand for y in texte_grand}
sum(len(_) for _ in distl), len(distd)
(360000, 100)
sys.getsizeof(distl), sys.getsizeof(distd)
(5496, 6240)

Le dictionnaire permet également de vérifier aisément qu’un calcul a déjà été effectué afin de gagner du temps et de ne pas le refaire.

distd = {}
for w in texte_grand:
    for y in texte_grand:
        if (w,y) not in distd:
            distd[w,y] = jaccard(w,y)
            distd[y,w] = distd[w,y]
len(distd)
100