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=\mathbf{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 une lettre de l'alphabet. Les probabilités p_i s'obtiennent généralement par la mesure de la fréquence des lettres 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'une 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 en utilise 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.

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$$

Nous verrons comment approcher cette longueur minimale à l'aide du codage de Huffman. 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}$.