Comment Huffman construit le code optimal
Hamming présente le codage Huffman comme un algorithme glouton qui construit un code sans préfixe de longueur moyenne minimale. L'idée clé : construire l'arbre de bas en haut, en fusionnant toujours les deux symboles les moins probables.
La passe avant (Construire)
1. Trier tous les symboles par probabilité, du plus haut au plus bas.
2. Prendre les deux symboles les moins probables. Les combiner en un nouveau méta-symbole avec probabilité = somme des deux.
3. Insérer le méta-symbole à sa position triée.
4. Répéter jusqu'à ce qu'il ne reste que deux symboles.
5. Assigner 0 et 1 aux deux symboles restants.
La passe arrière (Attribuer les codes)
Annuler les fusions en sens inverse : à chaque division, les deux symboles qui ont été fusionnés reçoivent les mêmes bits de préfixe que leur parent combiné, plus un 0 supplémentaire (un enfant) ou 1 (l'autre enfant). L'attribution 0/1 est arbitraire — l'une ou l'autre est valide.
Pourquoi c'est optimal : si un autre code avait une longueur moyenne plus petite L', en appliquant la même réduction avant, on produirait finalement deux symboles avec une longueur moyenne inférieure à 1 bit — impossible pour un code à 2 symboles. Contradiction.
Tracer l'algorithme
Exemple de Hamming : quatre symboles A, B, C, D avec p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
Passe avant :
Étape 1 : Triés : A(0,5), B(0,25), C(0,125), D(0,125). Les deux plus bas : C, D.
Étape 2 : Fusionner CD avec p=0,25. Nouvelle liste : A(0,5), B(0,25), CD(0,25).
Étape 3 : Les deux plus bas : B(0,25), CD(0,25). Fusionner BCD avec p=0,5.
Étape 4 : Deux symboles restent : A(0,5), BCD(0,5). Assigner A=0, BCD=1.
Passe arrière :
BCD → B obtient 10, CD obtient 11. CD → C obtient 110, D obtient 111.
Code final : A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3).
L = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 1,75 bits.
Codes Huffman multiples et valides
Hamming note deux sources de non-unicité :
1. Attribution arbitraire 0/1. À chaque division, vous pouvez donner 0 à l'un ou l'autre enfant. Permuter 0 et 1 partout donne un code différent avec un L identique.
2. Rupture d'égalité. Lorsque deux nœuds ont une probabilité égale, l'un ou l'autre peut être placé plus haut (combiné en premier). Différents choix de rupture d'égalité peuvent produire des arbres structurellement différents — « longs » par rapport à « touffus » — avec le même L mais des distributions de longueurs de code différentes.
Long par rapport à Touffu
Arbre long (asymétrique) : un symbole à chaque niveau de profondeur (structure de type Fibonacci). Les longueurs de code varient considérablement : un symbole obtient un code court, d'autres se succèdent vers des codes plus longs.
Arbre touffu (équilibré) : symboles répartis uniformément sur les niveaux de profondeur. Les longueurs de code se regroupent près de la moyenne. Variance inférieure.
Recommandation de Hamming : lorsque vous avez le choix, préférez l'arbre touffu. Même L, mais variance plus petite dans les longueurs de code → temps de décodage plus uniforme → exigences de mémoire tampon plus petites dans les applications en temps réel.
Calcul de la variance de la longueur du code
Variance des longueurs de code : Var = E[l²] − (E[l])²
Pour le code {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} avec p=[0,5, 0,25, 0,125, 0,125] :
E[l] = L = 1,75
E[l²] = 0,5·1² + 0,25·2² + 0,125·3² + 0,125·3² = 0,5 + 1,0 + 1,125 + 1,125 = 3,75
Var = 3,75 − 1,75² = 3,75 − 3,0625 = 0,6875
Un code touffu alternatif pour les symboles de probabilité égale utilise tous les codes de longueur 2 : L=2, Var=0.
Gains de compression par rapport à la distribution des symboles
Règle de Hamming : le codage Huffman est rentable uniquement lorsque les probabilités des symboles diffèrent considérablement.
Probabilités égales. Si tous les symboles 2^k ont une probabilité égale 1/2^k, Huffman produit un code de bloc : chaque symbole obtient la longueur k. L = H = k. Aucun gain par rapport au simple code de bloc.
Probabilités asymétriques. Si un symbole domine (p >> 1/2^k pour les autres), Huffman lui assigne un code très court (longueur 1 ou 2), réduisant considérablement L.
Le code virgule (terme de Hamming). Lorsque chaque probabilité dépasse 2/3 du total restant, Huffman produit naturellement : p(s1)→0, p(s2)→10, p(s3)→110, ..., jusqu'à deux codes de même longueur à la fin. C'est un « code virgule » : le 0 final après une suite de 1 agit comme une virgule.
Hamming note : la compression de données réelles (sauvegarde, archivage de fichiers) peut réduire le stockage de plus de moitié lorsque la source a des probabilités asymétriques — le texte anglais étant un exemple principal.
Codage Huffman par rapport au code de bloc : comparaison numérique
Deuxième exemple de Hamming : p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30.
Code de bloc : 8 symboles → 3 bits chacun → L_block = 3.
Hamming calcule le code Huffman et rapporte L_Huffman ≈ 2,58 bits.
Économies : (3 − 2,58)/3 ≈ 14 % de compression par rapport au codage de bloc.
Lorsque les probabilités des symboles diffèrent considérablement (1/3 par rapport à 1/30 ici, un ratio 10:1), le codage de longueur variable paie considérablement.
Programmes auto-compilants
Hamming termine le chapitre 11 avec une idée frappante : un encodeur Huffman peut s'encoder lui-même. L'arbre de décodage (qui indique au décodeur comment lire le message compressé) est transmis avec les données compressées. Le récepteur n'a besoin d'aucune connaissance préalable du code.
L'encodeur : échantillonne les données, estime les probabilités, construit le code Huffman, encode l'arbre de décodage en tant qu'en-tête, puis encode les données.
Le décodeur : lit l'en-tête pour reconstruire l'arbre, puis décode les données l'utilisant.
Le point de Hamming : tout ce pipeline peut s'exécuter en tant que fonction de bibliothèque sans implication humaine. Vous l'appelez, il compresse et décompresse automatiquement. Les formats d'archivage modernes (ZIP, gzip, bzip2) implémentent exactement ce modèle.
Le principe plus profond : l'intelligence se trouve dans l'algorithme, pas dans une table de code fixe. L'algorithme s'adapte à toutes les données qu'il reçoit. C'est le modèle que Hamming voit dans tous les grands systèmes d'ingénierie : l'adaptabilité intégrée, pas ajoutée au dernier moment.