Codage , entropie et mots typique

Cf. source (i)

De nos jours, les informations sont constamment échangées ou stockées que ce soit entre deux ou plusieurs personnes, d'une personne à une machine ou d'une machine à une autre machine. Mais pour pouvoir s'assurer que ces informations soient bien reçues, il existe un long processus permettant cela dont notamment l'entropie. Ce processus consiste à mesurer la quantité d'information pour pouvoir la compresser adéquatement et sans erreur. Dans cet article, nous développerons une partie de ce processus en nous intéressant à l'entropie de manière générale et les différents types de codages utilisant l'entropie.

1 . Qu'est-ce que l'entropie pour une source aléatoire ?

  • Un peu d’histoire
Rudolf Clausius

Le terme entropie a été introduit en 1865 par Rudolf Clausius, un physicien allemand, à partir d'un mot grec signifiant « transformation ». Il caractérise le degré de désorganisation, ou de imprédictibilité du contenu en information d'un système.

(image : Cf. source (j))

Cela étant l’entropie existe dans plusieurs domaines, et nous nous intéresserons à l’entropie en informatique : L'entropie de Shannon, due à Claude Shannon, un ingénieur en génie électrique et mathématicien américain.

  • L’entropie de Shannon
Claude Shannon

L’entropie de Shannon est une fonction mathématique qui, intuitivement, correspond à la quantité d'information contenue ou délivrée par une source d'information. Cette source peut être un texte écrit dans une langue donnée.

(Cf. source (k))

  • Exemples d’application

Un exemple de source de symboles est l’ensemble des lettres dans un texte pour lesquels on connaît la fréquence avec laquelle apparaît chaque lettre (Cf tableau partie 5 ). Un autre exemple serait un code source en binaire , soit une suite de 0 et de 1. 

Plus l’entropie est grande, plus il faudra de bits par symbole, en moyenne, pour encoder la source. Une source qui émet presque toujours le même symbole ne porte pas beaucoup d’information : son entropie est proche de 0, alors que si un symbole est choisi aléatoirement parmi 16 mots, son entropie peut aller jusqu’à 4 bits d’information. 

  • L'entropie pour une source aléatoire

Une source est une donnée d'un ensemble fini appelé alphabet A et d'une densité de probabilité, c'est-à-dire d'une application p : A -> [0,1] satisfaisant

(1)   \begin{equation*}  \sum_{s}{p(s) = 1} \end{equation*}

Avec s appartenant à l'alphabet A. Les éléments de A sont appelés les symboles. (Cf source (h))

Prenons par exemple une pièce de monnaie , la source aura un alphabet composé de deux éléments : pile et face. Donc A = {"Pile","Face"}. Or la probabilité est la même pour les deux faces , on a donc : p("Pile") = p("Face") = 0,5. Puis lorsque l'on additionne ces probabilités on obtient 1.

  • Définition de l'entropie pour une source

Soit S = (A, p) une source, avec A un alphabet et p une probabilité. L'entropie de S est

(2)   \begin{equation*} H(S) = - \sum_{s }{p(s)log_{2}(p(s))} \end{equation*}

Avec s appartenant à l'alphabet A.

Si p(s) = 0 pour un certain s, on remplace par convention le terme  p(s)log_{2}(p(s)) de la somme par 0.

  • Utilisation générale

Plus généralement, l’entropie est une notion centrale en compression car elle quantifie précisément le nombre moyen de bits nécessaires pour transmettre un mot provenant d’une source. L’algorithme de Huffman est un exemple d’algorithme dont le taux de compression est exactement l’entropie de la source dont il code les mots.

2 . Calcul d'entropie des lettres

Le calcul d'entropie des lettres varie selon la langue et selon les caractères spéciaux que l'on souhaite ajouté.

  • Entropie dans la langue française

Par exemple pour la langue française, en ajoutant les caractères spéciaux on obtient environ 115 caractères au total.

  • Entropie dans la langue anglaise

Pour la langue anglaise, le nombre de caractères utilisés est moins important que celui de la langue française, donc le nombre de bits pour une donnée est moins important.

Pour tester ces fonctions, il faut donc le code suivant :

  • Le calcul de l'entropie de façon générale

Pour calculer l'entropie de n'importe quelle langue il suffit de savoir combien de caractères seront nécessaires puis la longueur du texte duquel on souhaite calculé l'entropie.

Le calcul de l'entropie dans la vie courante est notamment utilisé pour connaitre la robustesse d'un mot de passe lorsque l'on souhaite créer un compte ou autre.

3. Courbe de l'entropie des sources binaires

L'entropie d'une source binaire, c'est-à-dire une source qui émet seulement deux symboles, par exemple 0 et 1, avec les probabilités k et (1-k) vaut :

H(k) = -k log_{2}(k) - (1-k) log_{2}(1-k)

La courbe suivante schématise l'entropie d'une source binaire :

Courbe de l'entropie d'une source binaire
(Cf. source (c))

On remarque que lorsque k = 0,5 , l'entropie atteint son maximum, cela signifie que les deux symboles sont équiprobables , c'est-à-dire qu'ils ont la même probabilité d'être émis.

Nous allons maintenant abordé les différents codages pour l'entropie en commençant par le codage de Huffman.

4. Le code de Huffman et ses limitations

  • Les limitations

Le codage de Huffman impose d’utiliser un nombre entier de bits pour un symbole source en utilisant le codage Huffman sur des blocs de n symboles.  On peut alors s’approcher de façon plus fine de l’entropie.  Le codage de Huffman évalue les probabilités des symboles au début, donc il n’est pas adapté dans le cas d’une source dont les propriétés statistiques évoluent.

  • Code de Huffman

Le code de Huffman consiste à construire progressivement un arbre binaire à code préfixe (Cf exemple).

On part d'une source sans mémoire, produisant N symboles  a_{0}, a_{1}, . . . , a_{N-1} selon la distribution de probabilité  p = ( p_{0}, p_{1}, . . . , p_{N-1} ).

On prend les deux symboles les moins probables puis on les relient à l'arbre en les étiquetant par 0 et 1. On répète cette étape jusqu'à obtenir un seul arbre.

Il y a N^n mots de longueur n sur un alphabet à N symboles.

Soit C un code de Huffman associé aux mots de longueur n, et soit  l'_{i} la longueur moyenne des mots codés par symbole initial. Alors :

 H(p) \le l'_{i} < H(p) + \frac{1}{n}

(Cf. source (d))

Un exemple de son utilisation sur le mot "ILYESSSAMYLAMIA":

Il existe de nombreux types de codages hormis celui de Huffman et qui sont adaptés pour différents types de sources.

5. Entropie et codages

Un élément d’un ensemble de taille 2^n peut être codé par n unités d’information. C’est le premier lien entre théorie de l’information et codage.

  • Codage sans bruit ( premier théorème de Shannon )

Le théorème montre que l'on ne peut pas compresser une chaîne de variables aléatoires indépendantes et identiquement distribuées, quand la longueur de celle-ci tend vers l'infini, de telle sorte à ce que la longueur moyenne des codes des variables soit inférieure à l'entropie de la variable source. Cependant, on peut avoir une compression avec une longueur moyenne de code arbitrairement proche de l'entropie lorsque la longueur de la chaîne tend vers l'infini.

  • Définition

Un codage sur un alphabet 𝐴 est une application injective de 𝐴 vers l’ensemble des mots sur un alphabet 𝐵 (souvent 𝐵 = {0, 1}). On dit que le codage est instantanément décodable s’il n’existe pas deux lettres 𝑎, 𝑎′ de 𝐴 telles que le code de 𝑎 soit un préfixe du code de 𝑎′.

On étend le codage aux mots sur 𝐴 par concaténation des codes des lettres. La propriété d’être instantanément décodable garantit alors que le codage des mots est non ambigu.

Le problème est le plus souvent de trouver les codages les plus courts possibles. La stratégie de base consiste à attribuer des codes courts aux lettres fréquentes, et des codes longs aux lettres moins fréquentes.

  On a le théorème de codage de Shannon, qui identifie entropie et taux de compression maximal :

Soit 𝐶 un codage instantanément décodable pour la suite de variables  X_{1}, . . . , X_{n},...  , L(C) la longueur moyenne du codage et S (X_{1},...,X_{n},... ) le codage sans bruit de Shannon appliqué à la suite de variables, alors :

(3)   \begin{equation*} L(C) >= \frac{S(X_{1}, . . . , X_{n}, ...)}{log |B|} \end{equation*}

De plus, on peut construire des codages ayant des longueurs arbitrairement proches de cette valeur.

La preuve qu’aucun code ne fait mieux que cette valeur est simple : c’est essentiellement le fait que si ∑︀p_{i} =∑︀ q_{i} = 1, alors ∑︀ p_{i} log q_{i} est maximal quand  p_{i} = q_{i}, et la remarque que si les l_{i} sont les longueurs des codes d’un codage instantanément déchiffrable, on a ∑︀ 2^{-l_{i}} <= 1.

  • Optimisation : Mots typiques et mots rares

Pour que le code soit le meilleur possible, les mots de longueur n obtenus par tirage des variable X_{i} peuvent être décomposés en deux classes, une classe de mots « typiques » et une classe de mots « rares ».

Les mots typiques sont environ au nombre de 2^{nS} , chacun d’entre eux étant de probabilité environ 2^{-nS} ; les mots rares ont une probabilité totale négligeable.

Pour coder dans {0, 1} un mot typique, on met un « 0 » suivi du code en base 2 du numéro du mot typique parmi les 2^{nS} mots typiques (ce qui prend nS chiffres en base 2) ; pour un mot rare, on met un « 1 » suivi simplement du code en base 2 du numéro du mot rare parmi l’ensemble des mots possibles sur l’alphabet de départ.

Les mots typiques sont les mots que nous utilisons le plus souvent au quotidien, par exemple le mot "bonjour" est un mot typique, mais un mot peut être composé que d'un seul caractère dans ce cas le mot "a" est un mot typique et parmi les mots rares on a pour exemple "xylophone" ou le mot "w".

Voici un exemple de l'application du codage sans bruit de Shannon
  • Fréquence des lettres dans la langue française

Voici le tableau des lettres de l’alphabet français, leur fréquence et leur taille en fonction de leur utilisation comme expliqué juste avant :

(Cf. source (h))
  • Codage avec bruit

Le codage avec bruit  est utilisé avec des canaux de communication qui peuvent introduire des erreurs dues à des perturbation atmosphériques, au média de transmission ou à l’émetteur de transmission. 

Soit X le message à la source, Z le message codé transmis dans un canal (qui est une fonction aléatoire de X). Soit 𝜙 une fonction de décodage, on veut que 𝜙(Z) = X le plus souvent possible, mais le passage de X vers Z n’est pas forcément injectif.

Par exemple, si l'on souhaite envoyer un texto à quelqu'un , ici le message X est le message que l'on envoie, Z est ce même message mais codé pour pouvoir être transmis via le ou les réseaux. Il n'existe pas une unique façon de codé un message . Avant la réception du message, la fonction 𝜙 va retraduire le message pour qu'il soit le même que X. Mais il se peut que le message ne soit pas bien reçu ou pas du tout reçu à cause des bruits , qui peuvent être dans cet exemple le changement de réseaux à plusieurs reprises.

  • Codage continu

Dans le cas où l’on cherche à transmettre une quantité continue (intensité, voltage...). On a des lois de probabilité sur R. Par analogie avec le cas discret, l’entropie d’une distribution de probabilité f sur R est égale à - ∫  ︀_{x e R}  f(x)  log  f(x)  dx.

(Cf. source (g))

Pour conclure l’entropie n’est qu’une des étapes nécessaire pour crypter n’importe quel type de données. Elle permet de mesurer une information donnée pour pouvoir la compressée dans la prochaine étape. Après la compression de cette information, il est nécessaire de sécuriser cette information compressée et d’éviter qu’il y ait des erreurs lors d’une recopie. Comment sécurisé cette information compressée ? Et comment éviter les erreurs pour une recopie ?  La cryptographie et les codes correcteurs sont la réponse à cette question.

Entropie

Départ
Félicitation - vous avez complété Entropie. Vous avez obtenu %%SCORE%% sur %%TOTAL%%. Votre performance a été évaluée à %%RATING%%
Vos réponses sont surlignées ci-dessous.
Retour
Les questions en gris sont complétées.
1234Fin
Retour
Source :
14 Cliquer pour recommander cet article