Partie 1

Q1. Faire un programme qui prend un argument le nom d'un fichier et écrit sur l'écran le nombre de fois où chacun des 256 caractères apparaît (ne pas afficher les caractères qui n'apparaissent pas). Le tableau devra être de la forme suivante:

Code ASCII | Nombre d'apparitions
  0        | 1
  1        | 1664
  9        | 93
  28       | 666
  65       | 888
  
   ...
   ...

Note: pour avoir le code ascii d'un caractère, il suffit de l'afficher avec %d au lieu de %c.

Q2. Compléter le programme pour qu'il affiche l'entropie du message. Rappel: il s'agit de faire la somme sur tous les caractères c du nombre de fois où c apparaît multiplié par l'opposé du logarithme (en base 2) de la *fréquence* du caractère c. Il ne faut pas compter les caractères qui n'apparaissent pas

On pourra utiliser la fonction log, disponible dans l'entête math.h, qui renvoie le logarithme naturel. Attention, il faudra compiler en ajoutant l'option -lm à gcc.

Quelques pièges:

• Déclarer votre buffer du type unsigned char buffer[1664] et non pas char buffer[1664]
• Quand vous calculez la fréquence de chacun des caractères, faire attention: si vous divisez deux entiers en C, il fera une division entière (alors qu'on a besoin pour l'énoncé d'une division flottante).
• La fonction log disponible donne un logarithme naturel, pour avoir un logarithme en base 2, il faut faire log2(x) = log(x) / log(2).

Partie 2

Q3. Télécharger les fichiers nécessaires à la suite.

Le fichier bits.c permet de lire et d'écrire dans un fichier bit par bit (et non pas octets par octets).

Q4. Lire et comprendre les fichiers bits.h et test.c. NE PAS LIRE bits.c.Compiler et exécuter test.c. Comprendre le fonctionnement du programme.

Dans la suite, on va créer un format de fichier compressé qui fonctionne de la manière suivante:

• Un octet dont la valeur est 0 est codé par le bit 0
• Un octet dont la valeur est 1 ou 2 est codé par les bits 100 ou 101
• Un octet dont la valeur est comprise entre 3 et 6 est codé par 11000, 11001, 11010 et 11011 (donc 110 suivi de sa valeur - 3, codée sur 2 bits)
• Un octet dont la valeur est comprise entre 7 et 14 est codé par 1110000, 1110001, ... 1110111 (donc 1110 suivi de sa valeur - 7, codée sur 3 bits)
• Les autres octets sont codés par 1111, suivi de leur valeur - 15 sur 8 bits
• La fin du fichier est représentée par la séquence 111111111111 (12 1).

Q5. Regardez le fichier ex avec la commande od -v -Ad -tu1z ex et le fichier compressé ex.cmp avec la commande xxd -b ex.cmp. Comprenez.

Q6. Ecrivez un programme pour compresser un fichier.

Q7. Ecrivez un programme pour décompresser un fichier.

Partie 3

Move to Front (mtf) est une heuristique qui modifie un fichier texte et qui espère augmenter la fréquence d'apparition des caractères de petits numéros, ce qui rend le texte plus facile à compresser par une méthode statistique.

Le principe est le suivant.

• On commence par un tableau code de 256 cases, initialement rempli par code[i] = i
• Pour chaque caractère c qu'on lit:
  • Chercher en quelle position i le caractère c se trouve dans le tableau code
  • Ecrire i
  • Modifier le tableau code pour que le caractère c soit en première position: il faut donc décaler tous les caractères de 0 à i-1 d'un cran vers la droite, et mettre c en position 0.

Par exemple, regardons ce qui se passe sur le texte toto. Initialement, le tableau a 256 positions (numérotées de 0 à 255), et on a par exemple

code[0] = 0
code[1] = 1
code[32] = 32
code[78] = 78
code[111] = 111
code[116] = 116
code[117] = 117

Le premier caractère est un t, c'est le caractère dont le code ASCII est 116. On cherche donc dans le tableau le caractère dont la valeur est 116. Il s'agit du caractère numéro 116. On écrit donc 116 et on décale le tableau

code[0] = 116
code[1] = 0
code[32] = 31
code[78] = 77
code[111] = 110
code[116] = 115
code[117] = 117

On passe au caractère suivant qui est le caractère o, donc le caractère de code ascii 111. On cherche donc dans le tableau où se trouve le caractère numéro 111. Il est en position numéro 112. On écrit donc 112, et le tableau devient:

code[0] = 111
code[1] = 116
code[32] = 30
code[78] = 76
code[111] = 109
code[112] = 110
code[113] = 112
..
code[116] = 115
code[117] = 117

On passe de nouveau au t, le caractère de code ascii 116. Il est en position 1 du tableau, donc on écrit 1, et le tableau devient:

code[0] = 116
code[1] = 111
code[32] = 30
code[78] = 76
code[111] = 109
code[112] = 110
code[113] = 112
..
code[116] = 115
code[117] = 117

Et on passe au o, le caractère de code ascii 111 qui se trouve en position 1, donc on écrit 1 et le tableau devient

code[0] = 111
code[1] = 116
code[32] = 30
code[78] = 76
code[111] = 109
code[112] = 110
code[113] = 112
..
code[116] = 115
code[117] = 117

Au final, on aura donc écrit les caractères de numéro 116 112 1 1, soit les caractères 't', 'p' et deux caractères spéciaux.

A noter qu'il n'est pas nécessaire de faire la conversion entre un caractère et son code ascii, c'est automatique en C.

Q8. Faire un programme qui prend un argument le nom d'un fichier et applique la transformation au fichier.

Q9. Faire un programme qui applique la transformation inverse.