Compression par plages — exercice corrigé de programmation Java (école d'ingénieur) (chapitre 6)

Compression par plages

Chaînes de caractères et entrées · niveau 3 (difficile)

Énoncé

La compression « par plages » remplace chaque suite de caractères identiques par le caractère suivi de la longueur de la suite : aaabccddddddddddddx devient a3b1c2d12x1.

Écrire static String compresser(String s), pour une chaîne sans chiffres.
Écrire static String decompresser(String code). Attention : une longueur peut avoir plusieurs chiffres.
Sur quelles chaînes la compression allonge-t-elle le texte ?

Corrigé


static String compresser(String s) {
    StringBuilder sb = new StringBuilder();
    int i = 0;
    while (i < s.length()) {
        char c = s.charAt(i);
        int j = i;
        while (j < s.length() && s.charAt(j) == c) j++;   // s[i..j-1] : même lettre
        sb.append(c).append(j - i);
        i = j;
    }
    return sb.toString();
}

static String decompresser(String code) {
    StringBuilder sb = new StringBuilder();
    int i = 0;
    while (i < code.length()) {
        char c = code.charAt(i);
        int j = i + 1;
        while (j < code.length() && Character.isDigit(code.charAt(j))) j++;
        int n = Integer.parseInt(code.substring(i + 1, j));
        for (int k = 0; k < n; k++) sb.append(c);
        i = j;
    }
    return sb.toString();
}


a3b1c2d12x1 -> aaabccddddddddddddx

Dans les deux méthodes, l'indice j avance jusqu'à la fin de la plage en cours, puis i saute directement à j : chaque caractère est examiné une seule fois. Dans decompresser, la plage de chiffres code.substring(i + 1, j) peut en contenir plusieurs, d'où 12. Une chaîne sans répétitions double de longueur : abc devient a1b1c1. La compression n'est utile que pour des textes à longues plages (images en noir et blanc, par exemple).