Le codage de Huffman expliqué
Les ordinateurs stockent généralement chaque lettre sur le même nombre de bits, huit en ASCII simple. C'est simple mais peu économe, car certaines lettres sont bien plus fréquentes que d'autres. En 1951, un étudiant a trouvé la meilleure façon de donner à chaque symbole un code de longueur propre, court pour les symboles fréquents et long pour les rares, grâce à une construction si simple qu'elle tient en quelques lignes. Le codage de Huffman se trouve aujourd'hui dans presque tous les fichiers compressés, images et sons que vous ouvrez.
Des codes courts pour les symboles fréquents
Le code Morse utilisait déjà cette idée dans les années 1830 : E, la lettre la plus fréquente en anglais, est un simple point, tandis que Q s'écrit trait trait point trait. Un tel code fait gagner du temps et de la place dès que certains symboles apparaissent plus souvent que d'autres. Mais les longueurs variables posent un problème que le Morse résolvait par des pauses : comment savoir où un code se termine et où commence le suivant ? Et quelles longueurs attribuer à chaque symbole pour que le total soit le plus petit possible ?
Les codes préfixes
Le premier problème disparaît si aucun code n'est le début d'un autre. Avec les codes A = 0, B = 10, C = 110 et D = 111, les bits 0101100 ne peuvent se lire que A B C A : dès que les bits lus jusque-là forment un code, ce code est complet. Ces codes préfixes correspondent exactement aux arbres binaires dont les symboles sont aux feuilles, où chaque branche gauche représente 0 et chaque branche droite 1. Choisir un code, c'est choisir un arbre.
La construction de Huffman
Partez d'une feuille par symbole, pondérée par sa fréquence d'apparition. Prenez les deux arbres les plus légers et réunissez-les sous un nouveau nœud dont le poids est leur somme, puis recommencez jusqu'à ce qu'il ne reste qu'un seul arbre. C'est tout l'algorithme. Les symboles rares sont réunis en premier et finissent au fond de l'arbre, avec des codes longs ; les symboles fréquents sont réunis en dernier et restent près du sommet, avec des codes courts. Avec une file de priorité, il faut un temps proportionnel à n log n pour n symboles.
Pourquoi c'est optimal
Dans un arbre optimal, on peut toujours placer les deux symboles les plus rares comme frères au niveau le plus profond : les échanger avec ce qui s'y trouve ne peut que raccourcir le total. Réunissez-les en un seul symbole ayant leur poids combiné, et le reste est le même problème avec un symbole de moins ; l'étape gloutonne n'exclut donc jamais la meilleure réponse. Le nombre total de bits utilisés est égal à la somme des poids de tous les nœuds internes, que les réunions successives maintiennent aussi petite que possible.
Un mémoire au lieu d'un examen
En 1951, David Huffman, étudiant de troisième cycle au MIT, suivait le cours de théorie de l'information de Robert Fano. Fano laissa le choix à ses étudiants : passer l'examen final ou rédiger un mémoire sur la recherche du code binaire le plus efficace. Huffman faillit renoncer au mémoire, puis comprit que construire l'arbre de bas en haut, au lieu de le diviser de haut en bas comme dans la méthode de Shannon–Fano, donne toujours le meilleur résultat. Il le publia en 1952 ; la méthode de l'étudiant surpassait celle que son professeur avait mise au point avec Claude Shannon.
Près de l'entropie
Claude Shannon a montré qu'aucun code ne peut utiliser, en moyenne, moins de bits par symbole que l'entropie de la source. Un code de Huffman atteint exactement l'entropie quand chaque probabilité est une puissance de un demi, et ne la dépasse jamais d'un bit entier par symbole. L'écart compte quand un symbole est très fréquent : un symbole qui représente 99 % du texte a toujours besoin d'au moins un bit entier, alors qu'il ne porte qu'environ 0,015 bit d'information. Le codage arithmétique et les systèmes de numération asymétriques (ANS) des compresseurs récents évitent cette limite.
Des codes de Huffman partout
Le codage de Huffman est rarement utilisé seul, mais il forme la dernière étape de nombreux formats. Deflate, présent dans ZIP, gzip et PNG, remplace d'abord les répétitions par des références, puis écrit le résultat avec des codes de Huffman. JPEG les utilise pour les nombres qui restent après sa transformation de l'image, MP3 pour ses données audio, et les télécopieurs pour les longueurs des plages noires et blanches. Les formats transmettent généralement un code de Huffman canonique, dont seules les longueurs de code doivent être stockées, car les codes eux-mêmes peuvent être reconstruits à partir d'elles.
À vous d'explorer
Ouvrez le constructeur de codes de Huffman pour construire, une étape à la fois, l'arbre d'ABRACADABRA, de MISSISSIPPI RIVER, d'une phrase de votre choix ou de n'importe quel autre texte. Regardez les deux arbres les plus légers se réunir à chaque étape, cliquez sur une feuille pour voir son code, suivez un symbole dans les bits codés, et comparez le total avec un code de longueur fixe, UTF-8 et l'entropie.
Questions fréquemment posées
Quelle est la différence entre le codage de Huffman et celui de Shannon–Fano ?
Le codage de Shannon–Fano construit l'arbre par le haut, en divisant encore et encore les symboles en deux groupes de poids presque égaux. Il est souvent bon, mais pas toujours optimal. Huffman construit l'arbre par le bas en réunissant les deux arbres les plus légers, et donne toujours le code préfixe le plus court possible.
Le décodeur a-t-il besoin de l'arbre ?
Oui, il lui faut le même code. Les fichiers compressés le stockent donc, en général sous forme de liste de longueurs de code pour un code canonique, ce qui ne prend que quelques dizaines d'octets. Pour des textes courts, ce surcoût peut dépasser le gain ; le constructeur ne compte que les bits codés.
Le codage de Huffman peut-il agrandir un fichier ?
Les symboles codés ne prennent jamais plus de bits qu'un code de longueur fixe pour les mêmes symboles. Mais la table des codes doit aussi être stockée, si bien que pour des données très courtes ou presque aléatoires, le résultat peut être légèrement plus gros que l'original.
Que dit l'inégalité de Kraft ?
Qu'un code préfixe de longueurs de code l₁, l₂, … existe exactement quand la somme de 2 puissance −l sur tous les symboles vaut au plus 1. Pour un arbre complet, comme tout arbre de Huffman d'au moins deux symboles, la somme vaut exactement 1.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Ouvrir le constructeur de codes de Huffman