Aller au contenu

Compression Run-Length Encoding⚓︎

Certains formats de fichiers informatiques utilisent la compression Run-Length Encoding.

Le principe est de remplacer les suites de valeurs identiques par des couples (valeur, répétition).

On propose ci-dessous un exemple d'application à un fichier texte :

Exemple

🐍 Console Python
>>> compression_RLE("aabbbbcaa")
"2a4b1c2a"

Le code "2a4b1c2a" signifie que la chaîne "aabbbbcaa" comporte dans cet ordre :

  • deux "a",
  • quatre "b",
  • un "c",
  • deux "a".

Remarque

Cette méthode de compression est particulièrement efficace dans le cas d'un texte comportant de nombreuses répétitions.

Par exemple, le texte 'aaaa...a' comportant 10 000 fois le caractère "a" sera compressé en "10000a". On passe ainsi de 10 000 caractères à 6 !

Afin de simplifier la démarche, on ne considérera que des chaînes de caractères ne comportant aucun chiffre. Ainsi, toutes les chaînes étudiées ne comporteront que des lettres ou de la ponctuation.

Afin de calculer la compression d'une chaîne de caractères par cette méthode, on doit la parcourir en comptant le nombre de répétitions de chaque caractère lu. Lorsque l'on change de caractère, on ajoute le couple (répétition, caractères) à la chaîne compressée, sans oublié d'ajouter une virgule si besoin.

Exemples

🐍 Console Python
>>> compression_RLE("aabbbbcaa")
"2a4b1c2a"
>>> compression_RLE("aa aa")
"2a1 2a"
>>> compression_RLE("aaa")
"3a"
>>> compression_RLE("aA")
"1a1A"

Vous devez écrire la fonction compression(texte) décrite.

On garantit que le texte proposé est non-vide.

🐍 Script Python
def compression_RLE(texte):
    chaine_compressee = ""

    caractere_repete = texte[0]
    nb_repetitions = ...

    for caractere in texte:
        if caractere == ...:
            nb_repetitions = ...
        else:
            chaine_compressee += ... + ...
            caractere_repete = ...
            nb_repetitions = ...

    chaine_compressee += ...

    return ...
Coup de pouce

Python ne supporte pas "l'addition" d'un caractère et d'un entier. On pourra utiliser la méthode suivante :

🐍 Console Python
>>> str(5) + "a"
"a5"
# Testsbksl-nlassert compressionpy-undRLE("aabbbbcaa") == "2a4b1c2a"bksl-nlassert compressionpy-undRLE("aa aa") == "2a1 2a"bksl-nlassert compressionpy-undRLE("aaa") == "3a"bksl-nlassert compressionpy-undRLE("aA") == "1a1A"bksl-nlbksl-nlbksl-nl# Tests supplémentairesbksl-nlassert compressionpy-undRLE("r") == "1r"bksl-nlassert compressionpy-undRLE("r"py-str10) == "10r"bksl-nlassert compressionpy-undRLE("r"py-str10+"a"py-str5) == "10r5a"bksl-nl ∞/∞

def compressionpy-undRLE(texte):bksl-nl chainepy-undcompressee = ""bksl-nlbksl-nl caracterepy-undrepete = texte[0]bksl-nl nbpy-undrepetitions = ...bksl-nlbksl-nl for caractere in texte:bksl-nl if caractere == ...:bksl-nl nbpy-undrepetitions = ...bksl-nl else:bksl-nl chainepy-undcompressee += ... + ...bksl-nl caracterepy-undrepete = ...bksl-nl nbpy-undrepetitions = ...bksl-nlbksl-nl chainepy-undcompressee += ...bksl-nlbksl-nl return ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert compressionpy-undRLE("aabbbbcaa") == "2a4b1c2a"bksl-nlassert compressionpy-undRLE("aa aa") == "2a1 2a"bksl-nlassert compressionpy-undRLE("aaa") == "3a"bksl-nlassert compressionpy-undRLE("aA") == "1a1A"bksl-nlbksl-nldef compressionpy-undRLE(texte):bksl-nl chainepy-undcompressee = ""bksl-nlbksl-nl caracterepy-undrepete = texte[0]bksl-nl nbpy-undrepetitions = 0bksl-nlbksl-nl for caractere in texte:bksl-nl if caractere == caracterepy-undrepete:bksl-nl nbpy-undrepetitions += 1bksl-nl else:bksl-nl chainepy-undcompressee += str(nbpy-undrepetitions) + caracterepy-undrepetebksl-nl caracterepy-undrepete = caracterebksl-nl nbpy-undrepetitions = 1bksl-nlbksl-nl chainepy-undcompressee += str(nbpy-undrepetitions) + caracterepy-undrepetebksl-nlbksl-nl return chainepy-undcompresseebksl-nlbksl-nlbksl-nl# Testsbksl-nlassert compressionpy-undRLE("aabbbbcaa") == "2a4b1c2a"bksl-nlassert compressionpy-undRLE("aa aa") == "2a1 2a"bksl-nlassert compressionpy-undRLE("aaa") == "3a"bksl-nlassert compressionpy-undRLE("aA") == "1a1A"bksl-nlbksl-nl

A

Commentaires⚓︎

On crée la variable chaine_comrpessee destinée à contenir la chaîne de caractères compressées.

Il faut ensuite initialiser le décompte. Pour cela on crée deux variables :

  • caractere_repete contiendra le caractère que la fonction est en train de compter. On l'initialise avec le premier caractère du texte ;
  • nb_repetitions contiendra le nombre de caractères identiques consécutifs.

On débute ensuite un parcours de l'ensemble du texte. Pour chaque caractere, on se demande s'il est égal à caractere_repete :

  • si oui, on incrémente nb_repetitions,
  • si non, on ajoute un nouveau couple au résultat (chaine_compressee += str(nb_repetitions) + caractere_repete) et on réinitialise les variables caractere_repete et nb_repetitions.

En fin de parcours, le couple correspondant au dernier caractère n'a pas été ajouté : on l'ajoute hors de la boucle.

En dernier lieu on renvoie la chaîne compressée.

Remarque : la concaténation de chaînes de caractères !py chaine += nouveau peut être coûteuse en Python (du fait de la création d'une nouvelle chaîne de caractères). On peut utiliser la méthode !py str.join qui permet d'éviter ce désagrément.

Il faut alors créer une liste de couples couples à regrouper dans la chaîne compressée et de les "joindre" en les séparant par une chaîne vide !py "".join(couples).

🐍 Script Python
def compression_RLE(texte):
    couples = []

    caractere_repete = texte[0]
    nb_repetitions = 0

    for caractere in texte:
        if caractere == caractere_repete:
            nb_repetitions += 1
        else:
            couples.append(str(nb_repetitions) + caractere_repete)
            caractere_repete = caractere
            nb_repetitions = 1

    couples.append(str(nb_repetitions) + caractere_repete)

    return "".join(couples)

Z

Retour en haut de la page