Poursuivons notre introduction à la compression données. Dans ce billet-ci, nous examinerons la mesure de l'information contenue dans un message, telle que proposée en 1928 par l'Américain Hartley.

Précédemment...

Dans le billet précédent, nous avons vu comment Alfred Vail a résolu le problème de la transmission efficace de messages par télégraphe. Plutôt que d'utiliser un nombre fixe de signaux élémentaires (dans le cas du télégraphe, les signaux élémentaires sont le point, le tiret et l'espace) pour tous les symboles du message, Vail a proposé d'utiliser un code où chaque symbole du message peut être représenté par un code de longueur variable. Ce que Vail propose, c'est de donner aux symboles les plus fréquents un code court, composé de peu de signaux élémentaires, et de donner aux symboles moins fréquents des codes plus longs — plus exactement, les codes les plus courts qui n'ont pas servi.

De la nature de l'information

Pour Vail, le message lui-même n'est qu'une suite de symboles qu'il faut transmettre de la façon la plus rapide et la plus pratique possible, et pour lui, grâce à son astucieux code, le problème est essentiellement résolu. Vail ne semble pas se poser de questions quant à la nature du message.

En fait, il semble qu'il faille attendre la fin des années 1920 pour qu'on propose une définition plus formelle — c'est-à-dire mathématique — de l'information. Dans son article de 1928, Ralph Vinton Lyon Hartley (1888–1970) remarque, en entrée de jeu et avec un certain agacement, que le terme « information » est bien élastique et qu'il est nécessaire de s'y attarder et de lui donner une définition bien rigoureuse.

Mesurer l'information

Hartley part de la supposition que pour composer un message, il faut d'abord avoir un alphabet dans lequel le composer. Pour Hartley, cet alphabet doit comporter un nombre fini s de symboles. Un message comportant n symboles tirés d'un alphabet de taille s n'est donc qu'un parmi les sⁿ messages possibles. Hartley a l'intuition que la quantité d'information intrinsèque au message ne devrait pas être proportionnelle au nombre de messages distincts de même longueur, mais seulement proportionnelle à sa longueur fois une quantité qui ne dépend que du nombre de symboles de l'alphabet. Autrement dit, la quantité d'information H d'un message de longueur n est de la forme H = k × n où la constante k est à déterminer. Mais comment déterminer cette constante?

Comment obtenir une fonction de la forme désirée, soit H = k × n, à partir de sⁿ ? Hartley propose d'utiliser le logarithme et de calculer

H = log(sⁿ) = n log s,

trouvant ainsi que k = log s.

(Dans son article de 1928, Hartley ne s'intéresse pas spécialement à la base du logarithme car il ne s'agit que d'une constante multiplicative qui ne change rien aux relations et aux déductions. Plus tard, on dira que si le logarithme est en base 2, on mesure l'information en bits, que si la base est la base e, c'est-à-dire la base des logarithmes naturels, on mesure l'information en nats, et qu'enfin si la base du logarithme est la base 10, on mesure l'information en ... hartleys.)

Un résultat contre-intuitif

La formule proposée par Hartley est cohérente mathématiquement, mais demeure « naïve » dans la mesure où elle donne une importance égale à tous les messages de même longueur (et composés dans le même alphabet). En effet, selon la formule proposée par Hartley, tous les symboles du message contiennent la même quantité d'information puisqu'ils sont tous multipliés par la même constante k = log s. La conséquence de cette observation est que puisque tous les symboles contiennent la même quantité d'information, il n'y a pas de distinction entre les symboles fréquents et les symboles moins fréquents. La mesure de Hartley nie donc qu'il y ait des symboles (et donc ultimement des messages) plus fréquents que d'autres.

La formule de Hartley contredit donc l'intuition de Vail pour qui les symboles fréquents devraient recevoir des codes plus courts. D'une part, la formule de Hartley dicte que tous les symboles doivent contenir la même quantité d'information, d'autre part, Vail nous dit que les symboles fréquents devraient recevoir des codes plus courts que les symboles moins fréquents. Or, un code plus court contient moins d'information qu'un code plus long, donc un symbole représenté par un code plus court contient moins d'information qu'un symbole représenté par un code plus long... C'est donc que les symboles les plus fréquents contiennent moins d'information que les symboles moins fréquents!

À suivre...

Comment concilier la formule de Hartley, l'intuition de Vail, et ce curieux résultat qui semble indiquer que les symboles les plus fréquents seraient en fait ceux qui contiennent le moins d'information? Nous découvrirons la réponse au prochain épisode!