Le principe est similaire à celui de la compression par demi-octets, mais en comptant les mots et non les caractères (et en doublant l'espace de codage :

• On établit une liste des mots les plus fréquents dans le texte d'origine
• on code sur 8 bits les plus fréquents (par exemple les 128 plus fréquents, signalés par un bit de poids fort à 0) ;
• sur 16 bits les suivants (par exemple les 2¹⁵-1 suivants, signalés par un bit de poids fort à 1) ;
• pour le reste, on ne code pas (mais il faut signaler au décodeur la partie non codée, par exemple par deux octets de signalement remplis de 1, suivis de deux octets codant le nombre de caractères non compressés).

• Que faire des séparateurs ?
  • Les inclure dans le dictionnaire ? Seuls ou combinés ? (une virgule suivie d'un espace, par exemple)
  • Coder leurs positions en en-tête ? (voir codage des espaces dans le TP1)
  • Coder des suites de caractères plutôt que des mots ?
• Le nombre total de mots est très grand.
   
  • Limiter le comptage à une "petite" portion du texte ? Dans ce cas, il faudra calibrer (et justifier dans l'analyse) la taille de cette portion.
  • Coder des suites de caractères plutôt que des mots ?

Vous pouvez commencer par un Map, puis réfléchir plus tard à une structure plus efficace.

Attention à la complexité des opérations sur votre structure. Réfléchissez au nombre de comparaisons de caractères qu'il faut pour insérer le mot barbapapa (qui a 11 caractères) à la liste ci-dessous, triée alphabétiquement.

  abri
  arbalète
  baba
  bad
  bar
  barbabelle
  barbalala
  barbamama
  barbotine
  barbouille

Il est donc recommandé de définir une classe (voire une interface) Dictionnaire, qui fournit deux méthodes :

		
		void incremente(String)
		int occurrences(String)
	      

pour permettre de changer de manière transparente son implémentation pour utiliser par la suite une structure de données plus efficace.

Le TP est à rendre pour le mercredi 8 février.

Je vous rappelle que l'analyse m'importe plus que les programmes que vous aurez écrits. Les programmes ne sont là que pour vous aider à comprendre en détail la méthode, et à produire des mesures qui vous serviront dans l'analyse.

La liste suivante est à prendre comme une suggestion, dans l'ordre de priorité, d'éléments à fournir dans votre analyse.

1. L'analyse de complexité et taux de compression théoriques (pire et meilleur cas).
2. Les performances en termes de taux de compression sur les caractères (TP1) puis sur les mots (ce TP). Pour cela, il n'est pas nécessaire d'avoir programmé le codage : il suffit d'avoir calculé les fréquences sur les fichiers de test.
3. Les performances en termes de taux de compression sur plusieurs sources de type texte (dans la même langue, dans une autre langue) et binaire pour la première version.
4. Les performances en termes de temps de calcul (ce n'est qu'à ce stade que vous avez besoin de programmer le codage)
5. Les performances (temps et taux de compression) sur des fichiers binaires dans la deuxième version (dans ce cas il faut déterminer comment procéder pour les séparateurs. Utiliser l'octet de valeur 0 peut être une bonne idée).
6. D'autres éléments complétant l'analyse : comparaison des performances (temps et taux de compression) en ne calculant les fréquences que sur une partie de la source, évolution de ces performances en fonction de la taille de la partie considérée, etc.