Codage de Huffman

Le codage de Huffman est une méthode de compression statistique de données qui permet de réduire la longueur du codage d'un alphabet. Le code de Huffman (1952) est un code de longueur variable optimal, c'est-à-dire tel que la longueur moyenne d'un texte codé soit minimale. On observe ainsi des réductions de taille de l'ordre de 20 à 90%.

Le principe

Le principe de l'algorithme de Huffman consiste à recoder les octets rencontrés dans un ensemble de données source avec des valeurs de longueur binaire variable.
L'unité de traitement est ramenée au bit. Huffman propose de recoder les données qui ont une occurrence très faible sur une longueur binaire supérieure à la moyenne, et recoder les données très fréquentes sur une longueur binaire très courte.
Ainsi, pour les données rares, nous perdons quelques bits regagnés pour les données répétitives. Par exemple, dans un fichier ASCII le "w" apparaissant 10 fois aura un code très long: 0101000001000. Ici la perte est de 40 bits (10 x 4 bits), car sans compression, il serait codé sur 8 bits au lieu de 12. Par contre, le caractère le plus fréquent comme le "e" avec 200 apparitions sera codé par 1. Le gain sera de 1400 bits (7 x 200 bits). On comprend l'intérêt d'une telle méthode.
De plus, le codage de Huffman a une propriété de préfixe: une séquence binaire ne peut jamais être à la fois représentative d'un élément codé et constituer le début du code d'un autre élément.
Si un caractère est représenté par la combinaison binaire 100 alors la combinaison 10001 ne peut être le code d'aucune autre information. Dans ce cas, l'algorithme de décodage interpréterait les 5 bits comme une succession du caractère codé 100 puis du caractère codé 01. Cette caractéristique du codage de Huffman permet une codification à l'aide d'une structure d'arbre binaire.

Méthode

L'algorithme opère sur une forêt. Une forêt est ici un ensemble d'arbres étiquetés complets: tout noeud interne (c'est-à-dire qui n'est pas une feuille) a deux fils non-vides.
La forêt initiale est formée d'un arbre à un noeud pour chaque lettre du langage-source, dont l'étiquette est la probabilité de cette lettre. La forêt finale est formée d'un unique arbre, qui est l'arbre de décodage du code.
L'algorithme est de type glouton: il choisit à chaque étape les deux arbres d'étiquettes minimales, soit x et y, et les remplace par l'arbre formé de x et y et ayant comme étiquette la somme de l'étiquette de x et de l'étiquette de y.
La figure ci-contre représente les étapes de la construction d'un code de Huffman pour l'alphabet source {A, B, C, D, E, F}, avec les probabilités P(A)=0.10, P(B)=0.10, P(C)=0.25, P(D)=0.15, P(E)=0.35 et P(F)=0.05.
Le code d'une lettre est alors déterminé en suivant le chemin depuis la racine de l'arbre jusqu'à la feuille associée à cette lettre en concaténant successivement un 0 ou un 1 selon que la branche suivie est à gauche ou à droite. Ainsi, sur la figure ci-contre, A=0111, B=010, C=10, D=00, E=11 et F=0110.

Par exemple le mot FADE serait codé 011001110011. Pour décoder, on lit simplement la chaîne de bits de gauche à droite. Le seul "découpage" possible, grâce à la propriété du préfixe, est 0110-0111-00-11.

Conclusion

Ce principe de compression est aussi utilisé dans le codage d'image TIFF (Tagged Image Format File) spécifié par Microsoft Corporation et Aldus Corporation.
Par ailleurs, le codage d'image est fait en retranscrivant exactement le contenu d'un écran (image), en utilisant les méthodes traditionnelles de compression. Il existe des méthodes qui ne conservent pas exactement le contenu d'une image (méthodes non conservatives) mais dont la représentation visuelle reste correcte. Entre autres, il y a la méthode JPEG (Join Photographic Experts Group) qui utilise la compression de type Huffman pour coder les informations d'une image.
Malgré son ancienneté, cette méthode est toujours remise au goût du jour, et offre des performances appréciables. En effet, beaucoup de recherches en algorithmique ont permis d'améliorer les fonctionnalités de la méthode Huffman de base, par exemple les arbres binaires, les arbres équilibrés, etc.

Exercices

Exercice 1

Construisez un codage de Huffman du message "ceciestuncodagedehuffman" (on a supprimé les espaces et la ponctuation pour simplifier la construction). Il y a plusieurs codages de Huffman possibles.
Vérifiez la propriété du préfixe.

Exercice 2 (pour les plus courageux)

Utilisez le tableau ci-dessous pour déterminer le codage de Huffman de la langue française.

Fréquences d'apparition des lettres en français
Lettre Fréquence Lettre Fréquence
A 8.40 % N 7.13 %
B 1.06 % O 5.26 %
C 3.03 % P 3.01 %
D 4.18 % Q 0.99 %
E 17.26 % R 6.55 %
F 1.12 % S 8.08 %
G 1.27 % T 7.07 %
H 0.92 % U 5.74 %
I 7.34 % V 1.32 %
J 0.31 % W 0.04 %
K 0.05 % X 0.45 %
L 6.01 % Y 0.30 %
M 2.96 % Z 0.12 %

Les corrigés sont disponibles, mais seulement pour les visiteurs autorisés!
Mot de passe :

Références

Didier Müller, 13.2.03