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
.
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.
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".
Question 4.- À l'aide d'une boucle, créer l'arbre suivant :
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.
- On initialise une séquence
D
d'arbres-feuilles, dont les étiquettes sont les symboles $(x_1, \dots, x_n)$ - 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$ deD
, et on lui rajoute l'arbre formé de la réunion de ces deux sous-arbres - 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 }
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.
É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 :
- stocker dans
T1
etT2
les arbres deD
dont les probabilités associées sont les plus petites - créer l'arbre
T
dont l'étiquette est la concaténation des étiquettes deT1
etT2
(par exemple séparée d'un "|"), et dont le sous-arbre gauche estT1
et le sous-arbre droit estT2
- retirer
T1
etT2
deD
, et ajouterT
dansD
(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)
Question 4.- Reprendre toutes les étapes précédentes et implanter l'algorithme de Huffman.
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