Table des matières

Compression RLE basique

La compression RLE (Run Length Encoding) est une ancienne technique de compression, utilisée en particulier dans le codage des images. Le principe très simple de cette technique est le suivant: toute séquence de caractères c identiques, et de longueur L (assez grande) est codée par : c flag L où flag est un caractère spécial, si possible peu fréquent dans les données à compresser. Les autres séquences ne sont pas modifiées.

Dans cette première partie, nous simplifions encore plus la compression RLE pour simplifier vos algorithmes : nous supposerons que le flag est absent des données à compresser (vous renverrez une erreur s’il est présent), et nous encoderons toutes les chaînes de caractères, même celles plus courtes que 4, alors que cela occupe plus de place. Nous codons la longueur L sous forme d’un caractère, la longueur maximale d’une séquence à compresser est donc 9. Dans le cas d’une séquence de plus de 9 caractères identiques, les 9 premiers seront codés de manière compressée puis la suite de la séquence sera considérée comme une nouvelle séquence à coder voir exemples de fonctionnement.

Travail à réaliser

Écrire une classe BasicRLECompression prenant en argument de son constructeur la valeur de flag et qui implémente l’interface ICompression suivante.

interface ICompression {
    public String compress(String data);
    public String uncompress(String data);
}

Aide algorithmique

On rappelle qu’une chaîne de caractères peut être vue comme un tableau de caractères. Reportez-vous à la documentation de la classe String de la javadoc. Nous attirons en particulier votre attention sur les méthodes charAt, length et substring de cette classe.

Dans le cadre de cette compression, vous aurez besoin de déterminer la longueur du plus long préfixe d’une chaîne de caractères constitué d’un même caractère (i.e., dans la chaine aaaabcccce, on renverra la valeur 4, puisque le mot commence par 4 a qui sont suivis d’un b). Vous commencerez par implémenter une méthode auxiliaire int lengthOfSingleLetterPrefix(String s) qui renvoie cette longueur. Cette méthode devra effectuer les pas suivants:

Votre méthode compress fera appel à la méthode précédente et effectuera les pas suivants :

Votre méthode uncompress effectuera les pas suivant :

Gestion des erreurs

En cas d’erreur dans les fonctions de compression ou de décompression, vous devrez lever une exception. Cette dernière devra contenir :

  1. un message d’erreur explicitant l’erreur qui s’est produite voir exemples de fonctionnement
  2. le message déjà traité (i.e. avant l’erreur)
  3. le reste du message à traiter (i.e. après l’endroit où l’erreur s’est produite).

Exemples de fonctionnement

(flag = ‘#’)

Entrez les données à comprimer : aaaaaaaaaaaaaaaa
Forme compressée:   a#9a#7
Test ok!

Entrez les données à décompresser : a#4
décompressé : aaaa

(flag = ‘$’)

Entrez les données à comprimer : aaaaaaa##bbbbbbaaaaaaaabbbbbbbcccccccccc#a
Forme compressée:   a$7#$2b$6a$8b$7c$9c$1#$1a$1
Test ok!

Entrez les données à comprimer : aaaa$bbccccc#
Erreur de compression : Flag présent dans la chaîne de caractère.
	encodé à ce stade : a$4
	non traité	  : $bbccccc#

Entrez les données à décompresser : a$4b$$4b$2d
Erreur de décompression : Caractère $ incorrect après le flag $
	décodé à ce stade : aaaa
	non décodé        : b$$4b$2d

Attention, toutes les erreurs que vous pouvez rencontrer ne sont pas présentées dans ces exemples. Déterminez toutes celles qui peuvent se produire et gérez-les correctement dans votre classe d’exception.

Compression RLE complète

Nous passons maintenant à une version plus complète de la compression RLE en lui apportant deux modifications :

Écrivez une classe RLECompression implémentant cette nouvelle compression, et comparez ses taux de compression avec la précédente.

Exemples de fonctionnement de la version complète

(flag = ‘#’)

Entrez les données à comprimer : #aaaaaaaaaaaaaaaa
Forme compressée:   #0a#9a#7
[ratio = 47.05882352941177%]
Test ok!

Entrez les données à décompresser : #0a#4
décompressé : #aaaa

Entrez les données à comprimer : aaaaaaa##bbbbbbaaaaaaaabbbbbbbcccccccccc#a
Forme compressée:   a#7#0#0b#6a#8b#7c#9c#0a
[ratio = 54.76190476190476%]
Test ok!

Entrez les données à décompresser : aa#04ba##4bb#0d
Erreur de décompression : Caractère # incorrect après le flag #
	décodé à ce stade : aa#4ba
	non décodé        : ##4bb#0d

Pour aller plus loin

Pour coder de grandes séquences consécutives, on peut utiliser les valeurs spéciales de L pour indiquer une extension du codage du nombre de répétitions. En effet, les valeurs 0, 1, 2 et 3 ne sont pas utilisées car les chaînes de longueur inférieure à 4 ne sont pas compressées. Nous utilisons déjà le 0 pour le flag seul. Nous pouvons ainsi décider :

De plus, si L=1, la longueur minimale codée de manière étendue devrait être 10 (sinon on code comme avant). Donc, on peut effectuer un décalage de 10 sur la valeur de L. Ainsi #199 représente une répétition de 109 caractères.

On peut utiliser la même technique pour coder des répétitions du flag ; dans ce cas, on peut utiliser par exemple la valeur spéciale ‘3’ pour indiquer que le flag est effectivement compressé, et le nombre de répétitions est encodé sur le prochain caractère. En effet, la valeur ‘3’ ne fournit aucune compression (a#3 fait la même taille que aaa) - La valeur compressée de aa#####bb est aa#35bb De même que précédemment, il est ridicule d’écrire #31 pour coder une seule répétition. On peut donc soit faire un décalage, soit définir un codage étendu à nouveau…