Travaux Pratiques
du cours de Théorie de l' Information

APPROXIMATION D'UN LANGAGE

Définition et objectif. 
Faire l'analyse à l'ordre L d'un texte c'est déterminer les fréquences des mots de longueurs L, les L-uplets, qui composent ce texte. Il s'agit de prendre en compte tous les mots obtenus en faisant glisser une fenêtre de longueur L sur le texte. L'approximation à l'ordre 1 donne la fréquence des lettres, l'approximation à l'ordre 2 donne la fréquence des digrammes, l'approximation à l'ordre 3 celle des trigrammes etc... Il s'agit d'une information plus précise que la simple distribution des lettres du texte. Pour toute lettre a, et pour tout mot x de longueur L-1, on note p( a | x ) la probabilité que xa soit un mot du texte, c'est la loi de probabilité assiociée à x. L'analyse à l'ordre L permet de calculer les lois des (L-1)-uplets. L'objectif de cette séance de travaux-pratiques est d'écrire un programme qui génère un texte aléatoire en respectant les lois de probabilités des (L-1)-uplets d'une source.



1. Entropie.

   1. Ecrire un progamme entropie [fichier] qui calcule la distribution des caractères dans un fichier. Il calculera l'entropie des caractères qui composent le fichier c'est-à-dire : la somme des - p(c) log( p(c) ) où p(c) est la probabilité du caractère c.

   2. Appliquez la commande à la source C de votre commande ( entropie.c ?)

   3. Appliquez la commande à l'exécutable lui même.

   4. Appliquez la commande sur la source C compressée par gzip.

2. Analyse à l'ordre L.

   
   Pour limiter la complexité des expériences numériques, les caractères lus dans un fichier texte seront transformés dans un jeu de 32 c symboles : les lettres A,B, ..., Z, les espaces \n, 032 et les caractères de ponctuations : 047, 054, 056, 073. Les symboles seront codés par les entiers : 0, 1, ..., 31. Un L-uplet est représenté par un mot de 5L bits et l' ensemble des lois associées par un tableau de 32^L-1 distribution de probabilités. Dans vos implantations, vous pourrez utiliser le type :

   typedef float* distrib;

   pour représenter une distribution de probabilité. Ainsi, les lois des (L-1)-uplets pourront être stockées dans des variables de type distrib *, un tableau dynamique indexé par les entiers inférieurs à 32^L-1..

   1. Estimez la valeur maximale que prendra L dans vos expériences numériques.

   2. Ecrire une fonction int code( int c ) qui renvoie un nombre compris entre 0 et 31 correspondant au symbole le plus proche, -1 en cas d'échec.

   3. Ecrire une fonction int caractere( int n ) qui renvoie le code ascii du caractère de code n.

   4. Ecrire une fonction distrib* ( FILE *src , int L ) qui calcule les lois associées aux mots de longueur L dans le fichier src.

3. Génération.

1. Ecrire une fonction int alea( distrib p) renvoie un entier aléatoire compris entre 0 et 31 suivant la loi p.

2. Implanter une procédure pour engendrer une suite de n symboles respectant les lois des L-uplets.

   void genere( distrib* dp , int L , int n );
   {

   etat = ...

   while ( n-- ) {

   s = alea( dp[etat] );

   c = caractere( s )

   ...

   etat = etat << 5 + s;

   }

}

Philippe Langevin,
Février 2006.