Accueil  / Semaine 2 / Théorie de l’information

Théorie de l’information

Théorie de l’information de Shannon

Chercheur de génie, Claude Shannon a travaillé au célèbre laboratoire AT&T Bell. Il a considérablement influé sur la science et le génie moderne par son application des techniques de thermodynamique (étude de la chaleur, de l’ordre et du désordre dans les systèmes physiques) à la représentation des informations. Plus particulièrement, il est en grande partie responsable de l’omniprésence du concept de bits en information.

Claude Shannon (1916-2001)

Shannon a mis à jour les limites de la représentation des informations en bits, car il a vite constaté qu’il était possible de représenter un texte de plusieurs façons différentes en anglais par l’utilisation de bits. Par contre, certains types de représentation sont plus efficaces que d’autres. Le génie de Shannon a été d’établir le lien entre la probabilité d’occurrence d’un terme ou d’un caractère et la « quantité d’informations » qui lui est associée.

Exemple. J’ai un texte de 3 mots « A », « B » et « C ». Je choisis d’abord de représenter le premier mot sous la forme binaire « 00 », le second sous la forme « 10 » et le dernier sous la forme « 11 ». La séquence « ABCA » devient alors « 00101100 » ou « 00-10-11-00 ». Il a donc fallu 8 bits pour stocker les 4 mots, donc une moyenne de 2 bits par mot. Shannon savait qu’il était possible d’être encore plus efficace. En effet, il a représenté le premier mot avec un seul bit : « 0 ». La séquence « ABCA » devient alors « 010110 » ou « 0-10-11-0 », donc 6 bits pour stocker 8 mots, ce qui représentait un gain substantiel ! Shannon s’est alors demandé s’il était possible de faire mieux.

Si un mot x apparaît f(x) fois dans un texte de longueur n, la probabilité de tomber sur le mot x par hasard est de p(x)=f(x)/n. La quantité d’informations associée au mot x est de -\log p(x) [1]. Ainsi, si p(x) est très petit, la quantité est très grande, alors que si p(x) est très grand, elle est presque nulle. En français, cela signifie que le mot « le » apporte très peu d’informations car il est utilisé très fréquemment, alors que le mot « anticonstitutionnellement », qui est assez peu usité, contient beaucoup d’informations. La moyenne de la quantité d’informations dans les mots d’un texte s’exprime par -\sum_x p(x) \log p(x) et celle dans un texte se mesure ainsi : -n \sum_x p(x) \log p(x) . L’un des principaux résultats de la théorie de Shannon est qu’il faut toujours au moins -n \sum_x p(x) \log p(x) bits pour stocker l’ensemble d’un texte, et ce, malgré l’utilisation de techniques de compression [2] comme zip [3]. Shannon a aussi montré qu’il était possible de s’approcher très près de cette limite théorique de compression.

Exemple. Prenons un texte de 2 mots, l’un ayant une fréquence de 500 et l’autre, de 250, pour un total de 750 (n=750). Nous avons alors p(1)=500/750=2/3 et p(2)=250/750=1/3. La quantité d’informations du premier mot est de -\log_2 (2/3)\approx 0,58 et la quantité d’informations du second mot est de -\log_2 (1/3)\approx 1,58. Pour coder le texte, il faut donc au moins (-(2/3) \log_2 (2/3)-(1/3) \log_2 (1/3)) \times 750 \approx 688 bits, soit environ 86 octets. Vous pouvez tester ce résultat en générant un texte de seulement 2 mots qui comporte les fréquences prescrites. Vous constaterez que, quels que soient vos efforts de compression avec zip ou avec un autre outil, vous n’arriverez pas, sans tricher, à un fichier qui fait moins de 688 bits.

L’entropie de Shannon (-\sum_x p(x) \log p(x) ) est maximale à condition que nous choisissions les mots selon une distribution uniforme (p(x)=c, où c est une constante). L’entropie est minimale (=0) quand un seul choix est possible (p(x)=1 pour un certain x, et p(x’)=0 autrement). En d’autres termes, un texte généré plus aléatoirement est moins compressible.

En général, la quantité d’informations d’un texte ou de tout autre objet est souvent mesurée en fonction de son « incompressibilité ». En pratique, une technique fréquemment utilisée consiste à compresser un texte et à ne prendre que la taille du fichier compressé comme mesure de la quantité d’informations. Ainsi, les textes particulièrement verbeux et redondants se compressent particulièrement bien. Un concept similaire à celui de l’entropie de Shannon, la complexité de Kolmogorov, est défini comme la taille du plus petit programme pouvant le générer. On peut choisir le langage que l’on veut (p. ex. Java) pour définir la complexité pour autant qu’il soit toujours le même. Tout comme dans le cas de l’entropie de Shannon, la complexité de Kolmogorov est maximale dans le cas d’un texte généré aléatoirement avec des mots équiprobables.

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

Application pratique de l’entropie de Shannon

En moyenne, un roman volumineux contient à peu près 660 000 caractères. Étant donné que, selon l’estimation de Shannon, l’entropie des caractères en anglais est d’environ 1,3 bit par caractère, il faudrait donc environ un minimum de 100 ko pour stocker un roman sans perdre la moindre information. Il en faudrait environ 5 fois plus pour le stocker sans compression.

Avec 60 Go de données, on peut stocker plus d’un demi-million de livres, à condition qu’ils soient parfaitement bien compressés. En comparaison, la Bibliothèque nationale du Québec renferme environ 1 200 000 ouvrages.

Combien de personnes peuvent lire autant de livres dans leur vie ? Si elle lisait un roman par jour, il faudrait à une personne environ 1 500 ans pour passer au travers de ce que ce petit appareil portatif peut stocker. Notons que même sans compression, il est possible de stocker beaucoup de livres dans de petits appareils [4].

Entropie et stockage

Comme nous l’avons vu, la théorie de Shannon permet de mesurer l’entropie d’un texte et de toute information. Cette entropie est liée à l’entropie thermodynamique et, en particulier, à la seconde loi de la thermodynamique selon laquelle l’entropie ne peut qu’augmenter. Ainsi, si nous prenons un disque dont les « bits » sont placés aléatoirement (entropie maximale) et que nous y déposons un texte électronique (dont l’entropie est relativement faible), nous produisons forcément de la chaleur et consommons du courant électrique. La physique nous apprend qu’il est impossible qu’un système de stockage d’informations numériques ne produisent pas de chaleur. Stocker un fichier MP3 sur votre lecteur doit donc produire de la chaleur !

En conséquence, les unités de stockage consommeront toujours du courant et produiront toujours de la chaleur. Plus on tente d’organiser les informations, plus on tente de réduire l’entropie, plus il faut consommer de courant et produire de la chaleur. Heureusement, nous sommes loin, très loin, d’avoir atteint les limites théoriques d’efficacité et on produit maintenant des ordinateurs et des systèmes d’information qui sont relativement « froids ».

 M. P. Frank, Physical Limits of Computing, Computing in Science and Engineering, vol. 4 (3), May/June 2002, p. 16-25.

 R. Landauer, Irreversibility and Heat Generation in the Computing Process, IBM. Journal of Research and Development, vol. 5, no 3, 1961.

 C. H. Bennett, Logical reversibility of computation, IBM journal of Research and Development, 1973.

N-grammes et entropie d’une langue

Un n-gramme est une suite de n caractères (ou n mots selon le cas). Par exemple, « bi » ou « ci » sont des 2-grammes, appelés aussi des bigrammes. Nous pouvons trouver tous les n-grammes que contient un texte. Par exemple, le mot « Lavie » contient les trigrammes « Lav », « avi » et « vie ». De la même façon qu’il est possible de calculer l’entropie des caractères, on peut calculer l’entropie des n-grammes, qui est notée ainsi : H_n. Shannon a défini l’entropie d’une langue comme étant H=\lim_{n\rightarrow \infty} H_n. Il a estimé que, pour l’anglais, l’entropie était entre 0,6 et 1,3.

Entropie et informations

L’entropie est-elle une mesure juste de la quantité d’informations ? Peut-on même mesurer les informations ? D’ailleurs, que sont les informations ? Les informations équivalent-elles à la connaissance ?

Prenez le temps d’y réfléchir un peu ! Après tout, nous sommes dans un cours portant sur les informations.

Principe de l’entropie maximale

Supposons que vous ne connaissiez pas la probabilité de distribution d’une variable donnée. Comment calculeriez-vous la partie manquante en toute objectivité ? Vous pouvez appliquer le principe de l’entropie maximale : la distribution qui maximise l’entropie est le choix le plus neutre.

Compression Lempel-Ziv

Nous savons maintenant comment compresser du texte très efficacement et nous approcher de la limite de Shannon. Il existe toute une famille d’algorithmes de compression dont la compression Huffman [5], le codage arithmétique, etc. Pour une étude détaillée de tous les algorithmes de compression, voir The Data Compression Book par Mark Nelson et Jean-Loup Gailly. Un des algorithmes de compression de données les plus populaires est l’algorithme Lempel-Ziv dont nous résumons ici l’essence.

Soit une chaîne de caractères ; nous commençons au début de la chaîne, et chaque fois que nous rencontrons une séquence de caractères s jamais rencontrée auparavant, nous l’enregistrons dans un « dictionnaire ». Notons s=s_ +c où c est le dernier caractère de la chaîne s et s_ est le « préfixe » de s (tous les caractères sauf le dernier). Puisque s est une séquence jamais rencontrée auparavant et que nous arrêtons chaque fois qu’une telle séquence est trouvée, alors s_ doit être une séquence connue. Nous pouvons donc « coder » s efficacement comme étant la juxtaposition d’une chaîne connue (en référence à un « dictionnaire ») plus son dernier caractère. Plus notre dictionnaire devient important, plus nous pouvons compresser efficacement les données.

Il est difficile d’illustrer l’algorithme Lempel-Ziv avec de courts exemples parce que l’algorithme prend tout son sens sur de très longues séquences. Néanmoins, prenons un exemple, soit le mot (fictif) antianant. Initialement, notre dictionnaire de chaînes est vide. Nous rencontrons d’abord la chaîne « a », qui n’est pas connue, et l’ajoutons donc au dictionnaire. Ensuite, nous avons la chaîne « n » que nous ajoutons à notre dictionnaire. Puis, c’est la chaîne « t » que nous ajoutons encore une fois à notre dictionnaire. Arrive alors la chaîne « i », que nous ajoutons encore à notre dictionnaire. Nous avons alors le dictionnaire suivant :

 1 : a

 2 : n

 3 : t

 4 : i

La prochaine chaîne inconnue est « an » (puisque « a » est déjà dans le dictionnaire). Nous ajoutons donc au dictionnaire :

 1 : a

 2 : n

 3 : t

 4 : i

 5 : an

Ensuite, la prochaine chaîne inconnue est « ant », que nous ajoutons encore une fois au dictionnaire :

 1 : a

 2 : n

 3 : t

 4 : i

 5 : an

 6 : ant

Si nous utilisons les paires « préfixe » et « dernier caractère », notre mot prendra la forme suivante :

(-,a), (-,n), (-,t), (-,i), (1,n),(5,t)

où « - » signifie qu’il n’y a pas de préfixe.

 J. Ziv et A. Lempel, Compression of individual sequences by variable rate coding. IEEE Transactions on Information Theory, 1978, vol. 24(5), p. 530-536.

Codage de Huffman (Matériel optionnel)

Le codage de Huffman est une autre technique de compression très utilisée. Nous vous invitons à consulter l’article chez wikipédia pour en savoir davantage.

 D.A. Huffman, A method for the construction of minimum-redundancy codes, Proceedings of the I.R.E., September 1952, p. 1098-1102.


La transformation de Burrows-Wheeler (BWT) (Matériel optionnel)

Nous obtenons de très bons résultats avec des techniques de compression fondées sur la transformation de Burrows-Wheeler. L’outil bzip2 emploie une telle technique et compresse plus efficacement que la plupart des outils d’usage courant. Bien qu’il soit très rapide, l’outil bzip2 n’est environ que 15 % moins efficace que des techniques beaucoup plus lourdes, telles que la compression par Prediction by Partial Matching (PPM).


Généralisation de Rényi (Matériel optionnel)

L’entropie de Shannon a été généralisée par Rényi avec la formule \frac{1}{1-\alpha} \log \sum_x p(x)^\alpha  ; l’entropie quadratique de Rényi est souvent exprimée ainsi : - \log \sum_x p(x)^2.

Généralisation de Markov (Matériel optionnel)

L’entropie de Shannon est parfois appelée « entropie de Markov de premier ordre ». Une généralisation du concept d’entropie s’applique aux processus de Markov. Nous verrons brièvement les processus de Markov dans le cadre de notre étude de l’algorithme PageRank. La généralisation est très naturelle et sert à calculer des limites de compression encore plus élevées, lesquelles sont utiles pour les chercheurs travaillant sur des algorithmes de compression de données.

Notes amusantes et utiles pour investir à la Bourse (Matériel optionnel)

Shannon aimait beaucoup s’amuser à jongler et à faire de l’unicycle. Par ailleurs, avec John Kelly et Ed Thorp, il a misé d’importantes sommes à Las Vegas et a remporté beaucoup d’argent. On dit aussi qu’il a fait encore plus d’argent en jouant à la Bourse. Son succès s’expliquerait par l’utilisation de la « formule de Kelly » qui est inspirée de ses travaux sur l’entropie et la théorie de l’information [6].

Supposons que vous jouez à pile ou face contre un adversaire et que vous avez l’avantage d’avoir une pièce de monnaie truquée et que vos chances de gagner sont de 6 sur 10. À chaque lancer, si vous pariez 10 dollars, vous gagnez 10 dollars en cas de victoire, et vous les perdez en cas de défaite.

Quelle est la meilleure stratégie ? Si vous pariez, chaque fois, la totalité de votre fortune, vous finirez par tout perdre. Si vous ne pariez rien, vous resterez avec votre magot actuel sans jamais ne rien gagner.

Le génie de Kelly et de Shannon a été de chercher à savoir quelle fraction de votre fortune, à chaque lancer, vous deviez miser. Si votre probabilité de gagner est de p et que votre probabilité de perdre est de q, votre fortune sera alors multipliée par (1+x)^p (1-x)^q (en moyenne) à chaque lancer où x est la fraction de l’avoir que vous misez. Vous maximisez vos chances de gagner à long terme lorsque x= 2p -1.

Cette règle s’applique autant aux investissements boursiers qu’aux jeux de hasard. Malheureusement, il est difficile, voire impossible, de calculer p avec précision pour un investissement à la Bourse. Le cas échéant, la formule de Kelly vous donnerait votre stratégie d’investissement optimal.

Référence : John Kelly, A New Interpretation of Information Rate.


[1En informatique, le logarithme est toujours en base 2. Si votre calculatrice n’a que la base e, vous pouvez utiliser la formule $\log_2 (x)= \log_e(x)/\log_e(2)$.

[2Dans le cadre du présent cours, le terme compression ne renvoie qu’à la « compression sans perte », où il est toujours possible de reproduire les données d’origine à partir des données compressées. Les méthodes de compression utilisées par les normes MP3, MPEG, JPEG, etc., sont donc exclues.

[3En fait, c’est le minimum de bits nécessaires au stockage d’un texte quand on utilise un code où chaque mot correspond à une séquence de bits unique. Les outils de compression peuvent faire appel à des techniques plus sophistiquées où la séquence de bits utilisée pour représenter un mot dépendra des mots précédemment rencontrés dans le texte. Il faudrait dans ce cas précis utiliser une généralisation du résultat de Shannon.

[4D’un autre côté, nombre de livres ne contiennent pas que du texte et ne sont donc pas toujours disponibles sous une forme numérique.

[5D.A. Huffman, A method for the construction of minimum-redundancy codes, Proceedings of the I.R.E., Sept. 1952, p. 1098-1102.

[6Voir le livre Fortune’s Formula, par William Poundstone, paru chez Hill and Wang en 2005, 400 p.