Codage de Huffman

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.