Visualiseur de codage Huffman

Saisissez un texte pour voir comment le codage de Huffman attribue des codes plus courts aux caractères fréquents.

Exemple résolu — Visualiseur de codage Huffman

Original (ASCII 8 bits)	88
Bits codés en Huffman	32
Gain	63.6%
'l' (3×)	10
'␣' (1×)	000
'w' (1×)	001
'r' (1×)	010
'd' (1×)	011

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Huffman ne peut jamais dépenser moins d’un bit 🖖

Les codes de Huffman sont optimaux, mais seulement à l’intérieur d’une règle qui leur coûte cher : chaque symbole doit recevoir un nombre entier de bits. La limite de Shannon dit qu’un symbole apparaissant 90% du temps vaut environ 0,15 bit, et une source composée à 90% d’un caractère et à 10% d’un autre ne porte que 0,469 bit d’entropie par symbole. Huffman ne sait pas écrire une fraction de bit : il attribue donc 1 et 1, dépensant plus du double de ce que vaut l’information. C’est cet écart qui explique pourquoi des données très déséquilibrées se compressent décevamment ici, et pourquoi les codeurs arithmétiques et par intervalles existent : ils encodent le message entier comme un seul nombre et peuvent dépenser des bits fractionnaires. Huffman est optimal parmi les codes à bits entiers, ce qui est plus étroit qu’optimal.

Toujours fusionner les deux plus rares 🖖

L'arbre se construit de bas en haut : on liste d'abord chaque caractère selon sa fréquence, puis on fusionne à répétition les deux éléments les moins fréquents en un petit sous-arbre traité comme un seul paquet. On recommence jusqu'à ce qu'il ne reste qu'un arbre ; on lit ensuite chaque code en descendant depuis le sommet — la gauche vaut 0, la droite vaut 1. Cette habitude « gloutonne » de toujours réunir les deux plus petits semble myope, mais produit de façon prouvée les codes les plus courts possibles.

Un devoir qui a battu le professeur 🖖

David Huffman l'a conçu en 1951, alors qu'il était étudiant en doctorat au MIT, quand le professeur Robert Fano laissa la classe choisir entre un examen final et un mémoire sur la recherche du code le plus efficace. Fano et Claude Shannon avaient déjà essayé, en construisant leurs arbres de haut en bas. Huffman faillit abandonner, puis comprit que construire de bas en haut — en fusionnant d'abord les symboles les plus rares — était optimal, surpassant la méthode de son propre professeur.

CODAGE DE HUFFMAN — QUAND AIDE-T-IL, ET À QUELLE DISTANCE DE L’OPTIMUM ?

Dans quel cas de compression êtes-vous ?

Huffman donne des codes courts aux symboles fréquents et longs aux rares, et il est prouvé qu’on ne peut faire mieux tant que chaque symbole reçoit un nombre entier de bits. Ce qu’il économise dépend entièrement de l’inégalité des fréquences. Parfaitement égales, il n’y a rien à exploiter ; très inégales, le gain est considérable — jusqu’au point où la limite n’est plus les fréquences mais le bit entier.

Fréquences déséquilibrées — exactement ce à quoi la méthode sert p_i ↑ ⇒ ℓ_i ↓

Tous les symboles aussi fréquents — rien à exploiter p_i = 1/n ⇒ ℓ = log₂n

Texte ordinaire — à un bit du plancher théorique H ≤ ℓ < H + 1

Un seul symbole — le plancher que Huffman ne peut franchir n = 1 ⇒ ℓ = 1

Fréquences déséquilibrées — exactement ce à quoi la méthode sert

Ce que vous savez: Quelques symboles dominent le texte. Ce sont eux qui reçoivent les codes les plus courts, et le total tombe bien en dessous d’un codage à longueur fixe.

Coût: p_i ↑ ⇒ ℓ_i ↓

Exemple résolu: « mississippi » : 11 caractères, 4 symboles distincts, codés en 21 bits contre 88 avec des caractères de 8 bits — une économie de 76,1 %

Ouvrir ce cas: mississippi

Fréquences déséquilibrées — exactement ce à quoi la méthode sert. Les deux symboles les plus fréquents reçoivent les codes les plus courts, et le total baisse d’autant. Quelques symboles dominent le texte. Ce sont eux qui reçoivent les codes les plus courts, et le total tombe bien en dessous d’un codage à longueur fixe. — Les deux symboles les plus fréquents reçoivent les codes les plus courts, et le total baisse d’autant.

Tous les symboles aussi fréquents — rien à exploiter

Ce que vous savez: Avec une distribution plate, il n’y a pas de symbole fréquent à récompenser. Huffman dégénère en quelque chose de très proche d’un code à longueur fixe.

Coût: p_i = 1/n ⇒ ℓ = log₂n

Exemple résolu: « abcdef » : 6 symboles distincts, chacun une fois, codés en 16 bits. Un simple code de 3 bits pour six symboles en coûterait 18.

Ouvrir ce cas: uniforme

Tous les symboles aussi fréquents — rien à exploiter. Une distribution plate donne un arbre presque uniforme, et tous les codes font à peu près la même longueur. Avec une distribution plate, il n’y a pas de symbole fréquent à récompenser. Huffman dégénère en quelque chose de très proche d’un code à longueur fixe. — Une distribution plate donne un arbre presque uniforme, et tous les codes font à peu près la même longueur.

Texte ordinaire — à un bit du plancher théorique

Ce que vous savez: Un mélange réaliste de symboles répétés et uniques. C’est le cas de tous les jours, et le résultat se pose juste au-dessus de la borne d’entropie.

Coût: H ≤ ℓ < H + 1

Exemple résolu: « hello world » : 11 caractères sur 8 symboles distincts, codés en 32 bits contre 88 — 63,6 % économisés, le plancher d’entropie étant à 31,3 bits

Ouvrir ce cas: hello world

Texte ordinaire — à un bit du plancher théorique. Une distribution mêlée donne un arbre déséquilibré, et le total se pose juste au-dessus de la borne d’entropie. Un mélange réaliste de symboles répétés et uniques. C’est le cas de tous les jours, et le résultat se pose juste au-dessus de la borne d’entropie. — Une distribution mêlée donne un arbre déséquilibré, et le total se pose juste au-dessus de la borne d’entropie.

Un seul symbole — le plancher que Huffman ne peut franchir

Ce que vous savez: Un texte sans la moindre variété. Son entropie est nulle, mais Huffman doit tout de même émettre au moins un bit par symbole : aucun code n’est plus court qu’un bit.

Coût: n = 1 ⇒ ℓ = 1

Exemple résolu: « aaaaaaaaaa » : 10 caractères, un seul symbole distinct, codés en 10 bits. L’entropie du texte vaut 0 bit.

Ouvrir ce cas: caractère unique

Un seul symbole — le plancher que Huffman ne peut franchir. Un symbole, un bit chacun : aucune distribution à exploiter et aucun code plus court disponible. Un texte sans la moindre variété. Son entropie est nulle, mais Huffman doit tout de même émettre au moins un bit par symbole : aucun code n’est plus court qu’un bit. — Un symbole, un bit chacun : aucune distribution à exploiter et aucun code plus court disponible.

Références (1)

Insight block 3 — the term paper itself: D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes." Proceedings of the IRE 40(9), 1098–1101, 1952.

Problème entièrement résolu

L'économie de l'encodage de "hello world" par codage de Huffman 5 étapes
Encodez « hello world » avec le codage de Huffman. Calculez l'économie réalisée — puis trouvez la limite qui indique ce que tout code pourrait atteindre au mieux.
1. L'ASCII à largeur fixe consacre les mêmes huit bits à chaque caractère, quelle que soit sa fréquence d'apparition. C'est ce gaspillage que le codage de Huffman élimine : les symboles fréquents reçoivent des codes courts, les plus rares des codes longs.
  
  $"hello world" : 11 chars \times 8 bits = 88 bits$
2. Commencez par compter les symboles, car le code est construit à partir de ces décomptes. Seuls « l » et « o » se répètent ; les six autres caractères n'apparaissent qu'une seule fois chacun.
  
  $ℓ = 3, o = 2, others = 1 each (8 distinct symbols)$
3. L’entropie de Shannon mesure l’information moyenne par symbole et constitue une borne inférieure absolue : aucun code à décodage unique ne peut obtenir une moyenne plus faible. Tout repose sur trois probabilités distinctes : 3/11 pour « l », 2/11 pour « o » et 1/11 pour chacun des six autres caractères. La somme vaut donc (3/11)(1,8745) + (2/11)(2,4594) + (6/11)(3,4594).
  
  $H = - i \sum p_{i} lo g_{2} p_{i} = 2.845 bits/symbol$
4. Multipliez par la longueur de la chaîne pour obtenir le plancher en bits. Le résultat de Huffman se situe nécessairement au niveau ou au-dessus de cette valeur, qu'il ne peut généralement pas atteindre car les longueurs de code sont des nombres entiers de bits, alors que l'entropie ne l'est pas.
  
  $11 \times 2.845 = 31.3 bits (entropy floor) \leq 32 (Huffman)$
5. Construisez l’arbre pour obtenir la longueur effective. À chaque étape, l’algorithme de Huffman fusionne les deux poids les plus faibles : 1+1, 1+1, 1+1, puis 2+2, puis 2+2, puis 3+4 et enfin 4+7. Chaque fusion ajoute un bit à tous les symboles situés sous le nœud correspondant. La longueur du codage est donc égale à la somme des poids fusionnés, soit 2+2+2+4+4+7+11 = 32, comme l’affiche le visualiseur.
  
  $Huffman = 32 bits ⟹ saving = 1 - \frac{32}{88} = 63.6%$
Réponse

De 88 bits à 32 — soit 63,6 % d'économie. Le plancher d'entropie pour ces fréquences est de 31,3 bits, et Huffman en produit 32 — 0,7 bit au-dessus de l'optimum, consommés par l'arrondi de huit longueurs de code à des bits entiers. La garantie repose sur l'encadrement H ≤ longueur moyenne < H + 1 : Huffman ne dépasse jamais l'optimum de plus d'un bit par symbole. C'est précisément cet écart d'un seul bit qui explique l'existence du codage arithmétique.

$88 \to 32 bits (63.6%) H \leq \overset{ˉ}{ℓ} < H + 1$

Parcours

La compression à la main

Mène à LZ77 des codes de longueur inégale, les plus courts étant consacrés aux symboles fréquents.

Par l’équipe 42Math · Mis à jour 2026-07-27

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

hello world - Les 88 bits de l’ASCII sont ramenés à 32, soit une économie de 63,6 %, et seulement 0,7 bit au-dessus de la limite entropique de 31,3.
mississippi - Quatre caractères distincts sur onze : de 88 bits, on passe à 21, le s recevant un code d’un seul bit. C’est aussi, parmi ces exemples, le plus grand écart par rapport à la limite entropique : 0,95 bit.
uniforme - Six symboles, chacun présent une seule fois : il n’y a donc aucune régularité à exploiter. On obtient tout de même 16 bits, contre 18 avec un code de longueur fixe, car six symboles ne remplissent pas les trois bits.
caractère unique - Dix caractères identiques portent exactement 0 bit d’information, mais le codage de Huffman en utilise tout de même 10 : un par symbole, puisqu’il ne peut pas en attribuer moins d’un.