Table des matières

Compression RLE

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.

Lorsque le caractère spécial flag est rencontré dans la séquence d’origine, il est codé par la séquence spéciale flag 0 (i.e. pas de caractère c, et L = 0). 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ères compressées puis la suite de la séquence sera considérée comme une nouvelle séquence à coder. Nous obtenons un gain dans le codage si la longueur du mot compressé est inférieure à celle du mot original. Aussi, nous considérons une valeur de L au moins égale à 4. En effet a#3 est équivalent à aaa alors que a#4 est plus petit que aaaa.

Travail à réaliser

Écrire une classe RLECompression 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);
}

Gestion des erreurs

En cas d’erreur dans la fonction 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 exemple de fonctionnement
  2. le message déjà décodé (i.e. avant l’erreur)
  3. le reste du message à décoder (i.e. après l’endroit où l’erreur s’est produite).

Remarque :Pour extraire une sous-chaîne on pourra utiliser la méthode substring de la classe String du JDK.

Exemples de fonctionnement (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…