Probabilités et statistiquesNotion · Glossaire
codage de Huffman
Le codage de Huffman est un algorithme de compression de données sans perte, inventé en 1952 par l'informaticien américain David Albert Huffman (1925-1999). Il repose sur l'attribution de codes binaires à longueur variable aux symboles d'une source (caractères, pixels, échantillons sonores) : les symboles les plus fréquents reçoivent les codes les plus courts, et inversement. Ce principe minimise la longueur moyenne des mots de code et produit ainsi un encodage optimal au sens de la théorie de l'information. La construction du code s'effectue par la construction d'un arbre binaire — l'arbre de Huffman — obtenu par fusions successives des deux nœuds de plus faible probabilité. Le codage dépend donc de la distribution statistique de la source, et donc de la langue ou du type de données traitées. Le gain obtenu dépend aussi du codage de référence et du coût des métadonnées nécessaires au décodage. La décompression est sans perte : le texte original est intégralement restitué. Il existe plusieurs variantes de l'algorithme, notamment le codage de Huffman adaptatif, qui ne nécessite pas de connaître la distribution a priori.
Sommaire
Ce que vous allez apprendre
- Relier la fréquence d’un symbole à la longueur de son mot binaire.
- Construire un arbre de Huffman par fusions successives des poids minimaux.
- Encoder puis décoder la chaîne AAAAABBCCD et contrôler sa longueur de 18 bits.
- Distinguer l’optimalité des codes préfixes d’une optimalité absolue de compression.
En clair
Imaginez un message où la lettre A apparaît cinq fois, tandis que D n’apparaît qu’une fois. Employer le même nombre de bits pour chaque lettre gaspille de la place. Le codage de Huffman attribue donc un code très court à A et des codes plus longs aux lettres rares.
Ces codes sont organisés comme les chemins d’un arbre. Aucun code n’étant le début d’un autre, le décodeur peut lire les bits sans séparateur et restituer exactement le message.
Définition
Le codage de Huffman est une méthode de compression sans perte conçue par David Albert Huffman en 1952. Elle s’applique aux symboles d’une source, par exemple des caractères, des valeurs de pixel ou des échantillons sonores. À chaque symbole, elle associe un mot formé de 0 et de 1. La longueur varie avec la fréquence : un symbole fréquent reçoit en général un mot plus court qu’un symbole rare.
Pour construire le code, on crée une feuille par symbole, pondérée par sa fréquence ou sa probabilité. On fusionne les deux nœuds de plus faible poids, puis on répète l’opération jusqu’à obtenir une seule racine. En étiquetant chaque branche par 0 ou 1, le chemin de la racine à une feuille fournit le mot du symbole. Les mots forment un code préfixe : aucun mot complet n’est le début d’un autre. Cette propriété rend le décodage non ambigu.
Pour une distribution connue et des mots binaires de longueur entière, l’algorithme minimise la longueur moyenne parmi les codes préfixes symbole par symbole. Le gain obtenu dépend donc de la langue ou du type de données, du codage de référence et du coût des métadonnées nécessaires au décodage. La variante adaptative met à jour l’arbre au fil des symboles et n’exige pas la distribution à l’avance.
Un exemple, pas à pas
On veut encoder le message AAAAABBCCD, qui contient dix caractères. Les données sont : A apparaît 5 fois, B 2 fois, C 2 fois et D 1 fois. Un code fixe pour quatre symboles utiliserait 2 bits par caractère, soit 20 bits.
1. On fusionne D, de poids 1, avec B, de poids 2 : le nouveau nœud pèse 3. En cas d’égalité entre B et C, choisir C à la place donnerait un autre code de même longueur totale.
2. On fusionne C, de poids 2, avec le nœud de poids 3 : leur parent pèse 5. On fusionne enfin ce parent avec A, de poids 5, pour atteindre la racine de poids 10.
3. Avec 0 sur les branches gauches et 1 sur les branches droites, on obtient A = 0, C = 10, D = 110 et B = 111. Le message devient 000001111111010110.
La longueur totale est la somme des fréquences multipliées par les longueurs des mots :
Le contrôle consiste à repartir de la racine après chaque feuille : les 18 bits redonnent successivement A, A, A, A, A, B, B, C, C et D. Le gain sur ce message est de 2 bits par rapport aux 20 bits du code fixe, hors stockage de l’arbre.
En pratique
Pour compresser un fichier, on compte d’abord les symboles, on construit l’arbre, puis on remplace chacun d’eux par son mot binaire. Le décodeur doit aussi connaître l’arbre ou une description équivalente. Sur un très petit fichier, ce surcoût peut annuler le gain.
Quand les fréquences sont connues et stables, un arbre fixe convient. Si elles changent au cours du flux ou ne sont pas disponibles au départ, le Huffman adaptatif met à jour le code pendant la lecture.
La méthode est pertinente quand certains symboles sont nettement plus fréquents que d’autres. Si leurs fréquences sont presque égales, les mots ont des longueurs voisines et le gain devient faible ; un code fixe peut alors être aussi compact une fois l’arbre pris en compte.
À ne pas confondre
Compression sans perte et compression avec perte. Huffman restitue chaque symbole original. Une méthode avec perte autorise au contraire une modification mesurable des données ; si le message décodé diffère, il ne s’agit pas d’un simple codage de Huffman.
Code à longueur variable et code de Huffman. Toute attribution de mots de tailles différentes n’est pas un code de Huffman. Il faut retrouver les fusions successives des deux poids minimaux et la propriété de préfixe ; sinon, la lecture peut être ambiguë ou non optimale.
Arbre de décision et arbre de Huffman. Tous deux sont binaires, mais leurs feuilles n’ont pas le même rôle. Dans Huffman, elles représentent les symboles et leurs chemins forment des mots binaires ; elles ne portent pas une décision de classement.
Limites et pièges
Fréquences égales. Plusieurs choix de fusion sont possibles. On peut obtenir des mots différents, mais de même longueur moyenne ; il faut conserver exactement le même arbre au codage et au décodage.
Un seul symbole distinct. Un arbre réduit à une feuille ne fournit aucun chemin. En pratique, on lui attribue conventionnellement un mot d’un bit et on transmet aussi le nombre de répétitions ; un flux vide ne permettrait pas de le retrouver.
Petit message. Les 2 bits gagnés sur AAAAABBCCD ne comptent pas la description de l’arbre. Si celle-ci dépasse 2 bits, le fichier complet n’est pas plus petit ; il faut comparer la taille totale, métadonnées comprises.
Optimalité à bien lire. Huffman est optimal parmi les codes préfixes binaires qui attribuent un nombre entier de bits à chaque symbole pris isolément, pour la distribution fournie. Cette garantie n’affirme pas qu’aucune autre méthode de compression ne puisse faire mieux.
Pour aller plus loin
Entropie. Reliez les fréquences des symboles à la quantité moyenne d’information et à la limite théorique de compression.
Théorie de l'information. Replacez les codes préfixes, l’entropie et la compression sans perte dans leur cadre mathématique commun.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres