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.
- 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 }
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 :
- 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)
# 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