📨 Le mystère du fichier qui rétrécit
Tu glisses un document texte dans un dossier ZIP. Il passait à 100 ko, le voilà à 40 ko. Tu le ré-ouvres : pas une lettre n'a disparu. Comment est-ce possible ? D'où vient cette place gagnée, si rien n'est perdu ?
La réponse tient dans une idée d'une simplicité désarmante. Dans un ordinateur, chaque lettre occupe normalement 8 bits (un octet), qu'elle soit fréquente ou rare. Le E, omniprésent en français, et le W, presque introuvable, coûtent exactement pareil. Quel gâchis ! L'idée géniale : donner des codes courts aux lettres fréquentes et des codes longs aux lettres rares. En moyenne, le message raccourcit. C'est tout le secret du codage de Huffman.
🌳 Construis l'arbre de Huffman
Choisis un mot, puis fusionne pas à pas les deux nœuds de plus faible fréquence. L'arbre final donne à chaque lettre son code optimal.
Choisis un mot et clique sur « Pas » pour fusionner les deux plus petites fréquences.
ASCII (8 bits)
—
Huffman
—
Compression
—
Longueur moyenne : — bits/lettre
🎓 Un devoir d'étudiant qui a changé le monde
1951, au MIT. Le professeur Robert Fano propose à ses étudiants un choix : passer l'examen final, ou rendre un devoir résolvant un problème ouvert — trouver le code binaire le plus court possible pour représenter un ensemble de symboles. Personne, pas même Fano ni son célèbre collègue Claude Shannon, ne savait s'il existait une solution vraiment optimale.
Un étudiant de 25 ans, David A. Huffman, choisit le devoir. Il s'acharne des semaines, sans succès, et s'apprête à abandonner pour réviser l'examen. Et là, en jetant ses notes, l'illumination : au lieu de construire l'arbre du haut vers le bas (comme tout le monde essayait), il faut le construire du bas vers le haut, en partant des symboles les plus rares. Sa méthode, publiée en 1952, était non seulement simple, mais prouvée optimale. Il venait, sans le savoir, de battre son propre professeur.
🔑 La règle d'or : un code sans préfixe
Si le E vaut 0 et le T vaut 01, on
a un problème : en lisant 01, l'ordinateur ne sait pas si c'est « T »
ou « E suivi de quelque chose ». Pour décoder sans la moindre ambiguïté,
Huffman impose une condition :
Code préfixe (« sans préfixe »). Aucun code de lettre n'est le
début d'un autre code. Si A = 0, alors
aucune autre lettre ne peut commencer par 0. Résultat : on lit le
flot de bits de gauche à droite et, dès qu'on reconnaît un code, c'est forcément celui-là.
Pas besoin de séparateur, pas d'ambiguïté.
C'est exactement ce que garantit un arbre binaire : chaque lettre est une
feuille. Pour atteindre une feuille, on descend en notant 0 à chaque virage
à gauche et 1 à droite. Comme une feuille n'est jamais sur le chemin d'une autre
feuille, son code ne peut jamais être le préfixe d'un autre. La propriété est gratuite.
🛠️ L'algorithme glouton, en quatre temps
La méthode de Huffman est un algorithme glouton : à chaque étape, il fait le choix qui paraît le meilleur sur le moment — fusionner les deux symboles les plus rares — sans jamais revenir en arrière. Et ici, miracle, ce choix local mène au résultat globalement optimal.
- Compter. On relève la fréquence de chaque lettre du texte.
- Une feuille par lettre. Chaque lettre devient un nœud isolé, étiqueté par sa fréquence. On les place dans une file de priorité (les plus petites fréquences d'abord).
- Fusionner les deux plus petits. On retire les deux nœuds de plus faible fréquence et on crée un nœud parent dont la fréquence est leur somme. On le replace dans la file.
- Recommencer jusqu'à ce qu'il ne reste qu'un seul nœud : la racine de l'arbre. Les codes se lisent alors de la racine vers chaque feuille (gauche = 0, droite = 1).
Pourquoi commencer par les plus rares ? Parce que fusionner deux nœuds les enfonce d'un cran plus profond dans l'arbre — donc leur donne un code plus long. On veut allonger en priorité les lettres rares, et garder les fréquentes près de la racine, là où les codes sont courts. Joue avec la visualisation ci-dessus pour le voir naître étape par étape.
🏆 Pourquoi c'est vraiment le meilleur
L'optimalité de Huffman n'est pas une impression : elle se démontre. L'argument repose sur une observation imparable : dans un code optimal, les deux symboles les moins fréquents doivent forcément être les plus profonds de l'arbre, et être frères (au même nœud parent). Sinon, on pourrait les échanger avec des feuilles plus profondes et raccourcir le total — contradiction.
Or c'est exactement ce que fait Huffman dès sa première fusion. En répétant l'argument sur l'arbre réduit (par récurrence), on prouve qu'aucun code préfixe ne peut faire mieux. Parmi tous les codes possibles, celui de Huffman atteint la longueur moyenne minimale.
Longueur moyenne. Si la lettre i a une fréquence pi et un code de longueur ℓi, le coût moyen par lettre est la somme des pi × ℓi. Huffman rend cette somme aussi petite que possible — c'est la définition même de l'optimalité.
📏 La limite ultime : l'entropie de Shannon
Peut-on compresser à l'infini ? Non. Claude Shannon a démontré en 1948 qu'il existe un plancher absolu, l'entropie de la source : le nombre moyen de bits vraiment nécessaires pour coder un symbole. Une lettre de probabilité p apporte log2(1/p) bits d'information : les événements rares sont « surprenants » donc coûteux, les fréquents presque gratuits.
Entropie ≤ Huffman < Entropie + 1
Le codage de Huffman s'approche du plancher de Shannon à moins d'un bit près par symbole. Il ne peut pas descendre sous l'entropie (ce serait perdre de l'information), et il ne s'en éloigne jamais de plus d'un bit. C'est le meilleur des deux mondes : optimal et borné par la théorie.
Sa seule petite faiblesse : chaque lettre reçoit un nombre entier de bits. Quand l'entropie idéale vaut, disons, 2,3 bits, Huffman doit arrondir. Des techniques plus modernes (codage arithmétique, codage par plage / range coding) effacent ce dernier petit gaspillage en codant des fractions de bit — mais elles reposent toutes sur la même intuition que Huffman a fondée.
🌍 Huffman est partout (vraiment partout)
Soixante-dix ans plus tard, le code de Huffman tourne des milliards de fois par seconde dans le monde, presque toujours invisible :
- ZIP, gzip, PNG : l'algorithme DEFLATE qui les anime combine un dictionnaire (LZ77) avec un codage de Huffman final.
- JPEG : après avoir transformé l'image, ses coefficients sont compressés par Huffman.
- MP3, AAC : le son numérique, une fois analysé en fréquences, passe lui aussi par des tables de Huffman.
- Fax, modems, protocoles réseau : partout où l'on transmet des données, on cherche à les raccourcir d'abord.
À chaque photo que tu envoies, chaque musique que tu écoutes en streaming, chaque page web qui se charge, l'idée d'un étudiant de 25 ans travaille discrètement pour toi.
🎒 Le lien avec ton programme
Le codage de Huffman est un point de rencontre magnifique entre plusieurs notions que tu croises en cours d'informatique et de maths :
- Arbres binaires : feuilles, racine, profondeur, parcours — Huffman en est l'application la plus élégante.
- Algorithmes gloutons : un cas d'école où le choix local optimal garantit l'optimum global (rare, et démontrable).
- Files de priorité (tas) : la structure qui permet de retirer efficacement les deux plus petits éléments à chaque étape.
- Logarithmes & probabilités : l'entropie, log2, l'espérance d'une longueur de code — les maths derrière la compression.
- Complexité : construire l'arbre coûte O(n log n) grâce à la file de priorité.