Combien de textes d’une longueur donnée peut-on écrire? La réponse à cette question permet d’explorer les fondations de la théorie de l’information et de définir la notion d’entropie pour une langue!

Commençons par un exemple simple. Considérons comme «texte» un programme informatique et encodons-le comme une suite de 0 et de 1, en tout N chiffres. Imaginons un cas idéalisé où toutes les suites possibles de N 0 et 1 auraient un «sens» informatique. Dans ce cas, le nombre de «textes» qu’on peut écrire est directement calculable et égal à 2 à la puissance N. Le logarithme de ce nombre est plus intéressant, car il est ici égal à N log 2, et donc en particulier proportionnel au nombre de caractères —ce qui veut dire que le nombre de textes possibles lui-même est littéralement exponentiel en sa longueur.

Claude Shannon, dans ses articles fondateurs de la théorie de l’information, proposa d’exprimer la quantité moyenne d’incertitude contenue dans un texte en divisant le logarithme du nombre de messages possibles de longueur N par cette quantité de référence que nous venons de calculer, N log 2. Pourquoi incertitude? Car a priori, avant de le lire, on ne connaît pas le contenu d’un texte! Au contraire, à chaque caractère lu, on réduit l’incertitude sur le texte, donc on parlera parfois de gain d’information, ou encore, par abus de langage, d’information moyenne par caractère.

Reprenant notre exemple précédent: la quantité moyenne d’incertitude dans notre programme informatique idéalisé est donc 1, une unité d’information. Shannon inventa un terme pour désigner cette unité: le bit. Intuitivement, dans l’exemple ci-dessus, le bit est donc une notion fondamentalement probabiliste: chaque caractère du message est une alternative entre 2 possibilités équiprobables, 0 et 1. Le bit est une mesure de l’incertitude sur le choix de ce caractère ou, de façon similaire, de la quantité d’information apportée par la connaissance d’un caractère.

Avec cet exemple en tête, considérons maintenant un texte d’un vrai langage, et estimons la quantité d’incertitude/information apportée par un nouveau caractère. Shannon étant anglophone, il réalisa cette étude sur l’anglais.

Un premier modèle «naïf» est de considérer, comme dans l’exemple ci-dessus, un texte comme une liste aléatoire de lettres. Si l’on néglige la ponctuation et les espaces, le nombre de caractères possibles est alors 26. Le nombre de textes est alors pour la même raison 26^N. Un exemple typique serait:

XFOML RXKHRJFFJUJ ZLPWCFWKCYJ FFJEYVKCQSGHYD QPAAMKBZAACIBZL HJQD.

On prend le log et on divise par N log 2, et l’on trouve le logarithme de 26 en base 2, qui est égal à 4.7 bits. Cela signifie qu’en moyenne chaque caractère apporte 4.7 unités d’information. Puisque 1 bit correspond à un choix binaire entre 0 et 1, une autre façon de dire cela est que chaque caractère dans notre message correspond en moyenne à 4.7 choix binaires. Une autre façon encore de dire cela est que si vous voulez encodez 26 caractères avec des nombres binaires, il vous faudra bien au minimum (et en arrondissant à un entier), 5 chiffres entre 0 et 1.

Là où les choses deviennent plus subtiles est qu’évidemment la phrase ci-dessus ne ressemble à rien à de l’anglais. Shannon a affiné son modèle en ajoutant des structures statistiques du langage. On peut d’abord construire des phrases dont les caractères ont la même fréquence qu’en anglais, par exemple:

OCRO HLI RGWR NMIELWIS EU LL NBNESEBYA TH EEI ALHENHTTPA OOBTTVA NAH BRL.

On peut alors calculer que la moyenne baisse à 4.1 bits. Mais ça ne ressemble toujours pas tellement à de l’anglais. Ajoutons encore de la structure: à la place de considérer les «lettres» comme caractères élémentaires de phrases, considérons les mots, et construisons des phrases en utilisant aléatoirement des mots selon leur fréquence dans le langage, par exemple:

REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NATURAL HERE HE THE A IN CAME THE TO OF TO EXPERT GRAY COME TO FURNISHES THE LINE MESSAGE HAD BE THESE.

C’est un peu mieux; l’information moyenne par mot est alors de 11 bits, et si on calcule l’information par caractère, on descend, encore une fois, à 2.62 bits.

Pourquoi cette quantité d’incertitude baisse à mesure qu’on s’approche du langage réel? La raison est qu’une langue n’est pas une suite de caractères aléatoires: les caractères d’un texte sont hautement corrélés, hautement structurés. Vous pouvez reconnaître et reconstruire cette structure sans même réfléchir. Pr ex vs pvz cmprndr ctt phrs. Ou ecnroe l'odrre des ltteers dnas un mot n'a pas tnat d’ipmrotncae.

Il y a en fait ce qu’on appelle de la redondance, qui fait que la quantité d’information moyenne apportée par une lettre est bien moins importante que si l’on considérait les lettres de façon indépendante. Donc, en moyenne, connaître une nouvelle lettre en apporte moins d’information que si chaque élément était purement aléatoire.

Shannon a mis au point un petit jeu diabolique pour mettre ce phénomène en évidence et mesurer la quantité «réelle» d’information par lettre. Prenez une phrase au hasard dans un livre, demandez à un interlocuteur de deviner successivement les lettres de la phrase, en lui donnant la réponse après chaque lettre. La première lettre est inconnue, mais a peu de chances d’être q ou z (en anglais). Mais une fois que vous connaissez la première lettre, vous pouvez souvent deviner de façon robuste la seconde lettre. Par exemple, une phrase en français qui commence par q aura nécessairement un u comme deuxième caractère; une phrase anglaise commençant par w a toutes les chances d’être une question et d’avoir un h comme deuxième caractère, etc. À cause des règles d’accord, de grammaire, de toutes ces structures donnant de la redondance à la langue, il est possible de deviner plus de 70% des lettres. Cela signifie que 70% de l’information moyenne par caractère est redondante (et «inutile»). Donc la quantité réelle d’information par caractère est, en moyenne, de l’ordre de 30% de la quantité d’information s’ils étaient indépendants, de l’ordre de 1.3 bit après calcul de Shannon. On n’est plus très loin du choix binaire par caractère en moyenne!

Ces considérations amusantes peuvent être bien sûr davantage formalisées mathématiquement, et ont donné naissance à ce qu’on appelle la théorie de l’information, appliquée aujourd’hui à énormément de domaines. Un exemple biophysique: les gènes dans les cellules vont se réguler les uns les autres, transmettant de l’information biochimique. Cette information peut être quantifiée dans certains cas, en utilisant des techniques similaires à ce qu’a fait Shannon sur l’anglais. On peut alors étudier comment cette information est transmise ou dégradée d’une cellule à l’autre, comment elle est dans certains cas optimisée, ce qui est très éclairant sur les contraintes biophysiques et biochimiques des communications cellulaires. On en reparlera.

Quelques références:

A Mathematical Theory of Communication, Claude E. Shannon, 1948.

• «Prediction and entropy of printed English», Claude E. Shannon - Bell system technical journal, 1951.

The information, James Gleick. Introduction historique à toutes ces idées, très vulgarisée.

• Il y a évidemment un XKCD sur le sujet.

• Il y a toujours des débats pour savoir si l’on doit parler d’incertitude ou d’information. Cette page donne la bonne réponse: l’information est l’incertitude qui disparaît lorsqu’on reçoit un message.