Le codage de Huffman

Le codage de Huffman est un codage statistique à longueur variable (VLC=Variable Length Coding), très proche du codage de Shannon-Fano. Il a été mis au point par David Albert Huffman alors qu'il était étudiant au MIT. Il publia l'algorithme en 1952 dans un article intitulé "A Method for the Construction of Minimum-Redundancy Codes". La compression se fait en remplaçant les caractères les plus fréquents par des codes courts et les caractères les moins fréquents par des codes longs. On observe ainsi des réductions de taille de l'ordre de 20 à 90%. C'est une méthode de compression largement utilisée, souvent en complément d'autres algorithmes.

Huffman utilise une méthode particulière pour choisir la représentation de chaque symbole codé. L'idée est que chaque code ne soit un préfixe d'aucun autre code. En clair, aucun des codes retenus ne doit être le début d'un autre code.

L'animation ci-après construit un arbre de Huffman a partir d'un texte. Pour simplifier le graphe, les caractères sont traduits en majuscules non accentuées et seuls les caractères alphabétiques sont codés. Vous pouvez saisir le texte dans la zone ci-dessous :

Voici trois a, un b, quatre c, six d, douze e, un f, un g, trois h, treize i, un j, un k, un l, un m, douze n, huit o, trois p, cinq q, sept r, sept s, douze t, dix-huit u, deux v, un w, quatre x, un y, et cinq z.