Code de Huffman
Code de longueur fixe
Économisé
Entropie

Symbole Occurrences Code Bits Bits au total

Plus d'informations sur le codage de Huffman

Constructeur de codes de Huffman

Pourquoi une lettre fréquente comme e devrait-elle prendre autant de bits qu'une lettre rare comme w ? Le codage de Huffman donne des codes courts aux symboles fréquents et des codes longs aux symboles rares, et il le fait de la meilleure façon possible. Tapez un texte ou choisissez un exemple, et construisez son arbre de Huffman une étape à la fois : les deux arbres les plus légers se réunissent sous un nouveau nœud, encore et encore, jusqu'à ce qu'il ne reste qu'un seul arbre. Chaque chemin depuis le sommet épelle alors un code, et vous pouvez suivre chaque symbole dans les bits codés. Tapez un texte ou choisissez un exemple. Chaque symbole commence comme une feuille portant son nombre d'occurrences. Avancez dans la construction étape par étape : chaque étape réunit les deux arbres les plus légers sous un nouveau nœud qui porte leur somme, jusqu'à ce qu'il ne reste qu'un seul arbre. Le chemin du sommet jusqu'à une feuille donne alors son code, 0 pour la gauche et 1 pour la droite. Cliquez sur une feuille, une ligne ou un morceau des bits pour suivre un symbole, et comparez le total avec un code de longueur fixe et avec l'entropie.

Comment ça marche

  1. Tapez ou collez un texte, ou choisissez un exemple comme ABRACADABRA ou MISSISSIPPI RIVER.
  2. Avancez dans la construction avec Étape suivante, ou appuyez sur Lecture : chaque étape réunit les deux arbres les plus légers sous un nœud qui porte leur somme.
  3. Une fois l'arbre complet, cliquez sur une feuille, une ligne du tableau ou un morceau des bits pour suivre un symbole, et comparez les totaux dans les tuiles.

Comment l'arbre se construit

Comptez combien de fois chaque symbole apparaît et faites de chacun un arbre d'une seule feuille, pondéré par son nombre d'occurrences. Répétez ensuite une seule étape simple : prenez les deux arbres de plus petit poids et accrochez-les sous un nouveau nœud dont le poids est leur somme. Chaque étape laisse un arbre de moins, si bien qu'après n − 1 étapes pour n symboles il ne reste qu'un seul arbre. Les symboles rares ont été réunis en premier et se trouvent tout en bas ; les symboles fréquents ont été réunis tard et se trouvent près du sommet.

Lire les codes

Descendez depuis le sommet : un pas vers la gauche ajoute un 0, un pas vers la droite un 1. Le chemin jusqu'à une feuille est le code de ce symbole. Comme les symboles ne se trouvent qu'aux feuilles, aucun code n'est le début d'un autre, et une suite de bits peut donc être décodée sans aucun séparateur : suivez les bits vers le bas de l'arbre et, chaque fois que vous atteignez une feuille, écrivez son symbole et repartez du sommet. Pour ABRACADABRA, Huffman a besoin de 23 bits, contre 33 pour un code fixe de 3 bits par lettre.

Questions fréquemment posées

Pourquoi le code de Huffman est-il le meilleur possible ?

Parmi tous les codes qui donnent à chaque symbole sa propre suite de bits entiers, aucun n'a un total plus court pour les nombres d'occurrences donnés. La preuve suit la construction : dans un code optimal, on peut toujours faire des deux symboles les plus rares des frères au niveau le plus profond, et les réunir laisse un problème plus petit du même type. Le nombre total de bits est égal à la somme des poids de tous les nœuds internes de l'arbre.

Qu'est-ce qu'un code préfixe ?

Un code dans lequel aucun mot de code n'est le début d'un autre, comme 0, 10, 110 et 111. Cette propriété permet à un décodeur de lire un flux de bits sans séparateurs, car il sait toujours où se termine un mot de code. Tout code de Huffman est un code préfixe : les symboles ne se trouvent qu'aux feuilles de l'arbre.

L'arbre de Huffman est-il unique ?

Pas tout à fait : quand deux arbres ont le même poids, l'un ou l'autre peut être pris en premier, et la gauche et la droite peuvent être échangées. Des choix différents donnent des codes différents, mais toujours le même nombre total de bits. Le constructeur départage toujours les égalités de la même façon, si bien qu'un texte donne toujours le même arbre.

À quel point Huffman s'approche-t-il de l'entropie ?

La longueur moyenne des codes est au moins égale à l'entropie et la dépasse de moins d'un bit. Elle est égale à l'entropie quand chaque probabilité est une puissance de un demi, comme dans l'exemple des occurrences divisées par deux. Le codage arithmétique et les codeurs par intervalles modernes évitent la limite des bits entiers et s'en approchent encore davantage.

Mon texte est-il envoyé quelque part ?

Non. L'arbre et les codes sont calculés dans votre navigateur, et votre texte reste dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur