Consignes

Vous devrez utiliser l'interface TPLab pour envoyer vos TP aux encadrants de TP.

Liens utiles

• la page du langage Python,
• la documentation des bibliothèques standards,

• email des enseignants : Pierre.Hyvernat@univ-savoie.fr, Rodolphe.Lepigre@univ-savoie.fr, Christophe.Raffalli@univ-savoie.fr

1. LZ78, méthode

1.1. Prélimaire

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 des chaines déjà vues.

2. On récupère les caractères de texte, un par un, en construisant une liste de caractère appelée mot_courant.
   Le but est de trouver le premier caractère c de texte qui vérifie
   • mot_courant+c n'est pas dans dico
   • et mot_courant est 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 mot_courant+c à la fin de dico,
   • on réinitialise la 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.

T.append(s)

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

def lz78_compresse(texte):
    """applique l'algorithme de compression par dictionnaire 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 = []        # variable contenant le résultat, càd une 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

def lz78_compresse(texte):
    """applique l'algorithme de compression par dictionnaire 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
    """

>>> 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]

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 des 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
     1. ajouter le caractère dans le résultat,
     2. ajouter le mot précédent, avec ce caractère en plus, dans la liste dico.

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

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

>>> 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

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
    """

>>> 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...

*** 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...)

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

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

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

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')
>>> b[0]
0
>>> b[1]
97
>>> b[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))

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

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

2.2. Un entier / un octet ?

>>> 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).

>>> 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')

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

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ù :

• les clés sont les chaines déjà rencontrées,
• les valeurs correspondent à la position.

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.)

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.
    """