Compression RLE et LZ

I) Présentation et objectifs
II) Lecture et écriture d'un fichier
III) Compression RLE
IV) Compression Ziv et Lempel
V) Bilan

I) Présentation et objectifs

1) Compression et décompression d'un fichier

La compression de données est l'opération informatique consistant à transformer un fichier A en un fichier B:
    • plus petit (en théorie) que le fichier A
    • pouvant restituer les mêmes informations ou des informations voisines, du fichier A
La décompression est l'opération inverse de la compression.

  On distingue deux familles d'algorithmes de compression:
    • les algorithmes de compression sans perte qui après les opérations successives de compression et de décompression restituent le fichier A de départ.
    • les algorithmes de compression avec perte qui ne permettent pas de reconstituer le fichier A de départ aprés les opérations successives de compression et de décompression. Les informations restituées ne sont pas identiques, mais seulement voisines de celles du fichier A de départ.

  Les algorithmes de compression sans perte sont utiles pour les documents, les archives, les fichiers exécutables ou les fichiers texte. Par exemple, les fichiers .zip, .rar, .7z sont des fichiers compressés par des algorithmes sans perte.
  Les algorithmes de compression avec perte sont utiles pour les images, le son et la vidéo. Par exemple, les fichiers .jpeg, .mp3, .divx, .mpeg sont des fichiers compressés par des algorithmes avec perte.

  Voir Wikipédia pour des compléments.

2) Objectifs

   On étudie deux algorithmes classiques de compression sans perte, exploitant les répétitions éventuelles:
    •  L'algorithme RLE, en anglais le run-length encoding, appelé en français le codage par plages.  L'idée est de compter les octets consécutifs égaux.
    •  L'algorithme de Ziv et Lempel, algorithme de compression par dictionnaire utilisant une fenêtre glissante ; les motifs déjà rencontrés dans la fenêtre sont remplacés par une référence à leur première apparition

3) Organisation du travail

    • On donne dans le II) les fonctions de conversion listes/fichiers.
    • Dans les paragraphes suivants les algorithmes seront précisément décrits puis codés.
    • Les tests sont ensuite faits sur de petites listes d'entiers puis sur de vrais fichiers.

  Les fichiers de données sont disponibles sur le site maths-algo.fr. Il y a:
    (1) Un fichier de 100 000 octets aléatoires de valeur 96 ou 97 (ce qui donne a ou b en mode “texte”) appelé “ab.txt”
    (2) Un fichier de 100 000 octets aléatoires de valeur 96, 97 ou 98 (ce qui donne a, b ou c en mode “texte”) appelé “abc.txt”
    (3) La nouvelle “Boule de Suif” de Guy de Maupassant de 86456 octets appelé “boule de suif.txt”
    (4) Une image bicolore au format .bmp de taille 320×240 pixels de 38518 octets appelée “etoile_BMP.bmp”
    (5) La même image au format .jpg de 12051 octets, appelée “etoile_JPG.jpg”
    (6) Une image en couleurs au format .bmp de 320×240 pixels  de 230454 octets appelée “soleils.bmp”

II) Lecture et écriture d'un fichier

  Un fichier informatique est une suite ordonnée d'octets enregistré sur un support. Pour travailler plus lisiblement ces octets seront convertis en entiers de {0,1,...,255}. On donne ici les fonctions de conversion listes/fichiers.

# -*- coding: UTF-8 -*
import os                    # Module contenant des fonctions utiles
##print(os.getcwd())        # Affiche le répertoire courant de travail
# Pour changer le répertoire courant de travail, on utilise os.chdir(); par exemple:
##os.chdir("C:/Users/Eric/Documents")

def lire_fichier(nom_fichier):
    """ Liste d'octets contenus dans fichier appelé nom_fichier convertis en
    une liste d'entiers de {0,...,255}"""
    with open(nom_fichier, "rb") as fich:   # Ouverture en lecture de fichier
         octets = fich.read()              # lecture du contenu de fichier
    return list(octets)                    # Conversion en une liste d'entiers

def enregistrer_fichier(nom_fichier, contenu):
    """Enregistrement du contenu dans le fichier appelé nom_fichier.
    contenu est une liste d'entiers de {0,...,255} qui est convertie en octets
    avant l'enregistrement"""
    octets = bytes(contenu)                # Conversion en liste d'octets
    with open(nom_fichier, "wb") as fich:  # Ouverture en écriture du fichier
        fich.write(octets)                 # Enregistrement

Un fichier est dans la suite une liste d'entiers de {0,...,255}. Les fonctions données ci-dessus permettent de travailler avec des vrais fichiers informatiques.

  Pour ajouter des éléments x, y, z,... à une liste L, il est plus rapide de faire L += [x, y, z] que L = L + [x, y, z]

  Les fichiers de données pour la compression sont disponibles dansce répertoire

III) Compression RLE

1) Description

  L'algorithme de compression RLE, en anglais le run-length encoding, appelé en français le codage par plages est un algorithme de compression sans perte rapide et très simple mais souvent peu performant.   L'idée est de compter les octets consécutifs égaux. L'algorithme est intéressant lorsqu'on rencontre très souvent dans le fichier de "longues" suites d'octets identiques. Ce n'est en général pas le cas, sauf dans certains cas particuliers.

On part d'un fichier (une liste d'octets) A que l'on parcourt et transforme en un fichier (une liste d'octets) B par les règles de transformation suivantes:
    (1) On initialise B à la liste vide.
    (2) Pour toute suite de n octets (avec 0 < n <  256) consécutifs identiques de valeur v de A, on ajoute la suite d'octets n, v dans B.

Par exemple:
    • avec A = [5, 5, 5, 5, 5, 5, 4, 4, 4], B = [6, 5, 3, 4]
    • avec A = [3, 3, 3, 2, 2, 1, 4, 4, 1, 1, 1, 3], B = [3, 3, 2, 2, 1, 1, 2, 4, 3, 1, 1, 3]  (Oui, B est plus long que A...)
    • avec A = [2] * 600 + [0, 0], B = [255, 2, 255, 2, 90, 2, 2, 0]

    Lors de la décompression il faut vérifier que le fichier B a été effectivement compressé par RLE.  L'algorithme de décompression d'un fichier compressé est alors le suivant:

On part d'un fichier compressé B que l'on parcourt et transforme en le fichier d'origine A par les règles de transformation suivantes:
    (1) On initialise A à la liste vide.
    (2)  Pour chaque paire (n, v) d'octets consécutifs de B, on ajoute à A n octets consécutifs de valeur v. L'octet n doit être non nul et l'octet v doit exister.

2) Algorithmes

Q1) Ecrire une fonction RLE_liste_compression(A) calculant, pour une liste d'entiers A, la liste d'entiers B résultat de la compression par RLE de A.
  On peut écrire cette fonction avec une boucle while ou une boucle for.  Il est interdit d'utiliser "break". Vérifier que:
    • avec A = [5, 5, 5, 5, 5, 5, 4, 4, 4], B = [6, 5, 3, 4]
    • avec A = [3, 3, 3, 2, 2, 1, 4, 4, 1, 1, 1, 3], B = [3, 3, 2, 2, 1, 1, 2, 4, 3, 1, 1, 3]  (Oui, B est plus long que A...)
    • avec A = [2] * 600 + [0, 0], B = [255, 2, 255, 2, 90, 2, 2, 0]

Q2) Ecrire une  fonction RLE_liste_decompression(B) qui renvoie pour une liste d'entiers B compressée par RLE, la liste d'entiers A telle que RLE_liste_compression(A) = B. Vérifier que:
    • avec B = [1, 2, 1, 1, 4, 5, 1, 3], alors A = [1, 1, 5, 5, 5, 5, 3]
    • avec B = [3, 1, 2, 1, 4, 0], alors A = [3, 3, 3, 1, 1, 0, 0, 0, 0]

  On peut maintenant compresser et décompresser les fichiers avec les deux fonctions précédentes et les fonctions de lecture et écriture données dans le II).

Q3) Ecrire une fonction RLE_fichier_compression(nom_fichier), avec nom_fichier une chaîne de caractères qui:
    • calcule et enregistre (dans le même répertoire courant) le fichier comp_RLE_nom_fichier résultat de la compression RLE du fichier ayant pour nom nom_fichier
    • calcule et affiche le taux de compression TC RLE en %, (TC est le rapport des longueurs du fichier compressé et du fichier original).

Q4) On veut compresser les fichiers de données. Vérifier que:

fichiers = ("ab.txt", "abc.txt", "boule de suif.txt", "etoile_BMP.bmp",
"etoile_JPG.jpg","soleils.bmp")
for f in fichiers:
    RLE_fichier_compression(f)
# renvoie
TC RLE de ab.txt = 100.3 %
TC RLE de abc.txt = 133.5 %
TC RLE de boule de suif.txt = 196.2 %
TC RLE de etoile_BMP.bmp = 4.481 %
TC RLE de etoile_JPG.jpg = 196.9 %
TC RLE de soleils.bmp = 199.7 %

  Q4a) Vérifier que seuls les fichiers textes compressés restent exécutables  et “proches” des originaux: pourquoi pas les autres ?
  Q4b) Justifier les taux de compression des fichiers “ab.txt” et “abc.txt”.
  Q4c) Pourquoi le taux de compression de “etoile_BMP.bmp” est-il excellent ?
  Q4d) Pourquoi les taux de compression des autres fichiers sont-ils voisins de 200 % ?

Q5) Ecrire une fonction RLE_fichier_decompression(nom_fichier), avec nom_fichier une chaîne de caractères qui calcule et enregistre (dans le même répertoire courant) le fichier dec_nom_fichier résultat de la décompression par RLE du fichier ayant pour nom nom_fichier.
Vérifier que les fichiers compressés en Q4) sont bien décompressés et que l'on retrouve bien le fichier d'origine

IV) Compression Ziv et Lempel

1) Description

  L'algorithme de Ziv et Lempel a été proposé par Abraham Lempel et Jacob Ziv en 1977. Cet algorithme de compression sans perte pose les bases de la plupart des algorithmes de compression par dictionnaire, à tel point qu'on parle couramment d'algorithme LZ pour désigner un algorithme de compression par dictionnaire.
  LZ77 est un algorithme de compression par dictionnaire utilisant une fenêtre glissante ; les motifs déjà rencontrés dans la fenêtre sont remplacés par une référence à leur première apparition. Voilà sa description précise:

  Etant donnés une liste A de longueur n et i < j deux entiers de {0,..., n-1}, on appelle motif_max(A, i, j) le plus grand entier k ∈ {0,...,255} tel que A[i: i + k] = A[j: j + k], c'est à dire tel que ∀ q ∈ {0,1,...,k-1}, A[i + q] = A[j + q].
  motif_max(A, i, j) est donc le plus nombre d'éléments de A identiques à partir des positions i et j.

Par exemple, si A = [1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 1, 4], alors:
    motif_max(A, 1, 2) = 0 ; motif_max(A, 0, 3) = 2 ; motif_max(A, 1, 6) = 4   

On part d'un fichier (une liste d'octets) A de longueur n que l'on parcourt et transforme en un fichier (une liste d'octets) B par les règles de transformation suivantes:
    (1) On initialise B aux trois premiers octets de A (ou moins si len(A) < 3) et j à j = 3.
    (2) Tant que  j < n - 1
        (2a)  On cherche l'entier i ∈ {1,2,...,255} tel que k = motif_max(j - i, j) soit maximum (il faut donc aussi que i ≤ j). En cas d'égalités, on choisit le plus petit entier i.
        (2b1) Si  j + k  < n  on ajoute à B le triplet (i, k, v) avec v = A[j + k]
        (2b2) Si  j + k  = n  on ajoute à B le couple (i, k)        
        (2c) On pose j = j + k + 1
    (3) Si  j = n - 1 on ajoute à B l'octet v = A[n -1]
Le dernier ajout à la liste B peut donc être:
    (F1) Un octet v ajouté en (3)
    (F2) Un couple (i, k) ajouté en (2b2)
    (F3) Un triplet (i, k, v) ajouté en (2b1)    

  Par exemple:

Avec A = [1] * 300 + [2, 2] :  
j (i,k,v) B
[1,1,1]
3 (1,255,1) [1,1,1,1,255,1]
259 (1,41,2) [1,1,1,1,255,1,1,41,2]
301 [1,1,1,1,255,1,1,41,2,2]
  Fin du type (F1). B=[1,1,1,1,255,1,1,41,2,2]

Avec A = [1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2] :
j (i,k,v) B
[1,2,3]
3 (3,2,1) [1,2,3,3,2,1]
5 (5,9,x) [1,2,3,3,2,1,5,9]
  Fin du type (F2). B = [1,2,3,3,2,1,5,9]

Avec A = [1, 1, 1, 1, 1,4] :
j (i,k,v) B
[1,1,1]
3 (1,2,4) [1,1,1,1,2,4]
  Fin du type (F3). B = [1,1,1,1,2,4]

L'algorithme de décompression d'un fichier compressé par LZ est alors le suivant:

On part d'un fichier compressé B de longueur n que l'on parcourt et transforme en le fichier d'origine A par les règles de transformation suivantes:
    (1) On initialise A aux trois premiers octets de B (ou moins si len(B) < 3) et on pose jA = jB = 3
    (2) Tant que  jB + 1 < n:
        (2a) On lit les deux octets (i, k) = (B[jB], B[jB + 1]):
        (2b) On ajoute la liste A[jA - i: jA - i + k] à la liste A
        (2c) Si  jB + 2 < n , on ajoute l'octet v = B[jB + 2] à la liste A
        (2d) On pose jB = jB + 3 et jA = jA + k + 1
    (3) Si jB = n - 1, on ajoute B[jB] à la liste A            

2) Algorithmes

Q6) Ecrire une fonction  motif_max(A, i, j), avec A liste d'octets et i, j deux entiers tels que 0 ≤ i < j < n (avec n = len(A)) qui calcule le plus grand entier k < 256 tel que A[i: i + k] = A[j: j + k], c'est à dire tel que ∀ q ∈ {0,1,...,k-1}, A[i + q] = A[j + q].
  Vérifier que:

A = [1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 3, 1, 4]
print(motif_max(A, 1, 2), motif_max(A, 0, 3), motif_max(A, 1, 6))→ 0 2 4
A = [2]*100 + [1]*100
print(motif_max(A, 3, 5)) → 95
A = [0]*300
print(motif_max(A, 3, 5)) → 255

Q7) Ecrire une fonction couple_motif_max(A, j),  avec A liste d'octets et j entier tels que 0 ≤ j < n (avec n = len(A)) qui calcule la liste [i, k] d'entiers tel que k = motif_max(j - i, j) soit maximum avec les contraintes:   i ∈ {1,2,...,255}, i le plus petit en cas d'égalité et retour immédiat si k = 255 .

Par exemple:

A = [1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2]
print(couple_motif_max(A, 1), couple_motif_max(A, 3), couple_motif_max(A, 8))
#renvoie
[1, 0] [3, 2] [5, 7]

Q8) Ecrire une fonction LZ_liste_compression(A)  calculant la liste B résultat de la compression de la liste A par l'algorithme de Ziv et Lempel.  Vérifier que:

a = [1] * 300 + [2, 2]
b = [1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2]
c = [1, 1, 1, 1, 1,4]
d = [1, 2, 3, 4, 5]
for s in (a, b, c, d):
    print(LZ_liste_compression(s))
#renvoie
[1, 1, 1, 1, 255, 1, 1, 41, 2, 2]
[1, 2, 3, 3, 2, 1, 5, 9]
[1, 1, 1, 1, 2, 4]
[1, 2, 3, 1, 0, 4, 5]

Q9) Ecrire une fonction LZ_liste_decompression(B) calculant la liste A dont la compression par l'algorithme  LZ est la liste B.
Vérifier sur les exemples précédents que LZ_liste_decompression(LZ_liste_compression(X))  = X.

a = [1] * 300 + [2, 2]
b = [1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2]
c = [1, 1, 1, 1, 1,4]
d = [1, 2, 3, 4, 5]
for s in (a, b, c, q):
    print(LZ_liste_decompression(LZ_liste_compression(s)) == s)
# renvoie un quadruple True   

Q10) Ecrire une fonction LZ_fichier_compression(nom_fichier), avec nom_fichier une chaîne de caractères qui:
    • calcule et enregistre (dans le même répertoire courant) le fichier comp_LZ_nom_fichier résultat de la compression LZ du fichier ayant pour nom nom_fichier
    • calcule et affiche le taux de compression TC LZ en %, (TC est le rapport des longueurs du fichier compressé et du fichier original).

Q11) On veut compresser les fichiers de données. Vérifier que:

fichiers = ("ab.txt", "abc.txt", "boule de suif.txt", "etoile_BMP.bmp",
"etoile_JPG.jpg","soleils.bmp")
for f in fichiers:
    LZ_fichier_compression(f)
# renvoie
TC LZ de ab.txt =  32.2 %
TC LZ de abc.txt = 49.55 %
TC LZ de boule de suif.txt = 96.88 %
TC LZ de etoile_BMP.bmp = 2.864 %
TC LZ de etoile_JPG.jpg = 155.6 %
TC LZ de soleils.bmp = 73.45 %

  Q11a) Vérifier que seuls les fichiers textes compressés restent exécutables mais ne ressemblent à rien.
  Q11b) Justifier les taux de compression des fichiers “ab.txt” et “abc.txt” et “boule de suif.txt”.
  Q11c) Pourquoi le taux de compression de “etoile_BMP.bmp” est-il encore meilleur qu'avec la compression RLE ?
  Q11d) Pourquoi le taux de compression de “etoile_JPG.jpg” est-il déplorable (mais moins pire qu'avec RLE) ?
  Q11e) Pourquoi le taux de compression de “soleils.bmp” est-il correct, alors qu'il était exécrable avec RLE ?

Q12) Ecrire une fonction LZ_fichier_decompression(nom_fichier), avec nom_fichier une chaîne de caractères qui calcule et enregistre (dans le même répertoire courant) le fichier dec_nom_fichier résultat de la décompression par LZ du fichier ayant pour nom nom_fichier.
  Vérifier que les fichiers compressés en Q11) sont bien décompressés et que l'on retrouve bien le fichier d'origine

V) Bilan

  Vous l'avez compris, dès qu'un fichier comporte un grand nombre d'octet isolés (c'est le cas de tout fichier texte et de beaucoup d'autres), l'algorithme de compression RLE n'est pas efficace.
  Mais, associé à un algorithme comme la Transformation de Burrows-Wheeler (objet d'un autre TD) qui modifie l'ordre des octets d'un fichier et a tendance à provoquer des regroupements, cet algorithme de compression devient intéressant.

  L'algorithme de compression LZ compresse plus que l'algorithme RLE, mais il est beaucoup plus lent (la décompression est rapide). Lorsque le fichier ne présente pas de redondances, il devient inefficace: le fichier compressé est plus gros que le fichier d'origine....

© 2015 - Eric Obermeyer      Corrigé