LZ78 et LZW : la compression par dictionnaire

Contrairement à LZ77, LZ78 est une méthode de compression par dictionnaire. Contrairement à la compression par fenêtre glissante, où on fait référence à des extraits du contenu déjà décompressé, la compression par dictionnaire stocke les extraits de contenu à répéter « à part ».

Le principe d’un dictionnaire est de faire correspondre un code (une suite d’octets pré-définie ou en tous cas déjà connue) à un contenu donné. En jargon technique, on dit aussi qu’on associe des clefs (les codes) à des valeurs (le contenu).

Les deux méthodes ne sont pas tellement « meilleures » l’une que l’autre, c’est juste une approche différente. On peut combiner les deux, comme nous le verrons plus tard.

Un soucis de LZ77 était que la fenêtre glissante était, justement, glissante : quand on sortait de la fenêtre parce que le contenu décompressé devenait trop large, on ne pouvait plus le répéter (par principe, le décompresseur l’avait déjà oublié).

Avec LZ78, un dictionnaire se constitue progressivement, et automatiquement au fur et à mesure que des données sont compressées ou décompressées. Il n’est donc pas partagé explicitement entre le compresseur et le décompresseur, chacun le recalcule de son côté.

Avec LZ77, on envoyait des tuples (position, taille, donnée). Avec LZ78, on envoie des tuples (code de dictionnaire, donnée).

Au départ, il n’y a qu’un seul code dans le dictionnaire (il représente une chaîne vide). À chaque nouvelle tuple envoyée, une nouvelle entrée de dictionnaire se créé, constituée de la valeur de dictionnaire référencée (s’il y en a une) + de la donnée, concaténées ensembles.

C’est ainsi que notre dictionnaire se construit au fur et à mesure.

Avec LZ77, les données décompressées étaient constituées comme ceci :

• Un extrait de la fenêtre, d’après sa position et sa taille (s’il y en a un)
• Une donnée
• Un extrait de la fenêtre, d’après sa position et sa taille (s’il y en a un)
• Une donnée
• Un extrait de la fenêtre, d’après sa position et sa taille (s’il y en a un)
• Une donnée
• etc.

Avec LZ78, les données décompressées sont constituées comme ceci :

• Une entrée de dictionnaire, d’après son code (s’il y en a une)
• Une donnée
• Une entrée de dictionnaire, d’après son code (s’il y en a une)
• Une donnée
• Une entrée de dictionnaire, d’après son code (s’il y en a une)
• Une donnée
• etc.

Avec LZ77, la fenêtre glissante se remplissait progressivement et toute seule. Avec LZ78, le dictionnaire se remplit progressivement et tout seul.

Avec LZ78, quand le dictionnaire est plein, il ne se remplit plus. Ce n’est pas une résolution optimale du problème de la fenêtre glissante, du coup ! Mais si les motifs qui se répètent sont tous présents dès le début du fichier, c’est intéressant.

Bien sûr !

Imaginions que nous ayons une chaîne "ABABABCABCDE" que nous avons compressé, et que nous voulons décompresser :

LZ78 est lui aussi un algorithme « théorique », on ne va pas s’étendre dessus.

Comme LZ77 a eu son premier pendant « concret » populaire avec LZSS, LZ78 a débouché en 1989 sur LZW (le W est l’initiale d’un troisième chercheur, Terry Welch) : celui-ci a donné lieu à plusieurs applications majeures :

• Le format .GIF, qui fut le grand format de la compression d’images en ligne durant des années (même si aujourd’hui .PNG l’a détrôné - sauf pour les animations bien sûr !)
• Le format .TIFF, qui fut un format populaire également. Créé au milieu des années 1980, il est plus vieux que le GIF, et fut créé par une entreprise qui a par la suite été rachetée par Adobe. Il supporte plusieurs formats de compression, et de grand organismes de normalisation ont aussi créé des normes dérivées.
• Le format .Z, un format créé par l’utilitaire compress pour UNIX (utilisé comme équivalent de ZIP dans les années 1980, et les systèmes UNIX étaient grosso modo les ancêtres de Linux). On n’en voit plus trop aujourd’hui (quoique la dernière et seule fois que j’en ai vu récemment, c’était dans un fichier des entreprises de l’État qui a été rendu public il n’y a pas si longtemps ! )

GIF a été créé en 1987 par un concurrent d’AOL, dénommé CompuServe. Le soucis, c’est qu’un brevet sur LZW était détenu par une autre entreprise, Unisys, qui a alors très maladroitement menacé de nombreux sites et logiciels utilisant GIF afin d’obtenir le paiement de taxes.

Cela a fait grand bruit chez nos amis californiens à l’époque. Aujourd’hui, le brevet a expiré en 2003 et ce n’est plus que de l’histoire ancienne (et en France, ça n’aurait pas pu arriver puisque les brevets logiciels n’existent pas, de toutes façons !). Mais cela a mené à la création de PNG et à des campagnes virulentes contre GIF et les brevets logiciels.

Avec LZW, le fichier compressé contient simplement une suite de codes : c’est le décompresseur qui reconstitue le dictionnaire, au fur et à mesure de la décompression.

Au départ, il n’existe que les codes de 0 à 255 : ils correspondent à tous les octets possibles. Les premiers codes sont donc forcément des octets bruts. Mais à partir du deuxième code, un nouveau code va être constitué automatiquement en combinant les deux derniers codes lus : par exemple, si le fichier commence par "A" puis "B", et que les codes créés automatiquement commencent à 257, une entrée de dictionnaire dont le code sera "257" et dont la valeur sera "AB" sera créée automatiquement.

Si après "A" et "B", le fichier contient "C", alors une entrée de dictionnaire dont le code sera "258" et la valeur sera "BC" sera créée, etc.

Imagions que notre fichier commence par "ABCBCD". Nos trois premiers codes seront ceux correspondant aux lettres ASCII "A", "B", "C", mais ensuite, il y aura le code "258", qui a été créé automatiquement par le décompresseur, et vaudra donc "BC".

À ce moment-là, le décompresseur créé un code "259" qui vaut "CB" (la valeur du précédent code + le premier octet du code actuel - on ne prend que le premier octet du code actuel, c’est une subtilité qui nous permet de s’assurer que nos valeurs de dictionnaire ne grandissent que d’un octet à la fois : ainsi, on saura reconnaître plus de motifs).

Quel sera le cinquième code ? Celui qui correspondra à la lettre ASCII "D". Mais lorsque le décompresseur le lira, il va créer un code "260" qui contiendra "BCD" (logique, c’est la combinaison des deux derniers codes lus, donc du code "258" qui vaut "BC" et du code "D") !

Si par la suite notre fichier contient "BCD", il suffira que le fichier à décompresser contienne donc le code "260", suite à quoi il sera créé un nouveau code qui vaudra 4 lettres, etc.

Si l’unité de base de compression est l’octet, et que notre dictionnaire est donc pré-rempli avec toutes les valeurs possibles de 0 à 255 (8 bits), alors de base nos codes feront 9 bits.

Quand il n’y aura plus de place pour stocker de nouveaux codes, alors la taille des codes augmentera automatiquement, par exemple d’1 bit. Leur taille maximale, après laquelle on n’alimente plus le dictionnaire, dépend des formats, mais est généralement de 12 ou 16 bits.

Quand la taille du dictionnaire est devenue déraisonnable, qu’il faut trop de bits pour encoder un code et que la compression ne devient plus intéressante en termes de ratio (c’est à dire d’efficacité), ou qu’il est compliqué de tout stocker, alors le dictionnaire va pouvoir émettre un code spécial (en général le code 256 qui est réservé à cet effet). Ce code aura pour effet de vider le dictionnaire et de le remettre à son état initial.

Voici un bref schéma du fonctionnement de LZW.

…

Nous allons maintenant entreprendre, pour nous exercer et parce que c’est l’implémentation répandue de LZW la plus « simple », de créer un fichier .Z.

.Z n’est pas un format d’archivage compressé comme .ZIP ou .RAR, mais juste de compression. C’est à dire que vous pouvez compresser un seul ficher à la fois avec, il ne contient pas une liste de fichiers.

Si on veut compresser un dossier avec .Z, on va donc utiliser un format d’archivage non-compressé (qui contiendra donc une arborescence de fichiers, de dossiers, leurs noms, leurs contenus, leurs permissions (qui peut écrire ?), etc.), comme .TAR, et on va le compresser dans un .Z. Cela pourra faire un fichier qu’on appellera .TAR.Z, ou encore .TAZ.

Si vous utilisez Linux, vous devez être familier à cette technique : vous devez voir passer des .TAR.GZ, des .TAR.XZ, des .TAR.BZ2… et notamment pour les logiciels. En lieu et place de cela, .ZIP ou .RAR, plus utilisées sous Windows, font les deux à la fois, archivage et compression. Sous Linux, il y avait aussi dans le temps un autre format plus ancien que .TAR qui s’appelait .CPIO.

Nous n’allons pas utiliser .TAR ici. Nous allons, comme dans le chapitre précédent, simplement décompresser une phrase.

Voici la phrase, compressée puis encodée en hexadécimal, que nous allons avoir à décompresser:

1f9d9045e88018762a0c083361d2081493a60d0b1062c23884f8a64e1b05c30e1944a810049c3963d0887c584620c18d0905da9153f16246941d194e8c38b3a5022261dccc01d1c6209d61aae8940191471ca04c3e2b0a8c53270d083a15e5b829a300a3c683294184ac4387a440384d77ea80c8268c98b256610a1cf3a64d9ba163d23c64eb76e8c9b45863367c48f361183420fe06467333e7ce366fdc682d36a98e9c876ae0b68523a78c1b323be184d9a900

Puisque nous allons traiter avec .Z (.GIF cela viendra plus tard !), je vais vous faire une brève description de ce format, et de ses champs. En informatique, un format n’est ni plus ni moins d’une suite d’informations (ici des octets) à interpréter dans l’ordre.

Les champs de l’en-tête sont :

Ensuite, il y a les données à décompresser.

Attelons-nous à notre code :

def mon_decompresseur_lzw(entree : bytes) -> bytes:

    assert entree[:2] == b'\x1F\x9D' # Vérifier la magic

    block_mode = bool(entree[2] >> 7)
    max_bits = entree[2] & 0b11111

On commence par interpréter l’en-tête LZW, dans l’ordre :

• On commence par vérifier que la magic est la bonne. Sinon, ce n’est pas le bon format. On utilise le mot-clef assert qui permet de vérifier une condition, et de déclencher une erreur si la condition n’est pas vérifiée : si entree[:2] == '\x1F\x9D' vaut False, alors une AssertionError sera déclenchée.
• Si tout va bien, super, on récupère le champ « block mode ». Pour ça, on prend le troisième octet, et on le décale de 7 bits vers la droite, il ne reste ainsi que le bit le plus haut. Au passage, on utilise la fonction bool() pour le convertir en booléen (une variable qui ne peut valoir que True ou False), juste parce que c’est plus clair que 0 ou 1.
• Ensuite, on récupère le champ « max bits ». La valeur ne peut pas être plus grande que 16, dont seuls les cinq derniers bits sont utilisés, j’ai écrit mon masque « 0b11111 » mais j’aurais aussi pu l’écrire « 0x1f » ou « 31 ».

    mon_dictionnaire = [bytes([octet]) for octet in range(256)] + ([None] if block_mode else [])

On implémente notre dictionnaire avec une liste d’entiers. On appelle la fonction range(256) qui va d’abord remplir notre variable avec tous les entiers possibles de 0 à 255. Si le champ « block mode » est activé, on ajoute aussi une entrée n° 256 qui ne vaudra rien (None), pour s’assurer que les entrées qui seront ajoutées ensuite commenceront bien à 257. Sinon, on n’ajoute rien.

    sortie = b''
    precedente_donnee_emise = None

On initialise nos variables d’état. On va bien sûr stocker notre contenu décompressé, mais aussi la précédente entrée de dictionnaire qu’on a émis, afin de pouvoir la combiner avec la suite plus tard dans notre dictionnaire, avec l’entrée suivante.

    position = 3
    position_depuis_le_dernier_changement_de_bits_par_code = position

    bits_non_lus = 0
    nombre_bits_non_lus = 0

    bits_par_code = 9
    anciens_bits_par_code = None
    
    while position < len(entree):

        octet = entree[position]
        
        bits_non_lus |= octet << nombre_bits_non_lus
        nombre_bits_non_lus += 8

Ça commence fort ! Dans cette nouvelle boucle, on va lire chaque octet du fichier à décompresser. On commence juste après l’en-tête (donc au 4ème octet). Comme un octet fait 8 bits et que nos codes font au moins 9 bits, on va devoir avoir une variable « extensible » dans laquelle on accumulera les données successives qu’on a reçues, jusqu’à avoir assez de bits pour lire un code.

Cette variale « extensible » sera bits_non_lus. On n’oubliera pas de compter, dans la variable nombre_de_bits_non_lus le nombre de bits qu’on a mis dans notre variable (y compris les bits à 0, il faut se rappeler qu’ils sont là !).

        if nombre_bits_non_lus >= bits_par_code:

            masque_bits_par_code = ((1 << bits_par_code) - 1) 

            code = bits_non_lus & masque_bits_par_code
            bits_non_lus >>= bits_par_code
            nombre_bits_non_lus -= bits_par_code

Si on a lu assez de bits, alors on peut entreprendre d’extraire le prochain code. Il se trouve tout à droite de la chaîne de bits, comme nous l’avons mentionné plus haut. On va donc l’extraire avec un Binary AND, et faire glisser vers la droite la chaîne de bits_non_lus pour ne garder que le reste ensuite.

            if block_mode and code == 256: # Code spécial reset du dictionnaire
                mon_dictionnaire = mon_dictionnaire[:257]

Si on rencontre le fameux code spécial dédié à cet effet, alors le dictionnaire est remis comme au départ.

            else:
                
                if code == len(mon_dictionnaire):
                    donnee = precedente_donnee_emise + precedente_donnee_emise[:1]
                else:
                    donnee = mon_dictionnaire[code]
                
                sortie += donnee
                if precedente_donnee_emise is not None and len(mon_dictionnaire) < (1 << max_bits) - 1:
                    mon_dictionnaire.append(precedente_donnee_emise + donnee[:1])
        
                precedente_donnee_emise = donnee

Autrement, on rentre dans le cœur de l’algorithme LZW - celui que je vous ai expliqué avec un diagramme plus haut. S’il reste encore de la place dans le dictionnaire, alors on ajoute une entrée.

        position += 1
        
        bits_par_code = len(format(len(mon_dictionnaire), 'b'))
        
        if anciens_bits_par_code and bits_par_code != anciens_bits_par_code:

Il faut maintenant vérifier si le nombre de bits par code a changé depuis le précédent passage dans la boucle.

Quelle taille fait un code ? On commence par regarder quel est le plus gros code du dictionnaire (ils commencent à 0), puis on convertit ce code en chaîne de caractères représentant un nombre binaire, grâce à la fonction format() : format(255, 'b') donnera '11111111' (vous avez de la chance de pouvoir faire ça aujourd’hui, quand j’avais commencé Python ce n’était pas possible) ! Ensuite, il suffit simplement de compter le nombre de caractères dans cette chaîne (donc de chiffres binaires qu’il faut pour écrire ce code).

            bits_non_lus = 0
            nombre_bits_non_lus = 0
            
            position += -(position - position_depuis_le_dernier_changement_de_bits_par_code) % anciens_bits_par_code
            position_depuis_le_dernier_changement_de_bits_par_code = position
        
        anciens_bits_par_code = bits_par_code

Si jamais elle a changé, on s’aligne sur l’octet suivant, et on saute un certain nombre d’octets (c’est la bizarrerie dont je vous ai parlé plus haut).

    return sortie
   
print(mon_decompresseur_lzw(bytes.fromhex('1f9d9045e88018762a0c083361d2081493a60d0b1062c23884f8a64e1b05c30e1944a810049c3963d0887c584620c18d0905da9153f16246941d194e8c38b3a5022261dccc01d1c6209d61aae8940191471ca04c3e2b0a8c53270d083a15e5b829a300a3c683294184ac4387a440384d77ea80c8268c98b256610a1cf3a64d9ba163d23c64eb76e8c9b45863367c48f361183420fe06467333e7ce366fdc682d36a98e9c876ae0b68523a78c1b323be184d9a900')).decode('utf8'))         

Et voilà ! On peut désormais comprendre ce que veut dire notre mystérieuse chaîne d’octets compressés, tel Micode hackant le système.

Voici ce que donne notre code en entier :

#!/usr/bin/python3
#-*- encoding: Utf-8 -*-

def mon_decompresseur_lzw(entree : bytes) -> bytes:

    assert entree[:2] == b'\x1F\x9D' # Vérifier la magic

    block_mode = bool(entree[2] >> 7)
    max_bits = entree[2] & 0b11111

    mon_dictionnaire = [bytes([octet]) for octet in range(256)] + ([None] if block_mode else [])

    sortie = b''
    precedente_donnee_emise = None

    position = 3
    position_depuis_le_dernier_changement_de_bits_par_code = position

    bits_non_lus = 0
    nombre_bits_non_lus = 0

    bits_par_code = 9
    anciens_bits_par_code = None
    
    while position < len(entree):

        octet = entree[position]
        
        bits_non_lus |= octet << nombre_bits_non_lus
        nombre_bits_non_lus += 8

        if nombre_bits_non_lus >= bits_par_code:

            masque_bits_par_code = ((1 << bits_par_code) - 1) 

            code = bits_non_lus & masque_bits_par_code
            bits_non_lus >>= bits_par_code
            nombre_bits_non_lus -= bits_par_code

            if block_mode and code == 256: # Code spécial reset du dictionnaire
                mon_dictionnaire = mon_dictionnaire[:257]
                
            else:
                
                if code == len(mon_dictionnaire):
                    donnee = precedente_donnee_emise + precedente_donnee_emise[:1]
                else:
                    donnee = mon_dictionnaire[code]
                
                sortie += donnee
                if precedente_donnee_emise is not None and len(mon_dictionnaire) < (1 << max_bits) - 1:
                    mon_dictionnaire.append(precedente_donnee_emise + donnee[:1])
        
                precedente_donnee_emise = donnee
        
        position += 1
        
        bits_par_code = len(format(len(mon_dictionnaire), 'b'))
            
        if anciens_bits_par_code and bits_par_code != anciens_bits_par_code:
            bits_non_lus = 0
            nombre_bits_non_lus = 0
            
            position += -(position - position_depuis_le_dernier_changement_de_bits_par_code) % anciens_bits_par_code
            position_depuis_le_dernier_changement_de_bits_par_code = position
        
        anciens_bits_par_code = bits_par_code
        
    return sortie
   
print(mon_decompresseur_lzw(bytes.fromhex('1f9d9045e88018762a0c083361d2081493a60d0b1062c23884f8a64e1b05c30e1944a810049c3963d0887c584620c18d0905da9153f16246941d194e8c38b3a5022261dccc01d1c6209d61aae8940191471ca04c3e2b0a8c53270d083a15e5b829a300a3c683294184ac4387a440384d77ea80c8268c98b256610a1cf3a64d9ba163d23c64eb76e8c9b45863367c48f361183420fe06467333e7ce366fdc682d36a98e9c876ae0b68523a78c1b323be184d9a900')).decode('utf8'))

On lance le code et notre résultat s’affiche :

Et ça fait bim, bam, boum
Ça fait pschhh, et ça fait vroum
Ça fait bim, bam, boum
Dans ma tête y’a tout qui tourne

Ça fait chut, et puis : blabla
Ça fait comme ci, comme ça
Ça fait bim, bam, ah ah ah
Dans mon cœur, je comprends pas 

Il s’agit du refrain de ce célèbre tube de l’Eurovision 2019.