L'entropie de Shannon

Qu'est-ce qu'un bit d'information ?

En 1948, Claude Shannon donne une définition mathématique de l'information. Son idée : l'information contenue dans un message se mesure par la surprise qu'il provoque. Un événement certain n'apporte aucune information ; un événement rare en apporte beaucoup. L'unité est le bit : c'est la quantité d'information d'un choix entre deux possibilités également probables (pile ou face).

De la probabilité à l'information

Un message d'autant plus probable est d'autant moins informatif. La quantité d'information d'un événement de probabilité p vaut log2(1/p) bits. Un événement de probabilité 1/2 apporte 1 bit ; un de probabilité 1/8 en apporte 3.

probabilite p      information = log2(1/p)
1     (certain)    0 bit     (aucune surprise)
1/2                1 bit
1/4                2 bits
1/8                3 bits    (plus c'est rare, plus c'est informatif)

L'entropie : l'information moyenne d'une source

L'entropie H d'une source est la quantité moyenne d'information par symbole qu'elle émet. Pour une source qui émet des symboles avec des probabilités p1, p2..., on additionne, pour chaque symbole, sa probabilité multipliée par son information. L'entropie se mesure en bits par symbole.

Une source qui émet toujours la même lettre a une entropie de 0 (aucune surprise). Une source qui émet 4 lettres équiprobables a une entropie de 2 bits par lettre. L'entropie est maximale quand tous les symboles sont également probables.

La limite de la compression

Le résultat central de Shannon : on ne peut pas coder une source avec moins de bits par symbole que son entropie, sans perdre d'information. L'entropie fixe donc la limite absolue de la compression sans perte. Aucun algorithme, aussi malin soit-il, ne peut la franchir.

Piège classique

Un fichier déjà bien compressé a une entropie proche du maximum : ses bits ressemblent à du hasard, il n'y a plus de redondance à exploiter. Chercher à le recompresser ne gagne rien, et peut même l'agrandir légèrement (à cause des en-têtes ajoutés). Croire qu'on peut compresser indéfiniment est l'illusion que l'entropie interdit.