Consignes

La note ne valide pas seulement le résultat de votre programme, mais également son style :

Vérifiez ces points avant de demander à votre intervenant de valider votre code.

Liens utiles

1. LZ78, méthode

1.1. Prélimaire

L'algorithme LZ78 est un algorithme de compression qui permet de remplacer des suites de caractères par leur numéro dans un "dictionnaire" de mots déjà rencontrés.

Pour programmer la méthode de compression LZ78, il faut pouvoir :

La fonction suivante permet de faire les deux même temps. Programmez la fonction 

def position(T, s):
    """renvoie la position de la chaine s dans la liste T
    Si s n'appartient pas à la liste T, la fonction renvoie -1 à la place.

    T: liste de chaine de caractères
    s: chaine de caractère
    résultat: nombre entier
    """

1.2. Rappel : l'algorithme LZ78

L'algorithme LZ78 permet de compresser une chaine (appelée texte dans la suite). Il fonctionne de la manière suivante :

  1. On initialise une liste appelée dico à [""] : c'est une liste de chaine déjà vues.

  2. On récupère les caractères de texte, un par un, en construisant une chaine de caractère appelée mot_courant.

    Le but est de trouver le premier caractère c de texte qui vérifie

    • mot_courant est dans dico,

    • mot_courant+c n'est pas dans dico.

  3. Lorsqu'on a trouvé ce c, on ajoute deux cases à la fin du résultat :

    • on ajoute la position de mot_courant dans dico à la fin du résultat,

    • on ajoute le caractère à la fin du résultat,

    On ajoute également mot_courant+c à la fin de dico (car cela correspond à une chaine vue), et on réinitialise mot_courant.

  4. On recommence au point 2 à partir de la position suivant le caractère c, jusqu'à arriver à la fin de la chaine texte.

Le résultat est donc une liste alternée d'entiers et de caractères.

Pour ajouter une case s à la fin d'une liste T, il faut utiliser 

T.append(s)

Le code, à trous, de la fonction de compression est le suivant : 

def lz78_compresse(texte):
    """applique l'algorithme de compression LZ78 sur la chaine ``texte``

    Le résultat est une liste [entier, caractère, entier, caractère, ...] se
    terminant soit sur un caractère, soit sur un entier.

    texte: chaine de caractères
    résultat: liste alternée d'entiers et caractères
    """
    resultat = []        # liste alternée de nombres / lettres
    ...
    ...     # initialisation des variables dico, et mot_courant
    for i in range(0, len(texte)):
        c = texte[i]
        if ...:  # on teste si mot_courant+c est dans la liste dico
            mot_courant = mot_courant + c
        else:
            ...
            ...  # on fait les étapes du point 3. de l'algorithme
            ...
    ...	    # gestion du dernier mot_courant
    return resultat

1.3. Compression

Complétez le code de la fonction lz78_compresse donné ci dessus : 

def lz78_compresse(texte):
    """applique l'algorithme de compression LZ78 sur la chaine ``texte``

    Le résultat est une liste [entier, caractère, entier, caractère, ...] se
    terminant soit sur un caractère, soit sur un entier.

    texte: chaine de caractères
    résultat: liste alternée d'entiers et caractères
    """

Par exemple, vous devriez obtenir 

>>> lz78_compresse("abracadabra")
[0, 'a', 0, 'b', 0, 'r', 1, 'c', 1, 'd', 1, 'b', 3, 'a']
>>> lz78_compresse("oleole")
[0, 'o', 0, 'l', 0, 'e', 1, 'l', 3]

Attention, lorsque la fonction atteint la fin du texte, si la chaine mot_courant est non-vide et est dans le dictionnaire, on ajoute simplement sa position (c'est ce qui se passe lors de la compression de "oleole").

1.4. Décompression

L'algorithme de décompression fonctionne en sens inverse. À partir de la liste alternée, appelée code, il faut reconstruire le dictionnaire au fur et à mesure:

  1. On initialise une liste appelée dico à [""] : c'est une liste de chaines déjà vues.

  2. On parcourt les cases de code :

    • pour les cases d'indice pair, il s'agit d'un nombre, et il faut ajouter le mot de dico correspondant dans le résultat,

    • pour les cases d'indice impair, il s'agit d'un caractère et il faut

      • ajouter le caractère dans le résultat,

      • ajouter le mot précédent, avec ce caractère en plus, dans la liste dico.

Programmez la fonction correspondante 

def lz78_decompresse(code):
    """applique l'algorithme de décompression LZ78 sur la liste ``code``

    code: liste alternée d'entiers et caractères
    résultat: chaine de caractères
    """

Par exemple, 

>>> lz78_decompresse([0, 'a', 0, 'b', 0, 'r', 1, 'c', 1, 'd', 1, 'b', 3, 'a'])
'abracadabra'
>>> lz78_decompresse([0, 'o', 0, 'l', 0, 'e', 1, 'l', 3])
'oleole'

1.5. Tests

Écrivez une procédure pour tester que votre fonction de décompression ... décompresse correctement. Pour ceci, il suffit de

  1. compresser un chaine,

  2. décompresser le résultat,

  3. le comparer à la chaine initiale. 

def test_lz78(texte):
    """vérifie que la décompression d'une chaine compressée est bien la chaine initiale

    texte: chaine de caractère
    """

On aura par exemple : 

>>> test_lz78("abracadabra")
    chaine de départ : 'abracadabra'
   résultat compressé : [0, 'a', 0, 'b', 0, 'r', 1, 'c', 1, 'd', 1, 'b', 3, 'a']
résultat décompressé : 'abracadabra'
=== OK...

Si le résultat n'est pas égal à la chaine de départ, la procédure affichera plutôt 

*** PROBLÈME : le résultat décompressé est différent de la chaine de départ !

2. LZ78, pratique

2.1. Octets pour compresser et décompresser

Compression

Pour pouvoir vraiment tester l'algorithme de compression, il faut pouvoir transformer la liste alternée de nombres / caractères en suite d'octets. La fonction suivante faite exactement ceci : 

def octets(T):
    """transforme une liste alternée d'entiers et caractères en tableau d'octets"""
    r = bytearray()
    for e in T:
        if isinstance(e, int):
            if not 0 <= e < 256:
                raise RuntimeError("*** Problème, l'entier {} n'est pas compris entre 0 et 255 !".format(e))
            r.append(e)
        elif isinstance(e, str):
            if len(e) != 1:
                raise RuntimeError("*** Problème, les caractères doivent être donnés un par un !")
            try:
                r.extend(e.encode("ASCII"))
            except UnicodeEncodeError:
                raise RuntimeError("*** Problème, '{}' n'est pas un caractère ASCII !".format(repr(e)))
        else:
            raise RuntimeError("*** Problème, '{}' n'est ni un entier, ni un caractère !".format(repr(e)))
            sys.exit(-1)
    return r

(La plupart des lignes de cette fonction servent à afficher des messages d'erreurs lisibles...)

Ajouter cette fonction dans votre fichier et recopier le code de la fonction lz78_compresse en ajoutant un appel à la fonction octets pour écrire la fonction 

def lz78_compresse_bin(texte):
    """applique l'algorithme de compression sur la chaine ``texte``

    texte: chaine de caractères
    résultat: liste d'octets.
    """

Vous devriez obtenir 

>>> lz78_compresse_bin("abracadabra")
bytearray(b'\x00a\x00b\x00r\x01c\x01d\x01b\x03a')

Le résultat est un tableau d'octet ("bytearray") où chaque octet est affiché :

Décompression

La liste d'octets obtenue avec la fonction lz78_compresse peut se manipuler comme une liste d'entier : 

>>> bs = lz78_compresse_bin("abracadabra")
>>> print(bs)
bytearray(b'a\x00b\x00r\x01c\x01d\x01b\x03a')
>>> bs[0]
0
>>> bs[1]
97
>>> bs[11]
3

La case n° 1 vaut 97, qui est le code ASCII de la lettre a minuscule.

Pour obtenir un caractère à partir d'un octet (c'est à dire son code ASCII), vous pouvez utiliser la fonction suivante : 

def ascii(n):
    """transforme un octet en caractère ASCII"""
    try:
        return bytes([n]).decode(encoding="ASCII")
    except UnicodeDecodeError:
        raise RuntimeError("*** Problème, '{}' ne correspond pas à un caractère ASCII !".format(n))

Recopier le code de la fonction lz78_decompresse et ajoutez des appels à la fonction ascii pour pour obtenir la fonction 

def lz78_decompresse_bin(code):
    """applique l'algorithme de décompression LZ78 sur ``code``

    code: liste d'octets
    résultat: chaine de caractères
    """

Testez vos deux fonctions en écrivant une fonction test_lz78_bin similaire à la fonction test_lz78.

2.2. Un entier / un octet ?

Testez votre fonction lz78_compresse_bin sur la chaine "aa...aa" avec 30000 a, puis avec 35000 a : 

>>> lz78_compresse_bin("a"*30000)
???
>>> lz78_compresse_bin("a"*35000)
???

Lorsque le dictionnaire devient trop grand (plus de 256 cases), les numéros de positions ne tiennent plus forcément sur 1 octet. Il faut dans ce cas commencer à écrire les numéros de positions sur 2 octets. Ainsi, la liste alternée 

[ ..., 1000, 'v', 100, 'l', ... ]

deviendra 

[ ..., 3, 232, 'v', 0, 100, 'l'... ]

car 1000 = 3*256 + 232 et 100 = 0*256 + 100.

On obtient le 3 comme 1000 // 256 (division entière) et le 232 comme 1000 % 256 (modulo).

Attention, lorsque la taille de la liste dépasse 256, tous les indices sont notés sur 2 octets. On ne modifie par contre pas les indices déjà calculés pendant le début de l'algorithme.

Modifiez votre fonction lz78_compresse_bin pour qu'elle ajoute deux entiers (au lieu d'un seul) pour chaque position lorsque le dictionnaire contient plus que 256 éléments.

Vérifiez que vous obtenez le bon résultat : 

>>> lz78_compresse_bin("a"*35000)
bytearray(b'\x00a\x01a\x02a\x03a\x04a\x05a\x06a\x07a\x08a\ta\na\x0ba\x0ca\ra\x0ea\x0fa\x10a\x11a\x12a\x13a
\x14a\x15a\x16a\x17a\x18a\x19a\x1aa\x1ba\x1ca\x1da\x1ea\x1fa a!a"a#a$a%a&a\'a(a)a*a+a,a-a.a/a0a1a2a3a4a5a6a
7a8a9a:a;a<a=a>a?a@aAaBaCaDaEaFaGaHaIaJaKaLaMaNaOaPaQaRaSaTaUaVaWaXaYaZa[a\\a]a^a_a`aaabacadaeafagahaiajaka
lamanaoapaqarasatauavawaxayaza{a|a}a~a\x7fa\x80a\x81a\x82a\x83a\x84a\x85a\x86a\x87a\x88a\x89a\x8aa\x8ba\x8ca
\x8da\x8ea\x8fa\x90a\x91a\x92a\x93a\x94a\x95a\x96a\x97a\x98a\x99a\x9aa\x9ba\x9ca\x9da\x9ea\x9fa\xa0a\xa1a
\xa2a\xa3a\xa4a\xa5a\xa6a\xa7a\xa8a\xa9a\xaaa\xaba\xaca\xada\xaea\xafa\xb0a\xb1a\xb2a\xb3a\xb4a\xb5a\xb6a
\xb7a\xb8a\xb9a\xbaa\xbba\xbca\xbda\xbea\xbfa\xc0a\xc1a\xc2a\xc3a\xc4a\xc5a\xc6a\xc7a\xc8a\xc9a\xcaa\xcba
\xcca\xcda\xcea\xcfa\xd0a\xd1a\xd2a\xd3a\xd4a\xd5a\xd6a\xd7a\xd8a\xd9a\xdaa\xdba\xdca\xdda\xdea\xdfa\xe0a
\xe1a\xe2a\xe3a\xe4a\xe5a\xe6a\xe7a\xe8a\xe9a\xeaa\xeba\xeca\xeda\xeea\xefa\xf0a\xf1a\xf2a\xf3a\xf4a\xf5a
\xf6a\xf7a\xf8a\xf9a\xfaa\xfba\xfca\xfda\xfea\xffa\x01\x00a\x01\x01a\x01\x02a\x01\x03a\x01\x04a\x01\x05a
\x01\x06a\x01\x07a\x00\x14')

Modifiez votre fonction lz78_decompresse_bin pour qu'elle récupère deux octets dans la liste pour chaque position dès que la taille du dictionnaire dépasse 256.

Attention, vous ne pourrez plus parcourir code avec une boucle for en faisant une distinction pair/impair: il faudra faire une boucle while. Chaque passage dans la boucle devra :

  • lire 1 ou 2 octets pour former le nombre,

  • lire un octet pour former le caractère.

Testez votre décompression en utilisant votre fonction test_lz78_bin sur la chaine "a"*35000.

BONUS

Lorsque la taille du dictionnaire dépasse 256^{2}=65536, les numéros de positions doivent être stockés sur 3 octets au lieu de 2, etc.

Modifiez vos fonctions pour qu'elles fonctionnent dans tous ces cas également. (Il faudra pour ceci décomposer les nombres en base 256...)

3. LZ78, fichiers et améliorations

3.1. Fichiers

La fonction suivantes permet de stocker le résultat de lz78_compresse_bin dans un fichier : 

def lz78_compresse_fichier(fichier):
    """compresse un fichier en utilisant l'algorithme LZ78
    Le résultat est stocké dans un fichier dont le nom est obtenu en ajoutant
    l'extension ".Z78" au nom de fichier donné.
    fichier: nom de fichier (chaine de caractère)
    """
    texte = open(fichier, mode="r").read()
    code = lz78_compresse_bin(texte)
    f = open(fichier + ".Z78", mode="wb")
    f.write(code)
    f.close()

    print("Fichier {} compressé avec succès.".format(fichier))
    print("avant : {} octets".format(len(texte)))
    print("après : {} octets".format(len(code)))

    return code

La fonction suivante décompresse un fichier : 

def lz78_decompresse_fichier(fichier):
    """decompresse un fichier en utilisant l'algorithme LZ78
    Le résultat est stocké dans un fichier dont le nom est obtenu en ajoutant
    l'extension ".A78" au nom de fichier donné.
    fichier: nom de fichier (chaine de caractère)
    """
    code = open(fichier, mode="rb").read()
    texte = lz78_decompresse_bin(code)
    f = open(fichier + ".A78", mode="w")
    f.write(texte)
    f.close()

    print("Fichier {} décompressé avec succès.".format(fichier))
    print("avant : {} octets".format(len(code)))
    print("après : {} octets".format(len(texte)))

    return texte

Testez ces fonctions (qui utilisent vos fonctions lz_78_compresse_bin et lz78_decompresse_bin) sur :

Qu'en pensez-vous ?

3.2. Améliorations (BONUS)

C'est la fonction lz78_compresse_bin qui prend le plus de temps. Ceci vient du fait que pour chercher si un mot est dans le dictionnaire (fonction position), il faut parcourir tout le dictionnaire à chaque fois.

On peut remplacer la fonction position par une fonction plus efficace en remplaçant la liste des chaines déjà rencontrés par un dictionnaire (structure de données spéciale).

Comme Python sait chercher une clé très rapidement, nous allons utiliser un dictionnaire où :

Ainsi, au lieu d'obtenir une liste 

['', 'a', 'b', 'r', 'ac', 'ad', 'ab', 'ra']

lors de la compression de "abracadabra", on obtiendra le dictionnaire 

{'': 0, 'ab': 6, 'ra': 7, 'ad': 5, 'ac': 4, 'a': 1, 'r': 3, 'b': 2}

La case de clé 'ra' a la valeur 7 car ce mot est arrivé en 7ème. (Ce mots est en position 7 dans la liste précédente.)

BONUS

Recopiez le code de la fonction lz78_compresse_bin en incorporant les changements ci dessus pour obtenir la fonction 

def lz78_compresse_opt(s):
    """applique l'algorithme de compression par dictionnaire LZ78 sur la chaine s (version optimisée)

    s: chaine de caractères
    résultat: liste d'octets.
    """

BONUS

Remplacez l'appel à l78_compresse_bin dans lz78_compresse_fichier par un appel à lz78_compresse_opt et essayez de compresser le fichier moby.txt à nouveau.

Que constatez vous ?

Le dictionnaire créé pour compresser moby.txt a une taille supérieure à 65536. Il faut donc avoir fait la question (bonus) 11 pour pouvoir tester sur ce fichier.

BONUS

Faut-il faire des changements à la fonction lz78_decompresse_bin pour décompresser le résultat de la fonction précédente ?

Décompressez le fichiers moby.txt.LZ78 et vérifiez que le contenu du fichier moby.txt.LZ78.AZ78 est bien le même que moby.txt

Essayer aussi de compresser vague.ppm, une image (format .ppm ASCII) plus grande que la précédente. Quel est le taux de compression ?