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 ? Ecrire à dCode !
Le code Huffman utilise la fréquence d'apparition des lettres dans le texte, calculer et trier 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.
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 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, 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
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%
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 de correspondance pour le déchiffrement.
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.
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.
Il a été publié en 1952 par David Albert Huffman.
dCode se réserve la propriété du code source de l'outil 'Codage de Huffman' en ligne. Sauf code licence open source explicite (indiqué CC / Creative Commons / gratuit), tout algorithme pour 'Codage de Huffman', applet ou snippet (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou toute fonction liée à 'Codage de Huffman' (calculer, convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codé en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) aucune donnée, téléchargement, script, copier-coller, ou accès API à 'Codage de Huffman' ne sera cédé gratuitement, idem pour un usage hors ligne, PC, tablette, appli iPhone ou Android ! dCode est gratuit est en ligne.
Rendez-vous sur notre communauté Discord dCode pour participer au forum d'entraide !
PS : Pour les messages codés, testez notre détecteur de chiffrement !
Grâce à vos remarques, réponses et commentaires pertinents, dCode peut développer le meilleur outil 'Codage de Huffman', alors écrivez-nous c'est gratuit ! Merci !