TP : code de Huffman¶

Exercice 1. Utilisation de la bibliothèque.¶

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

In [2]:
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.

In [ ]:

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.

In [ ]:

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".

In [ ]:

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

              0
             /
            1
           /
          2
         /
        3
       /
      4
     /
    5
   /
  6
 /
7
In [ ]:

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)}
In [ ]:
p = { "a":0.4, "b":0.3, "c":0.2, "d":0.1 }

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

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

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

In [ ]:

É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)

In [ ]:

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

In [ ]:
def huffman(p):
    pass

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
In [ ]: