Visualiseur de codage Huffman

Le codage Huffman optimise la compression des données en construisant dynamiquement un arbre binaire basé sur la fréquence statistique des symboles d'entrée. Il attribue des séquences de bits mathématiquement plus courtes à des caractères hautement probables, atteignant ainsi la limite théorique de l'entropie de Shannon. L'exigence stricte de codes sans préfixe garantit un décodage algorithmique sans ambiguïté. Cette réallocation déterministe du poids binaire minimise mathématiquement la taille totale du fichier sans aucune perte de données.

L'arbre se construit de bas en haut : on liste d'abord chaque caractère selon sa fréquence, puis on fusionne à répétition les deux éléments les moins fréquents en un petit sous-arbre traité comme un seul paquet. On recommence jusqu'à ce qu'il ne reste qu'un arbre ; on lit ensuite chaque code en descendant depuis le sommet — la gauche vaut 0, la droite vaut 1. Cette habitude « gloutonne » de toujours réunir les deux plus petits semble myope, mais produit de façon prouvée les codes les plus courts possibles.

David Huffman l'a conçu en 1951, alors qu'il était étudiant en doctorat au MIT, quand le professeur Robert Fano laissa la classe choisir entre un examen final et un mémoire sur la recherche du code le plus efficace. Fano et Claude Shannon avaient déjà essayé, en construisant leurs arbres de haut en bas. Huffman faillit abandonner, puis comprit que construire de bas en haut — en fusionnant d'abord les symboles les plus rares — était optimal, surpassant la méthode de son propre professeur.