Aire de jeu du codage entropique

Explore comment différentes distributions de symboles affectent l'entropie de Shannon, compare les limites du codage de Huffman, et découvre comment l'entropie régit les fonctions de perte et l'incertitude du vocabulaire dans les grands modèles de langage (LLM) modernes.

Valeurs de départ — Aire de jeu du codage entropique

Paramètre de distribution (λ)	1.5

Modifiez un réglage ci-dessus et les résultats sont recalculés.

Chargement de la simulation interactive...

Les bits entiers, voilà ce que Huffman paie 🖖

Le codage entropique exploite la redondance statistique pour représenter les messages avec moins de bits. Le théorème de codage de source de Shannon énonce que la longueur moyenne minimale absolue de tout code sans perte est l'entropie de Shannon : H(X) = −Σ p_i log₂ p_i. Le codage de Huffman est optimal pour un alphabet donné lorsque les symboles sont codés individuellement, mais il est contraint à des mots de code de longueur entière. Cette contrainte entière signifie que Huffman peut s'écarter de l'entropie théorique jusqu'à 0,086 bit/symbole (et bien plus si un symbole a p_i ≈ 1). Le codage arithmétique (par ex. ANS) dépasse cette limite en associant la séquence entière à des intervalles fractionnaires.

Lien avec les LLM et l'IA : Dans les modèles de langage (LLM) modernes, l'entropie est un concept central tant pour l'entraînement que pour la génération. Les LLM sont entraînés en minimisant la perte d'entropie croisée entre leurs prédictions de vocabulaire et le texte réel. Lors de la génération (inférence), le LLM produit une distribution de probabilité sur son vocabulaire pour le prochain token. L'entropie de cette distribution mesure l'incertitude de prédiction du modèle : une distribution plate (entropie élevée) donne un texte créatif ou aléatoire, tandis qu'une distribution pointue (entropie faible) donne un texte très prévisible. Des paramètres d'échantillonnage comme la température mettent directement à l'échelle cette entropie (une température plus basse la réduit, une température plus haute l'augmente), tandis que l'échantillonnage nucleus (Top-p) borne dynamiquement la probabilité cumulée pour élaguer les queues de forte entropie.

Pourquoi les symboles rares coûtent plus de bits 🖖

La vraie leçon de cet outil : le nombre idéal de bits pour un symbole est sa surprise, −log₂ p. Un symbole apparaissant une fois sur deux mérite 1 bit ; un symbole de probabilité 1 sur 1000, environ 10 bits. L'entropie n'est que la surprise moyenne sur l'ensemble des symboles. C'est pourquoi les distributions asymétriques (comme les préréglages laplacien ou exponentiel) se compriment bien, alors qu'un alphabet uniforme non — quand tout est équiprobable, il n'y a aucune redondance à supprimer.

Le morse : codage entropique avant Shannon 🖖

Le code morse attribuait le signal le plus court, un simple point, au E, la lettre la plus fréquente en anglais, et de longues séquences aux lettres rares comme Q et Z. Pour fixer les longueurs, Alfred Vail aurait compté les caractères en plomb dans la casse d'un imprimeur afin d'estimer la fréquence des lettres. C'était un codage à longueur variable fonctionnel dès les années 1840 — près d'un siècle avant que Shannon ne formalise, en 1948, pourquoi il fonctionne.

UNE ÉTAPE D'UNE CHAÎNE — CE QUI ENTRE, CE QUI SORT, CE QUI CASSE ENSUITE

Où cette étape se situe dans la chaîne d'encodage

Un encodeur vidéo n'est pas un algorithme mais huit étapes dans un ordre fixe, et cet ordre n'est pas arbitraire : chaque étape existe parce que la précédente a rendu son travail possible. Cet outil modélise l'une d'elles. La chaîne ci-dessous renvoie aux sept autres.

Aire de jeu du codage entropique — compacte les symboles quantifiés dans le moins de bits que leur statistique autorise

Ce qui entre: Un flux d'entiers quantifiés, fortement penché vers zéro.
Ce qui sort: Le train de bits final. Rien n'est jeté ici.
Ce que suppose l'étape suivante: Rien en aval — c'est la dernière étape de codage. Ce qu'elle suppose est en amont : que la distribution des symboles a déjà été rendue déséquilibrée pour elle.
Ce qui se casse ici: Aucun codeur entropique ne peut descendre sous l'entropie de Shannon de ce qu'on lui donne : son plafond est donc fixé entièrement par les étapes antérieures. Sur des coefficients non quantifiés il trouve peu de redondance, et c'est la raison pour laquelle l'étape avec perte vient d'abord et non en dernier.

Étape précédente: Quantification Étape suivante: Contrôle de débit

Problème entièrement résolu

La marge restante pour un algorithme plus astucieux que Huffman sur 16 symboles 6 étapes
16 symboles, loi de Laplace, entropie 3,010 bits. Huffman obtient 3,012. Calculez la marge d'amélioration restante pour un algorithme plus ingénieux.
1. L'entropie est la surprise moyenne, en bits, d'un symbole tiré de cette distribution. C'est une propriété des seules probabilités et elle ne sait rien d'un quelconque code.
  
  $H (X) = - i = 1 \sum N p_{i} lo g_{2} p_{i} = 3.010 bits/symbol (N = 16, Laplacian, λ = 1.5)$
2. L'alternative naïve donne à chaque symbole le même nombre de bits, et 16 symboles en nécessitent 4. C'est la référence par rapport à laquelle l'économie est mesurée.
  
  $L_{fixed} = ⌈ lo g_{2} N ⌉ = ⌈ lo g_{2} 16 ⌉ = 4.0 bits/symbol$
3. Huffman attribue des codes courts aux symboles fréquents et des codes longs aux symboles rares, et la moyenne est la longueur pondérée par les probabilités.
  
  $\overset{ˉ}{L} = \sum p_{i} L_{i} = 3.012 bits/symbol$
4. L'économie compare les deux longueurs de code, et non le code avec l'entropie — c'est pourquoi il s'agit d'une affirmation sur cette alternative plutôt que sur la limite.
  
  $savings = \frac{4.0 - 3.012}{4.0} = 24.7%$
5. Comparons maintenant à la limite. Le théorème du codage de source de Shannon indique qu'aucun code préfixe ne peut descendre sous H, et Huffman est garanti de se situer sous H + 1.
  
  $H \leq \overset{ˉ}{L} < H + 1 (Shannon); \overset{ˉ}{L} - H = 3.012 - 3.010 = 0.002 bits$
6. Exprimez l'écart restant sous forme de fraction et la question de l'optimisation trouve d'elle-même sa réponse.
  
  $\frac{0.002}{3.010} = 0.07% above the floor$
Réponse

0,002 bit par symbole, soit 0,07 %. Le théorème de Shannon encadre tout code préfixe entre H et H + 1, et l'algorithme de Huffman y est prouvé optimal. Aucun code préfixe ne battra donc jamais 3,012 sur ce texte. L'économie de 24,7 % par rapport au codage à longueur fixe est bien réelle, et les 0,07 % restants représentent tout ce qu'une ingénierie plus fine pourrait encore apporter. Au-delà, la compression progresse en modifiant le modèle plutôt que le code : si des symboles voisins sont corrélés, l'entropie de la distribution conditionnelle est inférieure à 3,010. C'est là une tout autre mesure.

$\overset{ˉ}{L} - H = 0.002 bits : Huffman is 0.07% off optimal here$

Références (1)

Insight block 2 — entropy as average surprise, and the limit Huffman cannot beat: C. E. Shannon, "A Mathematical Theory of Communication." Bell System Technical Journal 27(3), 379–423, 1948.

Par l’équipe 42Math · Mis à jour 2026-07-29

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

Uniforme 8 - Source uniforme à 8 symboles : H=3 bits, aucun gain de codage — l'entropie égale le code à longueur fixe
Type DCT (Laplace) - Laplacienne de type DCT : H≈2.1 bits, 23% d'économie — la plupart des coefficients AC vidéo se regroupent près de zéro
Type vecteur de mouvement - Exponentielle de type vecteur de mouvement : H≈2.3 bits, 43% d'économie par rapport à un code fixe de 4 bits
Bimodale - Bimodal : deux symboles dominants donnent H≈2.5 bits, un gain de compression Huffman significatif