Algorithmique des arbres

Codes, Arbres pondérés, Codage de Huffman

L2 Mathématique et Informatique
Outline

1 Introduction

2 Notion de codes

3 Codage de Huffman (1952)

Notion de cout associé à un arbre
Codage d’un texte
Décodage d’un texte

4 Implantation et représentation des données

5 Algorithme d’Huffman adaptatif

Compression d’un texte, sans perte de données
Objectif : Représenter une suite d’octets (le texte) par une suite
d’octets plus courte (le compressé) de sorte que le texte
reconstruit à partir du compressé soit identique à l’original.

Idée générale : Substituer un mot à une lettre !

Idée 1 : chaque lettre est codée par un mot de même longueur

Idée 2 : les lettres sont codées par des mots de longueurs variables :
les lettres apparaissant le plus grand nombre de
fois sont associées à des mots les plus courts pos-
sibles.

les lettres apparaissant peu de fois sont associées

à des mots potentiellement longs.

=⇒ Souvent, on gagne beaucoup ; rarement, on perd.

Longueur d’un texte compréssé

Propriété :
Si une lettre a est une lettre du texte apparaissant nb(a) fois dans le
texte et est associé à un mot de longueur l(a), alors la longueur du texte
compressé est
L(compressé) = nb(a) · l(a) .
X

a∈texte

Objectif : Minimiser la quantité L(compressé).

Exemple
Exemple :

Imaginons un texte de 1000 caractères dont le nombre d’occurences des

lettres est donné par :

Lettre a b c d e f
Nombre d’occurence 350 330 20 160 90 50

Lettre a b c d e f
Codage 1 :
Codage 000 001 010 011 100 101

=⇒ L(compressé) = 3000 bits

Lettre a b c d e f
Codage 2 :
Codage 0 11 10000 101 1001 10001

=⇒ L(compressé) = 350·1+330·2+20·5+160·3+90·4+50·5 = 2200 bits

Cela représente un gain d’un peu plus de 25%

Outline

1 Introduction

2 Notion de codes

3 Codage de Huffman (1952)

Notion de cout associé à un arbre
Codage d’un texte
Décodage d’un texte

4 Implantation et représentation des données

5 Algorithme d’Huffman adaptatif

Notion d’alphabet

Définition :
Soit A un ensemble, appelé un alphabet.
Un mot sur un alphabet A est une suite finie d’éléments de A.

Exemples :

Avec l’alphabet A = {0, 1, · · · , 9}, on construit des nombres :

2381, 0023, · · ·

Avec l’alphabet A = {0, 1}, on construit des mots dits binaires :

00100111

Avec l’alphabet A = {a, b, · · · , z}, on construit des ”mots

classiques” :
code, huffman, · · ·
Notion de code

Définition :
Soit A un ensemble, appelé alphabet.
Un code sur un alphabet A est un ensemble C de mots construits sur A
tels qu’une concaténation de mots de C ne peut être séparée en mots de
C que d’une unique façon :
Pour tous entiers n et p, pour tous mots x1 , · · · , xn , y1 , · · · , yp ∈ C,

p=n

x0 x1 . . . xn = y0 y1 . . . yp =⇒ (1)
∀i ∈ [[1; n]] , xi = yi

Définition :
Un code est dit binaire s’il est construit sur un alphabet à deux éléments.
(On identifiera alors ces deux lettres aux entiers 0 et 1).
Exemples

C0 = {001, 100, 010} est un code : tous ses mots sont de même
longueur

C1 = {1, 01, 001, . . . , 0n 1, n ∈ N} est un code : 1 est séparateur

C2 = {00, 1, 10} est un code, mais le délai de décodage est non

borné :
attendre le prochain 1 ou la fin
découper la séquence précédant le 1 de la gauche vers la droite

1001000101110 = 1|00|10|00|10|1|1|10

100000000 . . . = 1|00|00|00|00| . . . ou 10|00|00|00|0 . . . ?

Contre-exemple

C3 = {01, 1, 10, 11, 100} n’est pas un code :

10011 = 100|11 = 10|01|1 .

Code préfixe

Définition :
Un code préfixe est un ensemble C de mots sur un alphabet A dans
lequel aucun mot du code n’est préfixe d’un autre mot du code.

Remarque : Un code préfixe devrait plutôt s’appeler un code sans

préfixe, mais ce n’est pas la terminologie qui a été retenue...

Contre-exemple :

C2 = {00, 1, 10} est un code, mais il n’est pas préfixe :

1 est un préfixe de 10 C2 est un code suffixe !

Exemple :

C4 = {00, 01, 100, 1010, 1011} est un code préfixe.

Code préfixe et arbre binaire
Propriété :
L’ensemble des codes préfixes sur un alphabet à deux lettres est en
bijection avec l’ensemble des arbres binaires.

Preuve :

Etant donné un arbre binaire, on étiquette ses arêtes :

0 pour une arête gauche ;
1 pour une arête droite ;
on retrouve le code préfixe parcourant l’arbre binaire de la racine à
chaque feuille.

Etant donné un code préfixe, on ajoute successivement dans un

arbre binaire initialement vide une branche pour que chaque mot se
retrouve codé comme un chemin de la racine à une nouvelle feuille
(0 pour une arête gauche, 1 pour une arête droite)
Exemples 1/2

Exemple :

0 1

0 1

C = {000; 00110; 00111; 110}

0 1 0

0 1
Code binaire 2/2

Exemple :

C4 = {00; 01; 100; 1010; 1011}

Code binaire 2/2

Exemple :

0 1

C4 = {00; 01; 100; 1010; 1011}

Code binaire 2/2

Exemple :

0 1

0 1 0

C4 = {00; 01; 100; 1010; 1011}

0
Code binaire 2/2

Exemple :

0 1

0 1 0

C4 = {00; 01; 100; 1010; 1011}

0 1

0
Code binaire 2/2

Exemple :

0 1

0 1 0

C4 = {00; 01; 100; 1010; 1011}

0 1

0 1
Code binaire et factorisation d’un message
Propriété :
Un code préfixe sur un alphabet à deux lettres est un code : la
factorisation d’une suite de mot construite à partir du code préfixe est
unique.

Preuve :

Parcours de l’arbre binaire associé au code binaire à partir de la racine :

on sépare en arrivant à une feuille et on repart à la racine.

0 1
1100000011000110
0 1 C={000,00110,00111,110}
0 1 0
↓
1

0 1
110|000|00110|00110
Code binaire et factorisation d’un message

Propriété :
Un code préfixe est un code.

Preuve :

• Si l’alphabet associé au code possède N lettres, on associe au code

préfixe un arbre N-aire (tous les nœuds ont exactement N enfants,
éventuellement NULL)

• Parcours de l’arbre associé au code à partir de la racine :

on sépare en arrivant à une feuille et on repart à la racine.
Outline

1 Introduction

2 Notion de codes

3 Codage de Huffman (1952)

Notion de cout associé à un arbre
Codage d’un texte
Décodage d’un texte

4 Implantation et représentation des données

5 Algorithme d’Huffman adaptatif

Généralités

Objectif : Représenter une suite d’octets (le texte) par une suite
d’octets plus courte (le compressé) de sorte que le texte
reconstruit à partir du compressé soit identique à l’original.

=⇒ Compression de données sans perte

Le codage de Huffman est optimal parmi les codes qui substituent un

mot à une lettre : il minimise un ”cout”.

Application : le fax, la compressions de certaines images

Remarque : Il existe des méthodes de compression sans perte de

donnée beaucoup plus efficace que l’algorithme de Huff-
man.
Outline

1 Introduction

2 Notion de codes

3 Codage de Huffman (1952)

Notion de cout associé à un arbre
Codage d’un texte
Décodage d’un texte

4 Implantation et représentation des données

5 Algorithme d’Huffman adaptatif

Rappel

Rappel :
Si une lettre a est une lettre d’un texte à compresser apparaissant nb(a)
fois et est associé à un mot de longueur l(a), alors la longueur du texte
compressé vaut

L(compressé) = nb(a) · l(a) .

X

a∈texte

Implémentons cette formule sur un arbre !

Arbre pondéré et cout

Etant donné un arbre A :

on se donne une fonction de poids p définies sur les feuilles de A et à

valeurs positives ;

le poids d’un nœud interne est la somme des poids de ses enfants ;

le coût d’une feuille est le produit de son poids par son niveau ;

le coût d’un arbre est la somme des coûts de ses feuilles :

Cout(A) = poids(f ) · niveau(f )

X

f feuille de A
Arbre pondéré et cout

Etant donné un arbre A :

on se donne une fonction de poids p définies sur les feuilles de A et à

valeurs positives ;
p(f ) = nombre d’occurrence de l’étiquette de la feuille dans le texte
à compresser)
le poids d’un nœud interne est la somme des poids de ses enfants ;

le coût d’une feuille est le produit de son poids par son niveau ;
niveau = longueur du mot codant l’étiquette de la feuille
le coût d’un arbre est la somme des coûts de ses feuilles :

Cout(A) = poids(f ) · niveau(f )

X

f feuille de A

Cout(A) ←→ L(compréssé)
Recherche de minimisation du cout
Pour une fonction de poids donné, il existe des arbres de coût minimum.
Ces arbres sont localement complets (tous les nœuds ont 0 ou 2 enfants).
Considérons la fonction de poids Considérons l’arbre A suivant :
suivante :
p(a) 350

 =
p(b) 330

=


a

p(c) 20

=

 p(d) = 160
p(e) 90 b

=



p(f ) 50

=


c f

Alors :
Cout(A) = p(a) + 2p(b) + 3p(d) + 4p(e) + 5 p(c) + p(f ) = 2200
 
Recherche de minimisation du cout
Pour une fonction de poids donné, il existe des arbres de coût minimum.
Ces arbres sont localement complets (tous les nœuds ont 0 ou 2 enfants).

Considérons la fonction de poids Considérons l’arbre A suivant :

suivante :

 p(a) 350

 =
p(b) = 330



p(c) 20

=

 p(d) = 160
p(e) 90

=



p(f ) 50 e f

=


a b c d

Alors :

Cout(A) = 3 p(a) + p(b) + p(c) + p(d) + 2 p(e) + p(f ) = 2860

   
Outline

1 Introduction

2 Notion de codes

3 Codage de Huffman (1952)

Notion de cout associé à un arbre
Codage d’un texte
Décodage d’un texte

4 Implantation et représentation des données

5 Algorithme d’Huffman adaptatif

Principe du codage de Huffman

Le code de Huffman est un code préfixe de coût minimal construit grâce

à un arbre pondéré de coût minimum : les feuilles représentent les lettres,
leur poids est le nombre d’occurence dans le texte.

Une première passe du texte détermine le nombre d’occurence de

chaque lettre.
On construit un arbre pondéré de coût minimum.
On construit le codage de chaque lettre : l’étiquette de la branche
qui mène de la racine à la feuille contenant la lettre.
Une deuxième passe construit le texte compréssé en remplaçant
chaque lettre par son codage.
Principe du codage de Huffman

Le code de Huffman est un code préfixe de coût minimal construit grâce

à un arbre pondéré de coût minimum : les feuilles représentent les lettres,
leur poids est le nombre d’occurence dans le texte.

Une première passe du texte détermine le nombre d’occurence de

chaque lettre.
On construit un arbre pondéré de coût minimum.
En utilisant une file de priorité !
On construit le codage de chaque lettre : l’étiquette de la branche
qui mène de la racine à la feuille contenant la lettre.
Une deuxième passe construit le texte compréssé en remplaçant
chaque lettre par son codage.
Rappel : type abstrait de données File de priorité

Définition :
Soit C un ensemble quelconque et E un ensemble ordonné.
Une file de priorité est un ensemble de couples (cle,priorite) ∈ C × E ,
sur lequel on souhaite pouvoir réaliser les opérations suivantes :
• maximum : File −→ C × E ou minimum : File −→ C × E
• inserer : File×C × E −→ File ;
• supprimer : File −→ File.

Les opérations inserer et supprimer se font en O(log2 n), où n désigne

le nombre d’éléments dans la file de priorité.
Rappel : type abstrait de données File de priorité

Définition :
Soit C un ensemble quelconque et E un ensemble ordonné.
Une file de priorité est un ensemble de couples (cle,priorite) ∈ C × E ,
sur lequel on souhaite pouvoir réaliser les opérations suivantes :
• maximum : File −→ C × E ou minimum : File −→ C × E
• inserer : File×C × E −→ File ;
• supprimer : File −→ File.

Les opérations inserer et supprimer se font en O(log2 n), où n désigne

le nombre d’éléments dans la file de priorité.
Construction de l’arbre pondéré de cout minimum
A ce stade, on suppose connu :
1 le nombre n de lettres contenu dans le texte à compresser ;

2 le nombre d’occurence nb_occ(l) de chaque lettre l du texte.

Algorithme de création de l’arbre de Huffman :

Créer une file F de priorité vide.

Pour chaque lettre l du texte :
a = alloueNoeud(l)
inserer(F, a, nb_occ(l))
Pour i allant de 1 à n−1 :
b = alloueNoeud()
cle_1, priorite_1 = minimum(F)
cle_2, priorite_2 = minimum(F)
b->fils_gauche = cle_1
b->fils_droit = cle_2
inserer(F, b, priorite_1 + priorite_2)
Exemple

Texte à compresser : ”xabracadabrara”

x
1

c
1

d 1
Priorité
importante
b
2

r
3

a
6
Exemple

Texte à compresser : ”xabracadabrara”

d 1

b
2

Priorité
importante
x c
1 1

r
3

a
6
Exemple

Texte à compresser : ”xabracadabrara”

x c
1 1

r
3
Priorité
importante

d b
1 2

a
6
Exemple

Texte à compresser : ”xabracadabrara”

d b
1 2

Priorité
importante
r
3

x c
1 1

a
6
Exemple

Texte à compresser : ”xabracadabrara”

a
6

Priorité
importante
d b r
1 2 3

x c
1 1
Exemple

Texte à compresser : ”xabracadabrara”

a
6

Priorité
importante
d b r
1 2 3

x c
1 1
Exemple
Texte à compresser : ”xabracadabrara”

a
6

Priorité
importante
d b r
1 2 3

x c
1 1

Codage :
a: 0 d: 100
b : 101 r: 111
c : 1101 x: 1100
Exemple
Texte à compresser : ”xabracadabrara”

a
6

Priorité
importante
d b r
1 2 3

x c
1 1

Codage :
a: 0 d: 100 Compressé :
b : 101 r: 111 1100|0|101|111|0|1101|0|100|0|101|
c : 1101 x: 1100 32 bits contre 14 · 8 = 112 bits
Exercice

Imaginons un texte de 1000 caractères dont le nombre d’occurences des

lettres est donné par :

Lettre a b c d e f
Nombre d’occurence 350 330 20 160 90 50

Donner un arbre pondéré de cout minimal de Huffman pour ce texte et

comparer avec le codage 2 du transparent 5.
Outline

1 Introduction

2 Notion de codes

3 Codage de Huffman (1952)

Notion de cout associé à un arbre
Codage d’un texte
Décodage d’un texte

4 Implantation et représentation des données

5 Algorithme d’Huffman adaptatif

Principe du décodage

Pour décoder un message codé par l’algorithme de Huffman, il faut avoir

accès
au codage de chaque lettre
ou
à l’arbre de Huffman

Puisque le code de Huffman est un code préfixe, on peut déconcaténer le

messsage de manière unique !
Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y
Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé :
Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé :
Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : i
Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : i
Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : i
Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : i
Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : il
Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : il
Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : il
Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : ilo

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : ilo

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : ilo

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : ilov

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : ilov

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : ilov

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : ilove

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : ilove

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : ilove

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : ilove

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0

sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : ilovey

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0
sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : ilovey

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0
sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : ilovey

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0
sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : iloveyo

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0
sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : iloveyo

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0
sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : iloveyo

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0
sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : iloveyo

Exemple

Décodons le texte suivant :

1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0
sachant qu’il a été codé en utilisant l’arbre de Huffman suivant :

a o e v h i

l t u y

Texte décompréssé : iloveyou

Outline

1 Introduction

2 Notion de codes

3 Codage de Huffman (1952)

Notion de cout associé à un arbre
Codage d’un texte
Décodage d’un texte

4 Implantation et représentation des données

5 Algorithme d’Huffman adaptatif

Structure utilisée pour stocker l’arbre de Huffman

Fait : Si le nombre de feuilles est N, l’arbre de Huffman comprend

2N − 1 nœuds.

On représente donc l’arbre de Huffman par un tableau de 2N − 1 cases :

les nœuds sont chainés par indice.

typedef struct {
char lettre;
int occurence;
int gauche,droit;
} NoeudHuffman;
Construction de l’arbre

Les premier nœuds de l’arbre contiennent les lettres et sont triées

par ordre croissant

En remarquant que les nœuds internes sont crées par poids

croissant, le tableau est utilisé comme deux files de priorité :
la première contient la suite triée des feuilles ;
la seconde contient celle des nœuds internes.

Les deux nœuds de poids minimum sont donc parmi les deux
premières feuilles ou les deux premiers nœuds internes non traitées.
Exemple

Texte à compresser : ”xabracadabrara”

x lettre Poids G D
1
0 x 1 - -
c 1 c 1 - -
1 2 d 1 - -
d 3 b 2 - -
1
Priorité 4 r 3 - -
importante 5 a 6 - -
b
2
6

r 7
3
8

a 9
6 10
Exemple

Texte à compresser : ”xabracadabrara”

d lettre Poids G D
1
0 x 1 - -
b 1 c 1 - -
2 2 d 1 - -
3 b 2 - -
Priorité 4 r 3 - -
importante a 6 - -
x c 5
1 1 6 - 2 0 1
r 7
3
8

a 9
6 10
Exemple

Texte à compresser : ”xabracadabrara”

lettre Poids G D
0 x 1 - -
x c 1 c 1 - -
1 1 2 d 1 - -
r 3 b 2 - -
3
Priorité 4 r 3 - -
importante 5 a 6 - -
6 - 2 0 1
d b 7 - 3 2 3
1 2 8

a 9
6 10
Exemple

Texte à compresser : ”xabracadabrara”

lettre Poids G D
0 x 1 - -
d b 1 c 1 - -
1 2 2 d 1 - -
3 b 2 - -
Priorité 4 r 3 - -
importante a 6 - -
r 5
3 6 - 2 0 1
x c 7 - 3 2 3
1 1 8 - 5 6 4
a 9
6 10
Exemple

Texte à compresser : ”xabracadabrara”

a lettre Poids G D
6
0 x 1 - -
1 c 1 - -
2 d 1 - -
3 b 2 - -
Priorité 4 r 3 - -
importante a 6 - -
d b r 5
1 2 3 6 - 2 0 1
x c 7 - 3 2 3
1 1 8 - 5 6 4
9 - 8 7 8
10
Exemple

Texte à compresser : ”xabracadabrara”

lettre Poids G D
0 x 1 - -
a 1 c 1 - -
6
2 d 1 - -
3 b 2 - -
Priorité 4 r 3 - -
importante a 6 - -
d b r 5

1 2 3 6 - 2 0 1
x c 7 - 3 2 3
1 1 8 - 5 6 4
9 - 8 7 8
10 - 14 5 9
Deux difficultés :

Deux problèmes se posent pour permettre le décodage :

il faut transmettre le code utilisé ;

si la longueur du compressé n’est pas multiple de 8, il ne faut pas

prendre en compte tous les bits du dernier octet.
Transmission du code

Un parcours préfixe de l’arbre de Huffman permet d’associer les

mots du code et les lettres du texte :
un bit 0 indique un nœud interne ;
un bit 1 indique une feuille, que l’on fait suivre du code ASCII de la
lettre associée.

Structure pour stocker un mot du code :

typedef struct {
char *code;
int nombreBit;
} Codage;

Structure pour stocker intégralement le code :

#define NB_LETTRES 256
...
Codage Code[NB_LETTRES]
Exemple de transmission de code

Un arbre de Huffman :

a Transmission du code associée :

6

01[a]001[d]1[b]001[x]1[c]1[r]

[x] désigne le code ascii de la lettre x.

d b r
1 2 3

x c
1 1
Padding
Warning : Il peut y avoir des bits non valides dans dernier octet du fichier
compressé.
La longueur du compressé est égale au coût de l’arbre.
Le codage de l’arbre utilise un bit par nœud.
Le fichier compressé débute par 3 bits indiquant le nombre de bits
invalides du dernier octet (de 0 à 7).

Exemple : xabracadabrara

Codage : Calcul du padding :

a: 0 compressé : 32 bits ≡ 0[8]
a b : 101 nombre de nœuds : 11 ≡ 3[8]
6
c : 1101 padding = 8 − 0 − 3 − 3 = 2
d : 100
r : 111 Entête du fichier :
r x : 1100 010 - transmission du code
d b
1 2 3
Fichier compressé :
x c 01001[a]001[d]1[b]001[x]1[c]1[r]
1 1 1100010111101101010001011110111000
Décompression

1 On lit le padding ;

2 On reconstruit l’arbre à partir de son parcours préfixe ;

3 On décode le texte initial :

on suit le chemin à partir de la racine ;
Lorsqu’on arrive à une feuille, on décode la lettre et on repart de la
racine.

4 On oublie les bits de fin associé au padding.

Exercice : Sensibilité de l’algorithme d’Huffman aux erreurs

On vient d’obtenir un code de Huffman en deux passes d’un texte

initial :
1110001[A]1[O]01[E]1[V]001[H]01[L]1[T]01[I]01
[U]1[Y]1101010001011010111100111100111011
Celui-ci contient le message : iloveyou

On transmis ce fichier, mais une erreur a inversé le sixième bit du

texte compressé :
1110001[A]1[O]01[E]1[V]001[H]01[L]1[T]01[I]01
[U]1[Y]1101000001011010111100111100111011
Quel message contient désormais ce fichier ?

Pour les transmissions, on utilise des codes correcteurs d’erreurs.

Outline

1 Introduction

2 Notion de codes

3 Codage de Huffman (1952)

Notion de cout associé à un arbre
Codage d’un texte
Décodage d’un texte

4 Implantation et représentation des données

5 Algorithme d’Huffman adaptatif

Inconvénients de l’algorithme de Huffman

lire tout le texte avant de commencer la compression;

transmettre le code utilisé.

Solutions :
• utiliser un code fixe;
• version adaptative de Huffman qui modifie le code au fur et à mesure
de son utilisation.

Compression : à la lecture d’une lettre du texte,

on transmet son code actuel;
on incrémente sa fréquence et on met à jour l’arbre.

Décompression: le décompresseur mime le compresseur pour disposer des

mêmes données après avoir traité la même partie du texte.
Idée générale

Dans un arbre de Huffman, on peut ranger les nœuds dans une liste
• croissante pour les poids
• dans laquelle deux enfants du même nœud sont consécutifs.

13

a 6 7

r 3 4

2
b 2

c 1 d 1
Mise à jour dans l’algorithme d’Huffman adaptatif

A la lecture d’une lettre a du texte :

si la lettre a déjà été rencontrée :

on échange la feuille d’étiquette a avec le nœud de même poids le
plus loin dans la liste, puis on incrémente son poids. On
recommence avec le père, jusqu’à la mise à jour de la racine.

si la lettre n’a jamais été rencontrée :

on conserve dans l’arbre une feuille de poids nul qui représente
toutes les nouvelles lettres. On code la lettre a par le code de la
feuille de poids nul suivi du code ASCII de a. La feuille de poids nul
est remplacée par un nœud ayant pour enfants la feuille de poids nul
et une nouvelle feuille de poids 1 d’étiquette a. On poursuit comme
dans le cas précédent en incrémentant le poids du nœud parent de 1.
Exemple 1/2

T=abracadabrara

lu 2 3
a 1
b 1
0 a1 r a1 2
émis 0[b] 00[r]
0 a1
[a] 0 b1 1 b1
01100001
0 r1
4 5 6

a a2 2 c 3 a 3
a2 a3
0 100[c] 0
1 b1 b1 2 b1 2
0 r1
1 r1 1 r1

0 c1 0 c1
Exemple 2/2

T=abracadabrara

7 8 9
a3 4 4 5
a4 a4
d 2 a b 3
2 2 2 2
1100[d] 0 110
1 c1 b1 r1 1 c1 b1 r1 1 c1 r1 b2

0 d1 0 d1 0 d1

a r 12 a 13
r 10 11 0
0 110
110 a5 7
a4 6 a5 6 a6 7
4
4 2 4 r3 r3 4
2
2 b2 2
1 c1 r2 b2 1 c1 r2 b2 b2
1 c1 1
0 d1 0 d1 c1
0 d1
0 d1