Pourquoi la stratégie gloutonne est optimale
L'algorithme de Huffman est un algorithme glouton : à chaque étape, il fait le choix localement optimal (fusionner les deux nœuds les moins chers) sans regarder devant. Les algorithmes gloutons ne sont pas toujours globalement optimaux — mais ici ils le sont.
L'argument d'optimalité
Supposons qu'un code C ait une longueur moyenne minimale L. Considérez les deux symboles avec la probabilité la plus basse, disons p_a et p_b. Dans tout code optimal, ces deux symboles doivent apparaître comme des feuilles frères au niveau le plus profond de l'arbre. Pourquoi ?
S'ils ne partageaient pas un parent, vous pourriez échanger le symbole plus profond avec un code plus court — réduisant L. Par conséquent, les feuilles les plus profondes doivent être les symboles les moins probables.
Maintenant, si vous combinez a et b en un méta-symbole ab (avec p_ab = p_a + p_b), tout code optimal pour l'alphabet réduit moins un symbole est précisément le code Huffman sur le problème réduit. L'induction complète l'argument.
Vue géométrique
L'algorithme de Huffman construit l'arbre binaire de bas en haut, plaçant les symboles les moins probables à la plus grande profondeur. Cela minimise Σ p_i · profondeur(i) = L.
Une vue équivalente : vous attribuez des étiquettes aux feuilles d'arbre pour minimiser la longueur du chemin pondérée, où le poids de chaque feuille est sa probabilité.
Exécution des étapes gloutonne
Probabilités : p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. Somme = 1.0 ✓
Étape 1 : Les deux les plus basses : C(0.2), D(0.1). Fusionner → CD(0.3). Liste : A(0.4), B(0.3), CD(0.3).
Étape 2 : Les deux les plus basses : B(0.3), CD(0.3) (égalité — chacun valide). Fusionner → BCD(0.6). Liste : A(0.4), BCD(0.6).
Étape 3 : Fusionner A(0.4), BCD(0.6) → racine(1.0). Assigner A=0, BCD=1.
En arrière : BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3).
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9 bits.
Variance de la longueur du code
Deux codes Huffman peuvent atteindre la même L mais avoir des distributions de longueurs de code différentes. La variance des longueurs de code mesure cette dispersion :
Var(l) = E[l²] − (E[l])²
où E[l] = L (longueur moyenne du code) et E[l²] = Σ p_i · l_i².
Pourquoi la variance est importante :
1. Besoins en tampon. En décodage en temps réel, chaque symbole prend un nombre variable de bits. Une variance élevée signifie que certains symboles prennent de nombreux bits — vous avez besoin d'un tampon d'entrée plus grand pour garantir que vous pouvez toujours lire un symbole complet.
2. Latence de décodage. Les codes à variance élevée ont des chemins de décodage avec pire cas long. Les codes à variance basse (touffus) limitent le pire cas plus étroitement.
3. Robustesse. Un bit perdu dans un code à variance élevée cause plus de dégâts de synchronisation car les mots-codes longs doivent être entièrement relus.
Recommandation de Hamming : lorsque plusieurs codes Huffman valides existent (choix de rupture de lien), préférez celui avec variance inférieure — l'arbre touffu.
Calcul de la variance pour deux arbres
Utilisant p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 et le code A=0, B=10, C=110, D=111 :
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
Code Huffman à 3 symboles de bout en bout
Un exemple complet de bout en bout : construire le code Huffman, calculer L, calculer H, vérifier L ≥ H, calculer Var.
Source : p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
Construction Huffman :
Étape 1 : Trié : X(0.6), Y(0.3), Z(0.1). Les deux les plus basses : Y(0.3), Z(0.1).
Fusionner → YZ(0.4). Liste : X(0.6), YZ(0.4).
Étape 2 : Fusionner X(0.6), YZ(0.4) → racine(1.0). Assigner X=0, YZ=1.
YZ → Y=10, Z=11.
Code : X=0 (l=1), Y=10 (l=2), Z=11 (l=2).
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4 bits.
Entropie : H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295 bits.
L = 1.4 ≥ H = 1.295 ✓. L/H = 1.4/1.295 ≈ 1.081. 8.1% au-dessus de l'entropie.
Variance : E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2. Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24.
À votre tour : un pipeline complet
Valeurs log₂ à titre de référence : log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678.