Analyse statistique de fichiers
CS-108 — Corrigé de la série 2
Introduction
Le code du corrigé vous est fourni sous la forme d'une archive Zip. Les solutions aux différents exercices sont rapidement présentées ci-dessous.
Exercice 1
Pour calculer la table de fréquence, il suffit d'itérer sur les octets du fichier au moyen de la méthode read
en ajoutant, pour chaque octet lu, 1 à l'entrée qui lui correspond.
int[] byteFrequencies(String fileName) throws IOException { try (InputStream stream = new FileInputStream(fileName)) { int[] freq = new int[256]; int b; while ((b = stream.read()) != -1) freq[b] += 1; return freq; } }
Une fois la table de fréquence obtenue, il n'est pas difficile de l'utiliser pour calculer la moyenne des octets.
double average(int[] freq) { int sum = 0, length = 0; for (int i = 0; i < freq.length; i += 1) { sum += i * freq[i]; length += freq[i]; } return (double) sum / (double) length; }
En utilisant cette méthode pour calculer la valeur moyenne des octets des fichiers fournis, on obtient :
Fichier | Moyenne |
---|---|
file0.bin |
127.50 |
file1.bin |
91.99 |
file2.bin |
122.46 |
file3.bin |
91.91 |
file4.bin |
126.08 |
file5.bin |
127.11 |
On constate que, à l'exception de file1.bin
et file3.bin
, tous les fichiers ont une moyenne proche de 127.5, ce qui indique que leurs valeurs sont bien distribuées. On peut dès lors supposer que file1.bin
et file3.bin
sont ceux qui ne sont pas compressés, car ils ne semblent pas utiliser de manière optimale la totalité des valeurs à leur disposition, en quelque sorte.
Exercice 2
Le calcul de l'entropie ne pose pas de problème particulier, il suffit de traduire en Java la formule mathématique de l'énoncé :
double entropy(int[] freq) { int length = 0; for (int f : freq) length += f; double hNeg = 0, log2 = log(2); for (int f : freq) { if (f != 0) { double p = (double) f / (double) length; hNeg += p * log(p) / log2; } } return -hNeg; }
En utilisant cette méthode pour calculer l'entropie des différents fichiers, on obtient :
Fichier | Entropie |
---|---|
file0.bin |
8.00 |
file1.bin |
4.66 |
file2.bin |
7.97 |
file3.bin |
4.71 |
file4.bin |
7.99 |
file5.bin |
8.00 |
Une fois encore, on constate que les fichiers file1.bin
et file3.bin
se distinguent des autres, dans ce cas par le fait que leur entropie est sensiblement moins élevée.
Comme dit dans l'énoncé, les techniques de compression tirent parti de la faible entropie des données qu'on leur fournit pour les compresser. On peut en conclure, encore une fois, que les fichiers file1.bin
et file3.bin
ne sont pas compressés, ce qui est bien le cas. Le contenu des différents fichiers est donné par la table suivante :
Fichier | Contenu |
---|---|
file0.bin |
Tous les octets de 0 à 255, dans l'ordre |
file1.bin |
Texte du livre Zadig de Voltaire, en français |
file2.bin |
Photo au format (compressé) JPEG |
file3.bin |
Texte du livre Huckleberry Finn de Mark Twain, en anglais |
file4.bin |
Comme file1.bin mais compressé avec bzip2 |
file5.bin |
Suite de 47138 octets aléatoires |
Exercice 3
Le dessin du diagramme tige et feuille peut se faire en deux temps : premièrement, il faut calculer un facteur de redimensionnement pour éviter que les lignes fassent plus de 80 caractères, comme expliqué dans l'énoncé ; ensuite, il faut calculer le diagramme lui-même, représenté ici par un tableau dynamique contenant chaque ligne, représentée par une chaîne. La structure générale de la méthode de calcul est donc :
List<String> stemPlot(int[] freq) { // calcul du facteur de redimensionnement // ... // calcul du diagramme tige et feuilles (redimensionné) // ... }
Le facteur de redimensionnement, nommé scale
ci-dessous, se calcule en déterminant la longueur de la plus longue ligne du diagramme non redimensionné (maxLineLen
ci-dessous), puis en divisant 80 par cette valeur.
int maxLineLen = 0; for (int stem = 0; stem <= freq.length / 10; stem += 1) { int lineLen = 3; // 3 = longueur des tiges for (int leaf = 0; leaf <= 9; leaf += 1) { int i = 10 * stem + leaf; if (i >= freq.length) break; lineLen += freq[i]; } maxLineLen = max(lineLen, maxLineLen); } double scale = min(1, 80d / maxLineLen);
Une fois le facteur de redimensionnement calculé, il est possible de générer le diagramme redimensionné.
La chaîne correspondant à chaque ligne est construite au moyen de la classe StringBuilder
, qui est ce que l'on nomme un bâtisseur de chaînes. Son but est de construire une chaîne de caractères en plusieurs étapes, et de manière efficace — bien plus que l'opérateur +
ne le permet. Cette classe sera décrite plus en détail dans une leçon ultérieure.
List<String> lines = new ArrayList<>(); for (int stem = 0; stem <= freq.length / 10; stem += 1) { StringBuilder lineBuilder = new StringBuilder(); if (stem < 10) lineBuilder.append("0"); lineBuilder.append(stem).append("|"); for (int leaf = 0; leaf <= 9; leaf += 1) { int i = 10 * stem + leaf; if (i >= freq.length) break; String leafString = String.valueOf(leaf); int leavesCount = (int) (freq[i] * scale); lineBuilder.append(leafString.repeat(leavesCount)); } lines.add(lineBuilder.toString()); } return lines;