Information et entropie

L'analyse quantitative de l'information est due à Shannon  (1948). Il définit, dans un cadre probabiliste, une notion d'entropie, terme dû à Clausius (1864), qui a des interprétations diverses en informatique, en thermodynamique et en probabilités, pourtant toutes liées par des intuitions communes.

Considérons une partition $\mathcal{E} = (E_1, \ldots, E_n)$ d'un espace de probabilités $(\Omega, \mathcal{A}, \mathbf{P})$ en un ensemble d'événements : $\Omega = \bigcup_{i=1}^{n} E_i$, avec $E_i\cap E_j= \emptyset$ si $i\neq j$. En posant p_i=P(E_i), et en utilisant le logarithme en base 2 (par convention, $0\log 0 = 0$), l'entropie de $\mathcal{E}$ est définie par :

$$\mathbf{H}(\mathcal{E}) = - \sum_{1=1}^{n} p_i \log p_i$$

Dans les applications au codage, $\Omega$ est l'alphabet source, et chaque événement est un symbole de l'alphabet. Les probabilités p_is'obtiennent généralement par la mesure de la fréquence des symboles dans des textes usuels.

L'entropie mesure l'information par l'incertitude qu'elle permet de lever : incertitude avant, information après la réception d'un message identifiant l'un des événements de $\mathcal{E}$. Elle est ainsi maximale quand tous les événements sont équiprobables, c'est-à-dire p_i = 1/n : $\mathbf{H}(\mathcal{E}) = \log n$. On retrouve ainsi le nombre de bits nécessaires pour coder un élément d'un ensemble de cardinal n, en l'absence d'hypothèse probabiliste. Par exemple, pour les 26 lettres de l'alphabet, il faut au moins $\log 26 = 4,7$ bits (on doit donc en utiliser 5). L'entropie est minimale, et nulle, quand un des événements est de probabilité 1 : il n'y a aucune incertitude, et il est inutile de coder des événements de probabilité nulle. Un message codé sur zéro bit suffit à porter une information sûre !

Dans les cas intermédiaires, entre 0 et $\log n$, le rapport $\tau = \mathbf{H}(\mathcal{E}) / \log n$ mesure le taux de compression idéal que l'on obtiendrait en ne codant que les messages << les plus fréquents >>, et $1-\tau$ mesure la redondance intrinsèque, en terme d'information, d'un code représentant tous les messages possibles. Cette redondance est utile car elle permet de décrypter des messages chiffrés alors que la clé de déchiffrement est inconnue, et de façon plus courante, de corriger des fautes d'orthographe. La compression de données, requise pour réduire le coût des supports de stockage et de transmission de l'information, cherche au contraire à diminuer cette redondance.

On peut montrer que la longueur moyenne minimale, L, d'un codage binaire de l'alphabet source vérifie :

$$\mathbf{H}(\mathcal{E})\le L < \mathbf{H}(\mathcal{E}) + 1$$

La longueur moyenne d'un code de Huffman peut approcher d'aussi près que voulu la longueur moyenne minimale, à condition de coder non pas des lettres individuellement, mais des blocs de lettres de longueur assez grande. On peut aussi montrer que $\mathbf{H}(\mathcal{E})$ mesure le nombre moyen de questions binaires qu'il suffit de poser pour identifier l'un des événements de $\mathcal{E}$.