TP : code de Huffman

Exercice 1. Utilisation de la bibliothèque.

Dans cet exercice, on va apprendre à utiliser la bibliothèque binarytree de python.

from binarytree import *

La fonction Node(x) permet de créer un arbre constitué d'une feuille, dont l'étiquette est x.

Question 1.- Créer un arbre T constitué d'une feuille, dont l'étiquette est le caractère a. Puis, afficher cet arbre avec la commande print.

T = Node("a")
print(T)

a

Pour créer un arbre plus complexe, l'idée est d'assigner des descendants aux noeuds de l'arbre. Les descendants droit et gauche d'un noeud doivent eux-même être des noeuds. Par exemple, si T est un noeud et G est un autre noeud, alors on peut demander à ce que G soit le descendant à gauche de T en écrivant T.left = G.

Question 2.- Créer un arbre binaire de hauteur $1$, dont la racine a pour étiquette 0, la feuille gauche a pour étiquette a et la feuille droite a pour étiquette b. Puis, afficher cet arbre.

T = Node("0")
T.left = Node("a")
T.right = Node("b")
print(T)

  0
 / \
a   b

On accède à l'étiquette d'un noeud T grâce à l'attibut T.value

Question 3.- Modifier l'arbre précédent pour que l'étiquette de la racine soit le caractère "x".

T.value = "x"
print(T)

  x
 / \
a   b

Question 4.- À l'aide d'une boucle, créer l'arbre suivant :

              0
             /
            1
           /
          2
         /
        3
       /
      4
     /
    5
   /
  6
 /
7

A = Node(0)
T = A
for i in range(1, 8):
    T.left = Node(i)
    T = T.left
print(A)

              0
             /
            1
           /
          2
         /
        3
       /
      4
     /
    5
   /
  6
 /
7

Exercice 2. Code de Huffman

Pour rappel, l'algorithme de Huffman fonctionne de la sorte. Il prend en entrée une distribution $p = (p(x_1), \dots, p(x_n))$, et calcule un arbre binaire de la manière suivante.

1. On initialise une séquence D d'arbres-feuilles, dont les étiquettes sont les symboles $(x_1, \dots, x_n)$
2. Tant que la séquence contient au moins deux arbres : 1. on trouve dans la distribution $p$ les deux valeurs minimales $p(x_i)$ et $p(x_j)$ 2. on identifie dans D les deux arbres correspondants $T_i$ et $T_j$ 3. on retire $p(x_i)$ et $p(x_j)$ de $p$, et on lui rajoute la probabilité formée de la somme de ces probabilités 4. on retire les arbres $T_i$ et $T_j$ de D, et on lui rajoute l'arbre formé de la réunion de ces deux sous-arbres
3. On retourne de dernier arbre de la séquence

Pour implanter l'algorithme, nous allons utiliser une structure de dictionnaire pour représenter à la fois les "séquences d'arbres" et les distributions. Le dictionnaire D correspondant aura comme clés des couples $(x, p(x))$, où $x$ représente la concaténation des symboles dans l'arbre, et $p(x)$ la somme des probabilités correspondantes. La valeur D[k] de la clé k = (x, p(x)) sera l'arbre correspondant.

Pour bien se le reprsenter, commençons par initialiser ce dictionnaire.

Question 1.- Étant donnée une distribution $p$ stockée sous forme de dictionnaire, construire le dictionnaire initial D, dont les clés sont les couples $(x, p(x))$ et dont les valeurs sont les arbres-feuilles d'étiquette $x$.

Exemple : si la source a pour alphabet $\{ a, b, c, d \}$ et pour distribution associée $p = (0.4, 0.3, 0.2, 0.1)$, alors on doit obtenir le dictionnaire :

D = {('a', 0.4): Node(a), ('b', 0.3): Node(b), ('c', 0.2): Node(c), ('d', 0.1): Node(d)}

p = { "a":0.4, "b":0.3, "c":0.2, "d":0.1 }
D = { (x, p[x]): Node(x) for x in p }
print(D)

{('a', 0.4): Node(a), ('b', 0.3): Node(b), ('c', 0.2): Node(c), ('d', 0.1): Node(d)}

# Une syntaxe équivalente est la suivante :
D = dict()   # on définit le dictionnaire vide
for x in p:
    D[ (x, p[x]) ] = Node(x)
print(D)

{('a', 0.4): Node(a), ('b', 0.3): Node(b), ('c', 0.2): Node(c), ('d', 0.1): Node(d)}

Dans le dictionnaire D, on peut obtenir la clé $(x, p(x))$ correspondant à la probabilité $p(x)$ la plus faible en écrivant :

min(D, key=lambda y:y[1])

Concrètement, cela signifie que l'on cherche, dans le dictionnaire D, la valeur minimale de la deuxième entrée de la clé. Pour cela, on a besoin de définir une fonction "local" qui accède au à la deuxième entrée de la clé : c'est le sen de lambda y:y[1]. Voir https://www.pythoniste.fr/python/a-quoi-servent-les-fonctions-lambdas-en-python/ pour des explications rapides de l'utilisation des focntions lambda en python.

Question 2.- Vérifier cela en exécutant le code ci-dessus.

min(D, key=lambda y:y[1])

('d', 0.1)

Étant donné un dictionnaire d'arbres D sous la forme présentée ci-dessus, on souhaite effectuer une étape de boucle de l'algorithme de Huffman. À savoir :

1. stocker dans T1 et T2 les arbres de D dont les probabilités associées sont les plus petites
2. créer l'arbre T dont l'étiquette est la concaténation des étiquettes de T1 et T2 (par exemple séparée d'un "|"), et dont le sous-arbre gauche est T1 et le sous-arbre droit est T2
3. retirer T1 et T2 de D, et ajouter T dans D (avec la clé égale au couple formé de son étiquette concaténée et de sa probabilité "somme")

Question 3.- Écrire cette étape sur le dictionnaire D créé précédemment.

Sur l'exemple précédent, on doit obtenir quelque chose comme :

{('a', 0.4): Node(a), ('b', 0.3): Node(b), ('d|c', 0.3): Node(d|c)}

(il se peut qu'il y ait une erreur d'arrondi avec python)

# on cherche l'arbre dont la proba associée est la plus petite
k1 = min(D, key=lambda y:y[1])   # calcul de la clé correspondant à la proba minimale
T1 = D[k1]                       # obtention de l'arbre correspondant (dans le dictionnaire D)
p = k1[1]                        # obtention de la probabilité correspondante
D.pop(k1)                        # on retire cet arbre du dictionnaire

# puis on réitère pour la seconde probabilité la plus petite
k2 = min(D, key=lambda y:y[1])   
T2 = D[k2]
p += k2[1]                       # ici, on somme avec la probabilité précédente
D.pop(k2)

# enfin on contruit l'arbre "concaténé"
T = Node(T1.value + "|" + T2.value)   # T1.value + "|" + T2.value correspond à la valeur à assigner
T.left = T1                           # on créée le fils gauche
T.right = T2                          #          le fils droit
D[tuple([T.value, p])] = T            # puis on ajoute l'arbre nouvellement créé dans le dictionnaire

print(D)

{('a', 0.4): Node(a), ('b', 0.3): Node(b), ('d|c', 0.30000000000000004): Node(d|c)}

Question 4.- Reprendre toutes les étapes précédentes et implanter l'algorithme de Huffman.

def huffman(p):
    
    # On associe à chaque symbole un "arbre-feuille"
    # dans un dictionnaire
    D = { tuple([x, p[x]]): Node(x) for x in p }

    # On fusionne les arbres de manière itérative,
    # dans une boucle while
    while len(D) != 1:

        # on cherche les deux arbres à fusionner
        new_p = 0                         # la nouvelle proba = 0
        m1 = min(D, key=lambda y: y[1])   # symbole de proba min
        T1 = D[m1]                        # arbre associé
        new_p += m1[1]                    # mise à jour de la nouvelle proba
        D.pop(m1)                         # on le retire du dictionnaire
        m2 = min(D, key=lambda y: y[1])   # 2nd symbole de proba min
        T2 = D[m2]                        # 2nd arbre associé
        new_p += m2[1]                    # mise à jour de la nouvelle proba
        D.pop(m2)                         # on le retire du dictionnaire

        # on crée la fusion des deux arbres sélectionnés
        T = Node(T1.value + "|" + T2.value)                      # la racine
        T.left = T1                       # descendant gauche = T1
        T.right = T2                      # descendant droit = T2
        
        # on place cet arbre fusionné dans le dictionnaire
        D[tuple([T.value, new_p])] = T

    return D[list(D.keys())[0]]

Question 5.- Tester l'algorithme sur la distribution :

p = { "a":0.4, "b":0.3, "c":0.2, "d":0.1 }

Vous devriez obtenir :

  a|b|d|c____
 /           \
a           b|d|c___
           /        \
          b         d|c
                   /   \
                  d     c

p = { "a":0.4, "b":0.3, "c":0.2, "d":0.1 }
H = huffman(p)
print(H)

  a|b|d|c____
 /           \
a           b|d|c___
           /        \
          b         d|c
                   /   \
                  d     c