Analyse statistique de fichiers
Série 3 – corrigé

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.

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) {
    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 :

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.

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 :

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 :

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 :

ArrayList<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) {
  int lineLen = 4;
  for (int leaf = 0; leaf <= 9; ++leaf) {
    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é. Notez qu'il est possible qu'une ligne fasse plus de 80 caractères, car on utilise round, qui arrondit à l'entier le plus proche, pour arrondir les fréquences mises à l'échelle. On pourrait aussi utiliser floor pour éviter ce problème.

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.

Notez aussi l'utilisation de la méthode format de la classe String, qui permet de construire une chaîne composée de différents éléments mis en forme. La syntaxe de la chaîne de formattage est le même que celle de la méthode printf, et est décrite en détail dans la documentation de la classe java.util.Formatter. Dans le code ci-dessous, on l'utilise pour garantir que toutes les tiges sont représentées au moyen de 2 caractères, mêmes celles composées d'un seul chiffre.

ArrayList<String> lines = new ArrayList<>();
for (int stem = 0; stem <= freq.length / 10; ++stem) {
  StringBuilder lineBuilder =
    new StringBuilder(String.format("%2d|", stem));
  for (int leaf = 0; leaf <= 9; ++leaf) {
    int i = 10 * stem + leaf;
    if (i >= freq.length)
      break;
    for (int k = 0; k < round(freq[i] * scale); ++k)
      lineBuilder.append(leaf);
  }
  lines.add(lineBuilder.toString());
}
return lines;