Levenstein vs. les Sup

On utilisera pour ce TP Spyder. On pourra télécharger les projets anonymisés des Sup ici.

1. Chargement des codes sources

Un code source est représenté par la liste de ses lignes. Une ligne de code source est une chaîne de caractère.

Par exemple, le code suivant :

def maximum(l) :
    m = -float("inf")
    for x in l :
        if x > m :
            m = x
    return m

Est représenté par la liste :

['def maximum(l) :', '    m = -float("inf")', '    for x in l :', '        if x > m :', '            m = x', '    return m']

1.1. Chargement d’un code source.

Écrire une fonction chargement(chemin : str) -> list[str] qui prend en entrée le chemin d’un fichier et qui renvoie la liste des lignes du fichier.

N.B. : ici.

Correction

def chargement(chemin) :
    fichier = open(chemin,'r')
    return fichier.readlines()

1.2. Chargement des projets.

Les projets anonymisés qui vous avez télécharger sont au nombre de 128. Il sont numéroté à partir de 0 et le projet numéro i se nomme proj_music_i.py (proj_music_0.py, proj_music_1.py, \ldots).

Écrire une fonction projets(nombre : int) -> list[list[str]] qui prend en entrée le nombre de projets et qui renvoie la liste des codes sources des projets, comme obtenus par la fonction chargement. Le projet numéro i sera à l’indice i de la liste.

On pourra utiliser str(n) pour convertir un entier n en sa représentation textuelle.

Correction

def projets(n) :
    return [ chargement("proj_music_ano/proj_music_" + str(i) + ".py")
             for i in range(n) ]

2. Étude du problème

La distance de Levenstein entre deux codes sources c1 et c2 est définie comme le nombre minimal d’opération qu’il faut effectuer pour passer de c1 à c2 parmi :

La suppression d’une ligne de c1.
L’insertion d’une ligne quelconque dans c1.
La substitution d’une ligne complète dans c1.

Chacune de ces opérations coûtera 1, bien qu’elle consiste en la manipulation de ligne entière.

Le problème Lev est donc le calcul de la valeur de la distance de Levenstein sur deux codes sources données en entrées.

On fixe c1 et c2 deux codes sources, entrées du problème Lev. La taille des entrées consiste en le nombre de ligne de ces codes sources. Les sous problèmes auxquels nous allons nous restreindre sont les calculs de la distance de Levenstein sur les sous listes des $i$ premières lignes de c1 et des $j$ première ligne de c2.

On les notes L(i,j) = Lev(c1[:i],c2[:j]).

2.1. Propriété de sous problèmes optimaux.

Exprimer Lev(c1,c2) en fonction de L.
Donner une valeur pour L(0,j).
Donner une valeur pour L(i,0).
Proposer une relation de récurrence pour obtenir L(i+1,j+1) en fonction de
- L(i,j+1)
- L(i+1,j)
- L(i,j)
On pourra distinguer les cas c1[i] == c2[j] et c1[i] != c2[j].

Correction

Lev(c1,c2) = L(len(c1), len(c2))
L(0,j) = j.
L(i,0) = i.
Relation de récurrence :
- L(i+1,j+1) = L(i,j) si c1[i] = c2[j]
- L(i+1,j+1) = 1 + min(L(i,j+1), L(i+1,j), L(i,j)) sinon

2.2. Chevauchement.

Trouver deux sous problèmes dépendant pour les codes sources suivants :

def somme_liste(_X) :
    _X = 0
    for _X in _X  :
        _X = _X + _X
    return _X

def max_liste(_X) :
    _X = -float("inf")
    for _X in _X  :
        if _X < _X :
            _X = _X
    return _X

Correction

Le sous problèmes L(3,3) sera utile pour le calcul de L(3,4) et L(4,3). Ces deux derniers sont donc dépendants.

3. Distance de Levenstein

3.1. Distance de deux codes sources (descendante).

Implémentez en version descendante efficace la fonction levenstein(c1,c2) qui prend deux codes sources sous la forme de la liste de leurs ligne et qui renvoie la distance de Levenstein de ces deux codes.

Calculez la complexité de votre fonction.

Correction

def min(a,b,c) :
    if a < b and a < c:
        return a
    if b < c :
        return b
    return c
 
def L(i,j,c1,c2,memo) :
    if (i,j) in memo :
        return memo[(i,j)]
    if i == 0 :
        memo[(i,j)] = j
        return j
    if j == 0 :
        memo[(i,j)] = j
        return i
    if c1[i-1] == c2[j-1] :
        res = L(i-1,j-1,c1,c2,memo)
        memo[(i,j)] = res
        return res
    a = L(i-1,j,c1,c2,memo)
    b = L(i,j-1,c1,c2,memo)
    c = L(i-1,j-1,c1,c2,memo)
    res = 1 + min(a,b,c)
    memo[(i,j)] = res
    return res
 
def levenstein(c1,c2) :
    return L(len(c1),len(c2),c1,c2,{})

La complexité de la fonction correspond au nombre de sous problèmes utiles, multiplié par la complexité d’un appel (en dehors des appels récursifs).

Un appel de fonction est en $\O(1)$. Le nombre de sous problèmes utiles peut être majoré par len(c1)len(c2), le complexité finale est donc en $\O$(len(c1)len(c2)).

3.2. Distance de deux codes sources (montante).

Implémentez en version montante efficace de la fonction levenstein(c1,c2) qui prend deux codes sources sous la forme de la liste de leurs ligne et qui renvoie la distance de Levenstein de ces deux codes.

Calculez la complexité de votre fonction.

Correction

Pour la version montante on peut considérer une matrice $n_1 \times n_2$ avec $n_1$ = len(c1) et $n_2$ = len(c2). Dans chaque case i,j on stockera le résultat de L(i,j). Les sous problèmes de départ sont la première ligne et première colonne de la matrice. La ligne i+1 peut être calculé depuis la ligne i.

def levenstein(c1,c2) :
    n1, n2 = len(c1), len(c2)
    # Création de la matrice avec la première ligne, L(0,j).
    # et la première colonne L(i,0).
    L = [ [ j for j in range(n2+1)] ]
    for i in range(1,n1+1) :
        ligne = [i]
        ligne += [0] * n2
        L.append(ligne)
    # Calcul des sous problèmes.
    for i in range(1,n1+1) :
        for j in range(1,n2+1) :
            if c1[i-1] == c2[j-1] :
                ligne[i][j] = ligne[i-1][j-1]
            else :
                a = ligne[i-1][j]
                b = ligne[i][j-1]
                c = ligne[i-1][j-1]
                ligne[i][j] = 1 + min(a,b,c)
    return L[n1][n2]

La complexité de la fonction est encore en $\O$(len(c1)len(c2)).

A noter qu’il n’est pas forcément nécessaire de stocker toute la matrice. On peut conserver uniquement la ligne précédente.

3.3. Distance de tous les projets

Implémentez une fonction diffs(projs) qui prend en entrée la liste des projets telle que renvoyée par la fonction projets, et qui renvoie une matrice contenant à la ligne i, colonne j, la distance de Levenstein des codes sources numérotés i et j.

N.B. : La matrice est symétrique à diagonale nulle.

Correction

def diffs(projs) :
    n = len(projs)
    mat_diffs = [ [0] * n for i in range(n) ]
    for i in range(n) :
        for j in range(i) :
            mat_diffs[i][j] = levenstein(projs[i], projs[j])
            mat_diffs[j][i] = mat_diffs[i][j]
    return mat_diffs

3.4. Extraction de données

Pour les extractions si dessus, ne pas prendre en compte les 0 de la diagonale.

Relevez la moyenne des distances des codes.
Relevez la plus grande et la plus petite distance.
Relevez les couples de projets qui ont distance plus petite que 50% de la moyenne.
Relevez les couples de projets qui ont distance plus petite que 25% de la moyenne.
Donnez une liste contenant à l’indice i, le numéro du code le plus proche du code i, ansi que la distance qui les sépare.

Correction

projs = projets(chemin)
mat_diffs = diffs(projs)

def stats_diffs(mat_diffs) :
    n = len(mat_diffs)
    somme = 0
    cardinal = 0
    maximum = -float("inf")
    couple_maximum = None
    minimum = float("inf")
    couple_minimum = None
    for i in range(n) :
        for j in range(i) :
            d = mat_diffs[i][j]
            somme += d
            if d > maximum :
                maximum = d
                couple_maximum = (i,j)
            if d < minimum :
                minimum = d
                couple_minimum = (i,j)
            cardinal += 1
    return somme / cardinal, couple_maximum, maximum, couple_minimum, minimum
 
moyenne, c_maximum, maximum, c_minimum, minimum = stats_diffs(mat_diffs)

def trop_proches(mat_diffs, moyenne) :
    n = len(mat_diffs)
    m25 = moyenne * 0.25
    m50 = moyenne * 0.5
    l25, l50 = [], []
    for i in range(n) :
        for j in range(i) :
            d = mat_diffs[i][j]
            if s < m25 :
                l25.append( (d,(i,j)) )
                l50.append( (d,(i,j)) )
            elif s < m50 :
                l50.append( (d,(i,j)) )
    return l25, l50
 
def couples(mat_diffs) :
    n = len(mat_diffs)
    couples = [None] * n
    for i in range(n) :
        min_i = float("inf")
        proche = -1
        for j in range(n) :
            if i != j :
                d = mat_diffs[i][j]
                if d < min_i :
                    min_i = d
                    proche = j
        couples[i] = (min_i,proche)
    return couples
 
suspects = trop_proches(mat_diffs, moyenne)
BFFs = couples(mat_diffs)