L'entropie expliquée

En 1948, un ingénieur des Bell Labs, Claude Shannon, posa une question que personne n'avait formulée avec précision : combien d'information un message contient-il ? Sa réponse fut un nombre, mesuré en bits, qui ne dépend pas de ce que le message signifie mais de son caractère surprenant. Ce nombre, l'entropie, fixe les limites de tout programme de compression, de toute liaison réseau et de tout support de stockage, et il explique pourquoi certains textes se réduisent à une fraction de leur taille alors que d'autres ne se laissent pas compresser du tout.

Barres des probabilités des lettres, qui s'estompent des plus fréquentes aux plus rares, avec la courbe d'entropie qui descend à mesure que le contexte connu s'allonge
Barres des probabilités des lettres, qui s'estompent des plus fréquentes aux plus rares, avec la courbe d'entropie qui descend à mesure que le contexte connu s'allonge

L'information, c'est la surprise

L'idée de Shannon fut de mesurer l'information par le caractère inattendu d'un message, et non par ce qu'il signifie. Si vous connaissez déjà la réponse, l'entendre ne vous apprend rien ; si elle pouvait être une chose parmi mille, elle vous apprend beaucoup. Un message qui désigne une possibilité parmi deux également probables porte un bit. Une parmi quatre demande deux bits, une parmi huit trois bits, et en général une parmi N possibilités également probables demande log₂ N bits. Un symbole de probabilité p porte donc −log₂ p bits : plus il est rare, plus il en dit.

La formule de Shannon

L'entropie est l'information moyenne par symbole : H = −Σ p log₂ p, la somme portant sur tous les symboles, chacun avec sa probabilité p. Pour une pièce équilibrée, H vaut 1 bit. Pour une pièce qui tombe sur face 90 % du temps, elle ne vaut que 0,47 bit, car le résultat n'est généralement pas une surprise. L'entropie est maximale quand tous les symboles sont également probables, soit log₂ n bits pour n symboles, et nulle quand un symbole est certain. Shannon choisit ce nom sur le conseil de John von Neumann, car la même formule apparaît en physique, où l'entropie mesure le désordre.

Claude Shannon, qui en 1948, aux Bell Labs, précisa la quantité d’information contenue dans un message et la mesura en bits.
Claude Shannon, qui en 1948, aux Bell Labs, précisa la quantité d’information contenue dans un message et la mesura en bits.

La limite de la compression

Le théorème du codage de source de Shannon affirme qu'aucun code sans perte ne peut utiliser, en moyenne, moins de bits par symbole que l'entropie de la source, et que des codes peuvent s'en approcher autant qu'on le souhaite. Le codage de Huffman, inventé en 1952 par David Huffman alors qu'il était étudiant, attribue des codes courts aux symboles fréquents et des codes longs aux symboles rares, et s'approche de l'entropie à moins d'un bit par symbole ; le codage arithmétique s'en approche encore davantage. L'entropie n'est donc pas qu'une description, mais une limite infranchissable : un fichier d'octets aléatoires, avec 8 bits d'entropie par octet, ne peut pas être compressé du tout.

David Huffman, photographié lorsqu’il était professeur à l’université de Californie à Santa Cruz. Étudiant de troisième cycle au MIT en 1951, il trouva son code optimal dans un mémoire pour le cours de Robert Fano.
David Huffman, photographié lorsqu’il était professeur à l’université de Californie à Santa Cruz. Étudiant de troisième cycle au MIT en 1951, il trouva son code optimal dans un mémoire pour le cours de Robert Fano.

Contexte et redondance

Les lettres d'un texte ne sont pas indépendantes. En anglais, après Q vient U, après un point une majuscule, et un mot qui commence par INFORMA continue presque certainement par TION. Tenir compte des symboles précédents donne l'entropie conditionnelle, plus faible que l'entropie des symboles comptés un par un. La différence est la redondance : la partie du message qui aurait pu être prédite. Les programmes de compression comme ZIP, qui utilise la méthode deflate, repèrent les chaînes répétées et les remplacent par de courtes références, et les compresseurs modernes prédisent chaque symbole à partir de son contexte.

Combien d'information contient l'anglais ?

Comptée lettre par lettre, avec les fréquences de l'anglais, une lettre porte environ 4,1 bits, contre 4,7 pour des lettres tirées au hasard. En 1951, Shannon alla plus loin : il montra à des personnes le début d'un texte et leur demanda de deviner la lettre suivante, en comptant le nombre d'essais nécessaires. À partir de leurs réponses, il estima que l'anglais ne porte qu'environ 0,6 à 1,3 bit par lettre. Autrement dit, environ les trois quarts de l'anglais écrit sont de la redondance, et c'est pourquoi un texte auquel il manque des lettres reste généralement lisible.

Hasard et mots de passe

L'entropie mesure aussi l'imprévisibilité, dont dépend la sécurité. Une clé ou un mot de passe choisi uniformément parmi N possibilités a log₂ N bits d'entropie, et un attaquant doit en essayer en moyenne environ la moitié. Un mot de passe aléatoire de 12 lettres prises parmi les 26 minuscules a environ 56 bits ; un mot courant en a bien moins, quelle que soit sa longueur. On teste les générateurs de nombres aléatoires en vérifiant que leur sortie a l'entropie complète d'une source aléatoire, et les systèmes d'exploitation collectent de l'entropie à partir des fluctuations temporelles pour les initialiser.

Où l'on rencontre l'entropie

L'entropie détermine combien de bits il faut pour un appel téléphonique, une photo ou un flux vidéo, et à quel point un modem ou une liaison Wi-Fi peut approcher la capacité de son canal. Les biologistes l'utilisent pour mesurer l'information contenue dans l'ADN, où quatre bases peuvent porter au plus 2 bits chacune, ainsi que la diversité d'un écosystème. En apprentissage automatique, les arbres de décision choisissent la question qui réduit le plus l'entropie, et la perte d'entropie croisée sert à entraîner la plupart des réseaux de neurones. Les linguistes comparent les langues par leur entropie par caractère et par mot.

Explorez-la

Ouvrez le calculateur d'entropie pour mesurer n'importe quel texte par caractères, mots ou octets. Comparez un paragraphe avec des lettres, des bits, des chiffres et de l'ADN aléatoires, voyez la surprise de chaque symbole, la quantité d'information que contient le texte par rapport à sa taille stockée, et comment le nombre de bits par symbole baisse à mesure que le contexte connu s'allonge, à côté de ce qu'obtient réellement ZIP.

Questions fréquemment posées

Pourquoi l'entropie se mesure-t-elle en bits ?

Parce que Shannon utilisait des logarithmes en base 2, de sorte qu'un choix par oui ou par non entre deux options égales compte pour une unité. Avec le logarithme naturel, l'unité est le nat, environ 1,44 bit, et en base 10 le hartley, environ 3,32 bits ; les physiciens et certains statisticiens les utilisent.

Un texte peut-il avoir une entropie supérieure au log₂ de son alphabet ?

Non. Avec n symboles différents, l'entropie vaut au plus log₂ n bits par symbole, valeur atteinte seulement quand tous sont également fréquents. Tout déséquilibre, et toute prévisibilité due au contexte, la fait baisser.

L'entropie de la théorie de l'information est-elle la même que celle de la physique ?

Les formules ont la même forme : Boltzmann et Gibbs ont écrit l'entropie physique comme une somme sur les probabilités des états microscopiques d'un système. Le sens est apparenté, car les deux mesurent ce que l'on ignore, et les physiciens ont depuis montré qu'effacer un bit d'information doit libérer une petite quantité de chaleur.

Pourquoi compresser un fichier déjà compressé ne sert-il à rien ?

Un bon compresseur élimine l'essentiel de la redondance, si bien que sa sortie est proche de l'aléatoire, avec presque 8 bits d'entropie par octet. Il ne reste rien à éliminer, et le compresser à nouveau le rend généralement un peu plus gros à cause de la surcharge propre au compresseur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Ouvrir le calculateur d'entropie