Codage de Huffman appliqué au texte et à
l’image
Le codage de Huffman est un algorithme de compression sans perte qui associe à chaque symbole
(caractère ou niveau de gris) un code binaire de longueur variable, les symboles les plus fréquents
ayant les codes les plus courts. On représente les symboles sous forme de feuilles d’un arbre binaire
pondéré par leur fréquence. À chaque étape on fusionne les deux nœuds de plus faible poids pour créer
un nœud parent dont le poids est la somme des deux fréquences. Les codes binaires sont obtenus en
parcourant l’arbre de la racine vers les feuilles : on assigne par convention le bit 0 à chaque branche
gauche et le bit 1 à chaque branche droite, puis on lit les bits le long du chemin jusqu’à la feuille. Lors
de la décompression, on lit le flux binaire bit à bit en descendant l’arbre de Huffman ; chaque fois
qu’une feuille est atteinte, on récupère le symbole correspondant.
1. Codage Huffman du texte
On souhaite compresser la phrase : « je suis parmi les sept merveilles des temps modernes ».
1.1 Calcul des fréquences
On compte les occurrences de chaque caractère (lettre et espace) :
Caractère Fréquence
j 1
e 10
(espace) 8
s 8
m 4
i 3
p 3
r 3
l 3
t 2
d 2
a 1
v 1
o 1
n 1
u 1
Ces fréquences seront les poids des feuilles de l’arbre de Huffman.
1.2 Construction de l’arbre de Huffman
On crée d’abord un nœud feuille pour chaque caractère avec la fréquence correspondante. Ensuite, on
répète l’opération suivante : sélectionner les deux nœuds de plus faibles poids et les fusionner en un
nouveau nœud dont le poids est la somme des deux, ce nouveau nœud devenant le parent des deux
nœuds extraits. Voici les étapes de fusion (poids entre parenthèses) :
1. Fusionner 'j'(1) et 'u'(1) → nœud J-U (2)
2. Fusionner 'a'(1) et 'v'(1) → nœud A-V (2)
3. Fusionner 'o'(1) et 'n'(1) → nœud O-N (2)
4. Il reste les nœuds de poids 2 : {J-U, A-V, O-N, d(2), t(2)}. Fusionner d(2) et t(2) → nœud
D-T (4).
5. Fusionner J-U(2) et A-V(2) → nœud JU-AV (4).
6. Fusionner O-N(2) et D-T(4) → nœud ON-DT (6).
7. Il reste (APRES COMBINAISON) : i(3), p(3), r(3), l(3), M(4), JU-AV(4), ON-DT(6), S(8),
espace(8), E(10). Fusionner i(3) et p(3) → nœud IP (6).
8. Fusionner r(3) et l(3) → nœud RL (6).
9. Fusionner JU-AV(4) et M(4) → nœud JUAV-M (8).
10.Fusionner ON-DT(6) et IP(6) → nœud ONDT-IP (12).
11.Fusionner RL(6) et JUAV-M(8) → nœud RLJUAVM (14).
12.Fusionner s(8) et espace(8) → nœud S-ESP (16).
13.Fusionner E(10) et ONDT-IP(12) → nœud E-ONDTIP (22).
14.Fusionner RLJUAVM(14) et S-ESP(16) → nœud RLJUAVM-S (30).
15.Enfin, fusionner E-ONDTIP(22) et RLJUAVM-S(30) → racine (52).
L’arbre final (racine poids 52) regroupe ainsi tous les caractères.
1.3 Attribution des codes binaires
On assigne le bit 0 aux branches gauches et le bit 1 aux branches droites, depuis la racine vers les
feuilles. Par exemple, si on choisit un arbre où les feuilles sont placées comme ci-dessus, on obtient les
codes binaires suivants :
Symbole Code binaire
(espace) 111
a 100110
d 10101
e 00
Symbole Code binaire
i 0101
j 100100
l 1000
m 1011
n 101001
o 101000
p 0110
r 0111
s 110
t 0100
u 100101
v 100111
Tableau : codes Huffman attribués à chaque symbole (gauche=0, droite=1).
1.4 Exemple de codage du texte
On remplace chaque caractère du texte par son code binaire. Par exemple, les premiers mots « je suis »
donnent :
• j → 100100
• e → 00
• (espace) → 111
• s → 110
• u → 100101
• i → 0101
• s → 110
La phrase « je suis » se code donc : 100100 00 111 110 100101 0101 110. En concaténant tous les codes
pour l’ensemble du texte, on obtient un flux binaire compressé (ici environ 186 bits au lieu de
52×8=416 bits si chaque caractère était codé sur 8 bits).
1.5 Principe de décompression
Pour décompresser, on utilise l’arbre de Huffman construit ci-dessus. On lit le flux binaire compressé
bit par bit depuis la racine de l’arbre : à chaque bit 0 on descend à gauche, à chaque bit 1 on descend à
droite. À chaque fois qu’on atteint une feuille, on retrouve le caractère correspondant, qu’on émet, puis
on recommence depuis la racine avec le bit suivant. Ce processus restitue exactement le texte original.
2. Codage Huffman d’une image grayscale
Considérons une image en niveaux de gris de taille 4×4 (valeurs 0–255). Par exemple, la matrice de
pixels suivante :
0 50 50 50
50 100 100 50
200 255 200 200
200 255 100 255
2.1 Calcul de l’histogramme
On compte la fréquence de chaque intensité présente (l’histogramme) :
Intensité 0 50 100 200 255
Fréquence 1 5 3 4 3
(Par exemple, l’intensité 50 apparaît 5 fois dans l’image.) Cette distribution sert de base au codage
Huffman, de la même façon que pour un texte.
2.2 Construction de l’arbre de Huffman
On crée un nœud feuille pour chaque intensité avec le poids de la fréquence. Puis on fusionne
itérativement les deux nœuds de plus faible poids. Avec les fréquences ci-dessus, les étapes sont :
1. Fusionner 0 (1) et 100 (3) → nœud N1 (4).
2. Restent 255 (3), 200 (4), 50 (5), N1 (4). Fusionner 255 (3) et N1 (4) → nœud N2 (7).
3. Restent 200 (4), 50 (5), N2 (7). Fusionner 200 (4) et 50 (5) → nœud N3 (9).
4. Restent N2 (7) et N3 (9). Fusionner N2 (7) et N3 (9) → racine (16).
L’arbre final (poids total 16) est ainsi formé.
2.3 Attribution des codes aux intensités
On assigne encore 0 aux branches gauches et 1 aux branches droites. D’après l’arbre ci-dessus, on
obtient par exemple :
• Intensité 255 : chemin « gauche (0), gauche (0) » depuis la racine → code 00.
• Intensité 0 : chemin gauche (0), puis droite (1) → code 010.
• Intensité 100 : chemin gauche (0), puis droite (1) → code 011.
• Intensité 200 : chemin droite (1), puis gauche (0) → code 10.
• Intensité 50 : chemin droite (1), puis droite (1) → code 11.
En résumé :
Intensité Code binaire
0 010
Intensité Code binaire
50 11
100 011
200 10
255 00
2.4 Encodage de l’image
On remplace chaque pixel par son code. Par exemple, ligne par ligne :
• Ligne 1 : 0 →010, 50 →11, 50 →11, 50 →11.
• Ligne 2 : 50 →11, 100 →011, 100 →011, 50 →11.
• Ligne 3 : 200 →10, 255 →00, 200 →10, 200 →10.
• Ligne 4 : 200 →10, 255 →00, 100 →011, 255 →00.
On peut écrire par exemple :
0,50,50,50 → 010 11 11 11
50,100,100,50 → 11 011 011 11
200,255,200,200→ 10 00 10 10
200,255,100,255→ 10 00 011 00
Le flux compressé est la concaténation de ces codes. Par exemple, les deux premières lignes encodées
donnent « 01011111101101111… ».
2.5 Décompression
Pour décompresser, on reconstruit l’arbre (ou on le transmet) et on parcourt le flux binaire compressé
bit par bit comme précédemment. À chaque bit 0 on descend à gauche, à chaque bit 1 à droite dans
l’arbre. À l’atteinte d’une feuille, on émet l’intensité correspondante et on recommence au sommet de
l’arbre. Ce procédé restitue tous les pixels dans l’ordre, reconstituant exactement l’image d’origine.
Sources : principes du codage de Huffman et algorithme de construction d’arbre ; principe de
décompression par parcours de l’arbre.
