Un code comme un arbre
Un code préfixe se mappe à un arbre binaire : la racine représente le début du décodage, les branches gauches représentent le bit 0, les branches droites représentent le bit 1, et les feuilles représentent les mots de code complets.
La contrainte géométrique : chaque feuille termine un chemin racine-feuille. Aucune feuille ne peut avoir un descendant (si c'était le cas, son mot de code serait un préfixe du mot de code du descendant, violant la propriété préfixe).
Cela donne à l'inégalité de Kraft une interprétation géométrique :
Chaque feuille à profondeur d « occupe » une fraction 2^(−d) de la capacité totale de l'arbre. La capacité totale d'un arbre binaire complet à profondeur D est 1. Un code préfixe utilise des feuilles à diverses profondeurs ; la somme de Kraft mesure l'occupation totale.
Somme de Kraft = 1 : code complet (chaque chemin se termine à une feuille — empilement parfait).
Somme de Kraft < 1 : code incomplet (une capacité d'arbre inutilisée — plus de symboles pourraient être ajoutés).
Somme de Kraft > 1 : impossible pour les codes préfixes (certains chemins devraient partager une feuille).
Les feuilles plus profondes = Les codes plus longs = Moins de capacité
Une feuille à profondeur 1 utilise la moitié de la capacité de l'arbre (2^(−1) = 0.5).
Une feuille à profondeur 3 utilise un huitième (2^(−3) = 0.125).
Placer un mot de code court haut dans l'arbre bloque tous ses descendants d'être utilisés — vous échangez un code court contre de nombreux codes potentiellement plus longs.
Construire un arbre préfixe
Considérez 5 symboles avec des longueurs l = {1, 2, 3, 3, 3}. Somme de Kraft = 2^(−1) + 2^(−2) + 3·2^(−3) = 0.5 + 0.25 + 0.375 = 1.125 > 1.
Cela dépasse 1 : ces longueurs sont incompatibles avec un code préfixe. Au moins une longueur doit augmenter.
Correction : changez l_1 de 1 à 2. Nouvelles longueurs {2, 2, 3, 3, 3} : Kraft = 2·2^(−2) + 3·2^(−3) = 0.5 + 0.375 = 0.875 < 1. Valide, mais incomplet.
Correction : changez l_1 de 2 à 2, ajoutez l_2 = 3 pour utiliser la capacité restante. Kraft = 0.875 ; restant = 0.125 = 2^(−3) : place pour une autre feuille de profondeur 3.
Pourquoi l'entropie limite la longueur du code
L'inégalité de Kraft contraint la structure du code (les longueurs doivent s'adapter à l'arbre). L'entropie de Shannon contraint l'efficacité du code (la longueur moyenne ne peut pas surpasser un plancher théorique).
Les longueurs de code optimales. Pour un symbole avec probabilité p_i, la longueur de code idéale est log₂(1/p_i). Les symboles rares méritent des codes longs ; les symboles fréquents méritent des codes courts. Cela reflète l'égalité de Kraft : 2^(−l_i) = p_i quand l_i = log₂(1/p_i).
Mais log₂(1/p_i) est rarement un entier. L'arrondi vers le haut à ⌈log₂(1/p_i)⌉ donne la longueur de Huffman, qui satisfait H ≤ L < H + 1.
Lecture géométrique. Tracez chaque symbole comme un point sur l'arbre binaire à profondeur l_i. La somme de Kraft mesure la couverture totale des feuilles. L'entropie mesure la profondeur moyenne pondérée, pondérée par la probabilité. Théorème de Shannon : la profondeur moyenne pondérée par la probabilité ≥ le contenu informatif pondéré par la probabilité.
Vérification de la limite d'entropie
L'exemple travaillé : p = [1/2, 1/4, 1/8, 1/8] pour les symboles {A, B, C, D}.
Longueurs optimales : l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
Ce sont tous des entiers — une correspondance parfaite. Code de Huffman : A=0, B=10, C=110, D=111.
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75.
H = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75. L = H exactement : code optimal.
Un exemple travaillé complet
Pipeline complet : données des probabilités, calculez l'entropie, vérifiez qu'un code respecte la limite.
Source : p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125.
H = 1.75 bits (calculé ci-dessus).
Un code bloc naïf : 4 symboles → 2 bits chacun → L = 2.0. Surcharge par rapport à l'entropie : 2.0 − 1.75 = 0.25 bits/symbole = 12.5 % de gaspillage.
Le code de longueur variable économise 12.5 % par rapport à la longueur fixe. Pour les messages longs, c'est substantiel.
Taux d'entropie de l'anglais. Shannon a estimé l'entropie de l'anglais écrit à environ 1.0 à 1.3 bits par caractère, malgré l'utilisation de codes ASCII 5 bits. Ce ratio 4:1 reflète la redondance massive du langage naturel — les lettres courantes se regroupent, les mots se répètent, la grammaire contraint les séquences.
La compression ne peut pas surpasser l'entropie
Taux de compression : H / (longueur du code bloc). Pour notre exemple : 1.75/2.0 = 0.875 — efficacité de 87.5 %.
Pouvez-vous compresser davantage ? Seulement en utilisant le contexte : si vous codez des paires ou des triplets de symboles ensemble, l'entropie conjointe H(X,Y) peut être inférieure à 2·H(X) en raison des dépendances statistiques. C'est l'extension du théorème du codage sans bruit aux n-grammes.