Analyse statistique de fichiers

Le but de cette série est de vous familiariser avec le concept de flot d'octets en les utilisant pour analyser le contenu de différents fichiers mis à votre disposition.

Pour commencer, téléchargez l'archive Zip que nous vous fournissons, extrayez son contenu et créez un nouveau projet à partir du dossier STAT créé. Notez que cette archive ne contient aucun code, mais six fichiers nommés file0.bin à file5.bin. Le premier d'entre eux, file0.bin, contient simplement la totalité des octets (de 0 à 255), dans l'ordre. Les cinq autres contiennent des données diverses, compressées ou non, dont vous allez analyser certaines caractéristiques.

Une fois le projet créé, marquez le dossier src comme dossier source en faisant un clic droit sur lui puis sélectionnant Mark Directory as puis Sources Root. Ensuite, créez un nouveau paquetage nommé cs108 dans ce dossier, puis une classe nommée Main dans ce paquetage. Pour simplifier les choses, tout le code de cette série se trouvera dans cette classe.

La totalité des analyses qui suivront peuvent se faire au moyen d'une table de fréquence d'apparition des différents octets dans le fichier. Le premier but de cet exercice est donc d'écrire une méthode (statique) dans la classe Main à laquelle on passe un nom de fichier et qui retourne cette table sous la forme d'un tableau d'entiers de 256 entrées. La valeur d'index i de ce tableau donne le nombre d'occurrences de l'octet i dans le fichier.

Cette méthode pourrait ressembler à ceci :

int[] byteFrequencies(String fileName) { … }

Par exemple, appliquée au nom de fichier file0.bin, elle retourne une table de 256 entiers valant tous 1 puisque chaque octet apparaît exactement une fois dans le fichier file0.bin. Pour vérifier que tel est bien le cas, vous pouvez utiliser la méthode toString de la classe Arrays afin d'afficher à l'écran le contenu de cette table. Vous devriez obtenir :

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, …]

Pour des raisons de présentation, la chaîne affichée a été tronquée ici, mais elle ne contient que la valeur 1 répétée 256 fois.

Pour mémoire, pour lire les données d'un fichier, vous devez créer un flot d'entrée de type FileInputStream en passant le nom de ce fichier au constructeur, par exemple ainsi :

InputStream stream = new FileInputStream("file0.bin");

Une fois ce flot créé, vous pouvez utiliser la variante sans argument de la méthode read pour lire un à un les octets du fichier. Ceux-ci sont retournés sous la forme d'un entier compris entre 0 et 255 (inclus), sauf si la fin du flot est atteinte, auquel cas -1 est retourné. N'oubliez pas de fermer le flot au moyen de la méthode close lorsque vous avez lu tous les octets — soit explicitement, soit implicitement au moyen de la notation try-with-resource.

Une fois cette méthode écrite, écrivez la première méthode d'analyse qui, étant donnée la table produite par la méthode ci-dessus, retourne la moyenne des octets contenus dans un fichier. Cette méthode aura la signature suivante :

double average(int[] freq) { … }

Attention, cette méthode ne doit pas calculer la moyenne des valeurs du tableau passé, mais la moyenne des valeurs du fichier étant donnée la table de fréquence d'apparition passée !

Pour vérifier qu'elle fonctionne, assurez-vous que la moyenne des valeurs contenues dans le fichier file0.bin est bien 127.5, comme attendu.

Cela fait, calculez et affichez la valeur moyenne des cinq autres fichiers. Sachant que deux de ces fichiers contiennent des données non compressées, arrivez-vous à deviner desquels il s'agit ? (Si vous n'y arrivez pas, passez à l'exercice suivant, à la fin duquel vous aurez plus d'indications.)

En dehors de la moyenne, une autre information qu'il est intéressant de connaître pour les différents fichiers est leur entropie. En théorie de l'information, l'entropie H d'une séquence d'octets est définie de la manière suivante :

\[ H = -\sum_{i = 0}^{255} p(i)\,\log_2 p(i) \]

où \(p(i)\) est la probabilité d'apparition de l'octet \(i\) dans la séquence, qui est simplement le rapport entre le nombre d'occurrences de l'octet dans la séquence et la longueur de cette dernière. Par convention, si un octet n'apparaît jamais, c-à-d si \(p(i) = 0\), alors le terme \(p(i)\,\log_2 p(i)\) est remplacé par 0 dans la somme ci-dessus.

Pour calculer l'entropie des différents fichiers, écrivez une méthode la déterminant en se basant sur la table de fréquence, dont la signature pourrait être la suivante :

double entropy(int[] freq) { … }

Pour écrire votre méthode, souvenez-vous que le logarithme dans une base \(b\) quelconque peut se calculer au moyen du logarithme naturel \(\ln\), grâce à l'égalité suivante : \[ \log_b x = \frac{\ln x}{\ln b} \] En Java, le logarithme naturel peut être calculé au moyen de la méthode log de la classe Math.

Une fois la méthode entropy écrite, modifiez votre programme principal pour calculer et afficher l'entropie des fichiers fournis. Vérifiez qu'elle vaut bien 8 — la plus grande valeur possible — pour le fichier file0.bin.

Cela fait, et sachant que les techniques de compression tirent généralement parti de la faible entropie des données pour les compresser, arrivez-vous à deviner lesquels des fichiers file1.bin à file5.bin contiennent des données non compressées ?

Pour terminer, et pour avoir une meilleure idée de la distribution des valeurs contenues dans les différents fichiers, écrivez une méthode permettant de dessiner un diagramme tige et feuille des octets.

Un diagramme tige et feuille (stem-and-leaf plot, souvent abrégé stemplot en anglais) permet de visualiser la distribution d'un ensemble de valeurs entières. Il est similaire à un histogramme à barres horizontales, mais dont les barres sont les chiffres des unités des valeurs elle-mêmes.

Par exemple, admettons l'existence d'une équipe de 14 jeunes sportifs dont la taille en centimètres est { 152, 152, 154, 160, 161, 161, 162, 163, 163, 173, 173, 175, 175, 191 }. Pour créer un diagramme tige et feuille à partir de ces données, on commence par séparer chaque valeur en une tige, composée de tous les chiffres sauf celui des unités, et une feuille, le chiffre des unités. Par exemple, la valeur 152 a pour tige 15 et pour feuille 2, tandis que la valeur 154 a également 15 comme tige mais 4 comme feuille. Cette séparation faite, on produit le diagramme en affichant une ligne par tige possible entre la plus petite et la plus grande tige trouvées dans les données. Chaque ligne est composée de la tige qui lui correspond, suivie d'une barre verticale et de toutes les feuilles ayant cette tige, triées en ordre croissant. Pour les valeurs données plus haut, on obtient le diagramme suivant :

15|224
16|011233
17|3355
18|
19|1

Un tel diagramme permet d'une part de visualiser la distribution des données, puisque la longueur de chaque ligne est proportionnelle au nombre de valeurs ayant la tige correspondant à la ligne, et d'autre part de connaître précisément les valeurs présentes dans les données. Ainsi, au moyen du diagramme ci-dessus, il est trivial de reconstituer la totalité des données.

Le diagramme tige et feuille correspondant au premier fichier fourni, file0.bin, n'est pas très intéressant puisque chaque ligne est similaire. Amputé des lignes ayant les valeurs 2 à 23 comme tiges, il ressemble à ceci :

 0|0123456789
 1|0123456789
 ...
24|0123456789
25|012345

Les diagrammes des autres fichiers sont plus intéressants.

Notez qu'au vu de la grande quantité d'octets contenus dans les fichiers fournis, vous ne pourrez pas dessiner un diagramme représentant la totalité des octets, sauf pour le premier fichier. Dès lors, nous vous suggérons de diviser la fréquence d'apparition de chaque octet par une valeur telle que la plus longue ligne du diagramme fasse environ 80 caractères.