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 un 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 basée sur les statistiques d'apparition des caractères dans le message.
Huffman attribue des codes binaires de longueur variable aux différents caractères selon leur fréquence d'apparition dans le message à compresser (les plus fréquents bénéficiant d'un code court afin de réduire la taille totale des données).
Comment encoder avec le Codage Huffman ? (Principe de chiffrement)
Le code Huffman calcule la fréquence d'apparition des lettres dans le texte, 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. Pour créer cet arbre, rechercher les 2 noeuds les plus faibles (plus petit poids) et les accrocher à un nouveau noeud dont le poids est la somme des 2 noeuds. Répéter l'opération jusqu'à n'avoir plus qu'un seul noeud, qui deviendra la racine (et qui aura comme poids le nombre total de lettres du message).
Le code binaire de chaque caractère est alors obtenu en parcourant l'arbre de la racine jusqu'à la feuille et en notant le parcours (0 ou 1) à chaque noeud. L'ensemble des associations caractère-binaire consitue 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 ? (Principe de déchiffrement)
Le déchiffrement du code Huffman requiert la connaissance de l'arbre ou du dictionnaire de correspondance (caractères <-> codes binaires)
Pour déchiffrer, parcourir l'arbre de la racine jusqu'aux feuilles (généralement du haut vers le bas) jusqu'à obtenir une feuille existante (ou une valeur connue dans le dictionnaire).
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
Pourquoi Huffman est-il utilisé en compression ?
En appliquant l'algorithme du codage Huffman, les caractères les plus fréquents (avec plus grande occurrence) sont codés avec les plus petits mots binaires, ainsi, la place utilisée pour les coder est minimale, ce qui augmente la compression.
Le ratio/rapport/taux de compression dépasse souvent 50%, surtout si le message est long et constitué majoritairement des mêmes caractères.
Cependant, Huffman ne fonctionne pas bien avec des données de taille réduite, car la surcharge de la représentation de l'arbre peut annuler les gains 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 ?
L'arbre/dictionnaire est nécessaire pour attribuer correctement les codes aux symboles. Sans celui-ci, le déchiffrement devient compliqué voire impossible.
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ères 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é ?
Il 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". Sauf code licence open source explicite (indiqué Creative Commons / gratuit), l'algorithme pour "Codage de Huffman", l'applet ou snippet (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou les 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 les données, en téléchargement, script, ou les accès API à "Codage de Huffman" ne sont pas publics, idem pour un usage hors ligne, PC, mobile, tablette, appli iPhone ou Android !
Rappel : dCode est gratuit.
Citation
Le copier-coller de la page "Codage de Huffman" ou de ses résultats est autorisée (même pour un usage commercial) tant que vous créditez dCode !
L'exportation des résultats sous forme de fichier .csv ou .txt est gratuite en cliquant sur l'icone export
Citer comme source bibliographique :
Codage de Huffman sur dCode.fr [site web en ligne], consulté le 21/11/2024,
- Déchiffrement du Codage Huffman
- Générateur de un Codage Huffman
- Qu'est-ce que le codage Huffman ? (Définition)
- Comment encoder avec le Codage Huffman ? (Principe de chiffrement)
- Comment décoder le Code Huffman ? (Principe de déchiffrement)
- 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é ?
