Outil pour compresser/décompresser avec le codage Huffman. Le codage de Huffman est un algorithme de compression de données sans perte utilisant un arbre binaire et un code à longueur variable basé sur des probabilités d'apparition.
Codage de Huffman - dCode
Catégorie(s) : Compression
dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les maths, les énigmes, les géocaches, et les problèmes à résoudre au quotidien !
Une suggestion ? un problème ? une idée ? Écrire à dCode !
Codage de Huffman
Déchiffrement du Codage Huffman
Générateur de Codage Huffman
Réponses aux Questions (FAQ)
Qu'est-ce que le codage Huffman ? (Définition)
Le codage de Huffman est une technique de compression sans perte de données fondée sur les probabilités d'apparition des symboles dans un message.
Il attribue à chaque symbole un mot binaire de longueur variable, de sorte que les symboles les plus fréquents reçoivent les codes les plus courts.
Comment encoder avec le Codage Huffman ?
Le codage de Huffman commence par calculer la fréquence d'apparition de chaque symbole dans le message, et trie les caractères du plus fréquent au moins fréquent.
Exemple : Le message DCODEMESSAGE contient 3 fois la lettre E, 2 fois les lettres D et S, et 1 fois les lettres A, C, G, M et O.
L'algorithme de Huffman va créer un arbre ayant pour feuilles les lettres trouvées et pour valeur (ou poids) leur nombre d'occurrence dans le message.
1 - Associer à chaque symbole un noeud pondéré par sa fréquence.
2 - Sélectionner les deux noeuds de plus faible poids.
3 - Les fusionner en un nouveau noeud dont le poids est la somme des deux.
4 - Répéter les étapes 2 et 3 jusqu'à obtenir un unique noeud racine.
Le code binaire d'un caractère est obtenu en parcourant l'arbre depuis la racine jusqu'à la feuille et en notant le parcours (0 ou 1) à chaque noeud.
L'ensemble des associations caractère-binaire constitue le dictionnaire.
Exemple : DCODEMOI entraine la création d'un arbre tel que le D et le O, présents le plus souvent auront un code court. D=00, O=01, I=111, M=110, E=101, C=100 soit 00100010010111001111 (20 bits) 
Le dictionnaire est indisociable du message, sans lui, le message ne peut pas être décodé.
Comment décoder le Code Huffman ?
Le décodage du code Huffman nécessite la connaissance de l'arbre ou du dictionnaire de correspondance (caractères ↔ codes binaires).
1 - Lire les bits un par un et parcourir l'arbre depuis la racine en suivant le chemin de bits (0 ou 1)
2 - Dès qu'une feuille est atteinte, afficher le symbole correspondant
3 - Répéter l'étape 1
Exemple : Décoder le message 00100010010111001111 avec le dictionnaire décrit ci-dessus. Rechercher 0 ne donne aucune correspondance, continuer alors avec 00 qui est code de la lettre D, puis 1 (n'existe pas), puis 10 (n'existe pas), puis 100 (code pour C), etc.
Le message clair est DCODEMOI
Comment choisir entre gauche et droite lors de la construction de l'arbre de Huffman ?
Lorsque deux noeuds ont le même poids lors de la construction de l'arbre de Huffman, le choix de placer l'un à gauche ou à droite est arbitraire.
Ce choix n'a aucun impact sur la performance du codage : la longueur moyenne reste identique et l'optimalité du code est conservée.
En revanche, ce choix modifie les codes binaires obtenus : inverser gauche/droite revient à échanger les bits 0 et 1 sur une branche, les codes changent, mais leur longueur reste la même.
Dans certaines implémentations, des règles supplémentaires sont utilisées pour rendre le résultat déterministe (possibilité d'utiliser l'ordre lexicographique des symboles), afin d'obtenir toujours le même dictionnaire pour un même message.
Pourquoi Huffman est-il utilisé en compression ?
Le codage de Huffman est utilisé car il réduit la taille moyenne des données en exploitant les fréquences des symboles.
La longueur moyenne du code est proche de la limite théorique donnée par l'entropie de Shannon.
Le gain dépend fortement de la distribution des symboles : il est élevé si certaines valeurs sont très fréquentes mais faible si les fréquences sont uniformes.
A noter que pour des messages courts, le coût de stockage de l'arbre ou du dictionnaire peut réduire, voire annuler, le gain de compression.
Comment reconnaitre le codage de Huffman ?
Le message codé est au format binaire (ou dans une représentation hexadécimale) et doit être accompagné d'un arbre ou d'une table/dictionnaire de correspondance pour le déchiffrement.
La présence de codes de longueurs variables est une caractéristique importante.
Les notions d'arborescence, d'arbre ou d'élagage (technique visant à optimiser l'arbre en supprimant des branches/noeuds dynamiquement) sont des indices.
Comment déchiffrer le codage de Huffman sans arbre ?
Sans l'arbre ou le dictionnaire, le décodage d'un message Huffman est en général impossible. En effet, plusieurs codes préfixes différents peuvent produire des séquences binaires compatibles.
En faisant des hypothèses sur la longueur du message et de la taille des mots binaires, il est possible de rechercher la liste probable des mots utilisés par Huffman.
Il convient ensuite d'y associer les bonnes lettres, ce qui représente une seconde difficulté pour le déchiffrement et requiert certainement des méthodes automatiques.
Quelles sont les variantes du chiffre Huffman ?
Il existe des variantes de Huffman lors de la création de l'arbre/du dictionnaire.
Soit le dictionnaire est statique : chaque caractère/octet a un code prédéfini et connu ou publié à l'avance (il n'a donc pas besoin d'être transmis)
Soit le dictionnaire est semi-adaptatif : le contenu est analysé pour calculer les fréquence de chaque caractère et un arbre optimisé est utilisé pour le codage (il doit alors être transmis pour le décodage). C'est la version implémentée sur dCode.
Soit le dictionnaire est adaptatif : à partir d'un arbre connu (publié avant et donc non transmis) celui-ci est modifié pendant la compression et optimisé au fur et à mesure. Le temps de calcul est beaucoup plus long mais propose souvent un meilleur taux de compression.
Le code Morse utilise des codes de longueur variable de manière similaire au codage Huffman.
Quand le codage Huffman a-t-il été inventé ?
Le codage de Huffman a été publié en 1952 par David Albert Huffman.
Code source
dCode se réserve la propriété du code source pour "Codage de Huffman". Tout algorithme pour "Codage de Huffman", applet ou snippet ou script (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou toutes fonctions liées à "Codage de Huffman" (calculer, convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codés en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) ou toute base de données, ou accès API à "Codage de Huffman" ou tout autre élément ne sont pas publics (sauf licence open source explicite). Idem avec le téléchargement pour un usage hors ligne sur PC, mobile, tablette, appli iPhone ou Android.
Rappel : dCode est une ressource éducative et pédagogique, accessible en ligne gratuitement et pour tous.
Citation
Le contenu de la page "Codage de Huffman" ainsi que ses résultats peuvent être copiés et réutilisés librement, y compris à des fins commerciales, à condition de mentionner dCode.fr comme source (Licence de libre diffusion Creative Commons CC-BY).
L'export des résultats est gratuit et se fait simplement en cliquant sur les icônes d'export ⤓ (format .csv ou .txt) ou ⧉ copier-coller.
Pour citer dCode.fr sur un autre site Internet, utiliser le lien :
Dans un article scientifique ou un livre, la citation bibliographique recommandée est : Codage de Huffman sur dCode.fr [site web en ligne], consulté le 23/05/2026,
- Déchiffrement du Codage Huffman
- Générateur de Codage Huffman
- Qu'est-ce que le codage Huffman ? (Définition)
- Comment encoder avec le Codage Huffman ?
- Comment décoder le Code Huffman ?
- Comment choisir entre gauche et droite lors de la construction de l'arbre de Huffman ?
- Pourquoi Huffman est-il utilisé en compression ?
- Comment reconnaitre le codage de Huffman ?
- Comment déchiffrer le codage de Huffman sans arbre ?
- Quelles sont les variantes du chiffre Huffman ?
- Quand le codage Huffman a-t-il été inventé ?
