LZ78 et LZW : la compression par dictionnaire

Un an après LZ77, Lempel et Ziv (nos chercheurs israéliens) publient un second algorithme, LZ78 (c’est bien l’année à la fin du nom de l’algorithme). Celui-ci fonctionne bien aussi, mais repose sur un principe légèrement différent.

Plus tard, LZ78 a aussi donné naissance à LZW, l’algorithme que vous retrouvez dans le célèbre format .GIF.

LZ78 : La compression par dictionnaire

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

Dans un vrai dictionnaire, je cherche des mots et j’obtiens des définitions en retours. Ici, je cherche des codes et je trouve des données. (source de l’image)

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.

Tu peux nous faire un petit exemple de décompression avec LZ78 ?

Bien sûr !

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

Après avoir traité la tuple…

(code, donnée)

…on obtient (décompressé)

…notre dictionnaire vaut

(0, "A")

A

0 = "<chaîne vide>"

1 = "A"

(0, "B")

AB

0 = "<chaîne vide>"

1 = "A"

2 = "B"

(1, "B")

ABAB

0 = "<chaîne vide>"

1 = "A"

2 = "B"

3 = "AB"

(3, "C")

ABABABC

0 = "<chaîne vide>"

1 = "A"

2 = "B"

3 = "AB"

4 = "ABC"

(4, "D")

ABABABCABCD

0 = "<chaîne vide>"

1 = "A"

2 = "B"

3 = "AB"

4 = "ABC"

5 = "ABCD"

(0, "E")

ABABABCABCDE

0 = "<chaîne vide>"

1 = "A"

2 = "B"

3 = "AB"

4 = "ABC"

5 = "ABCD"

6 = "E"

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

LZW : L'algorithme de .GIF, .TIFF...

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 ! :D )

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.

Quelques personnes sont mêmes descendues dans la rue. Ils savaient s'amuser à l'époque, à San Francisco !
Quelques personnes sont mêmes descendues dans la rue. Ils savaient s'amuser à l'époque, à San Francisco !

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.

Ah d’accord, ça fonctionne comme une sorte d’avalanche. Plus de caractères sont répétés à la suite, plus le programme apprend à en reconnaître de nouveaux. Mais alors le décompresseur doit stocker beaucoup de codes ? Quelle taille font-ils, ces codes ? Et que se passe-t-il quand il n’y a plus de place ?

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.

Du coup, si on a une longue séquence de caractères différents qui se répètent beaucoup, alors le dictionnaire va progressivement en enregistrer un peu plus à chaque itération (chaque occurrence) :

dans l’exemple ci-dessous, où l’on répète « ABCDEFGH » en boucle, vous aurez entre chevrons, l’entrée de dictionnaire précédente qui est réutilisée :

<A><B><C><D><E><F><G><H>
<AB><CD><EF><GH>
<ABC><DE><FG><HA>
<BC><DEF><GHA>
<BCD><EFG><HAB>
<CDE><FGH>
<ABCD><EFGH>
<ABCDE><FGHA>
<BCDE><FGHAB>
<CDEF><GHAB>
<CDEFG><HABC>
<DEFG><HABCD>
<EFGHA><BCDEF><GHABC><DEFGH><ABCDEF><GHABCD><EFGHAB><CDEFGH><ABCDEFG><HABCDE><FGHABC><DEFGHA><BCDEFG><HABCDEF><GHABCDE><FGHABCD><EFGHABC><DEFGHAB><CDEFGHA><BCDEFGH><ABCDEFGH><ABCDEFGHA><BCDEFGHA><BCDEFGHAB><CDEFGHAB><CDEFGHABC><DEFGHABC><DEFGHABCD><EFGHABCD><EFGHABCDE><FGHABCDE><FGHABCDEF><GHABCDEF><GHABCDEFG><HABCDEFG><HABCDEFGH><ABCDEFGHAB><CDEFGHABCD><EFGHABCDEF><GHABCDEFGH><ABCDEFGHABC><DEFGHABCDE><FGHABCDEFG><HABCDEFGHA><BCDEFGHABC><DEFGHABCDEF><GHABCDEFGHA><BCDEFGHABCD><EFGHABCDEFG><HABCDEFGHAB><CDEFGHABCDE><FGHABCDEFGH><ABCDEFGHABCD><EFGHABCDEFGH><ABCDEFGHABCDE><FGHABCDEFGHA><BCDEFGHABCDE><FGHABCDEFGHAB><CDEFGHABCDEF><GHABCDEFGHAB><CDEFGHABCDEFG><HABCDEFGHABC>
etc. Comme vous le voyez, la taille du contenu des codes augmente progressivement.

Mais si le même caractère se répète continuellement, alors cela va être encore plus rapide : par exemple, s’il n’y a que des zéros :

<0><0>
<00>
<000>
<0000>
<00000>
<000000>
<0000000>
<00000000>
<000000000>
<0000000000>
<00000000000>
<000000000000>
<0000000000000>
<00000000000000>
etc.

Voici un bref schéma du fonctionnement de LZW.

Schéma du fonctionnement de l'algorithme LZW.
Schéma du fonctionnement de l'algorithme LZW.

La décompression d'un fichier LZW avec Python (.Z)

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 :

Nom Taille en bits Description
Magic 16 Les octets "1F 9D". Ils n’ont pas de signification particulière, ils servent juste à identifier le format et à ne pas le confondre avec d’autres.
Block mode 1 Si ce champ vaut 1 (c’est le bit le plus haut du second octet), alors le code "256" sera un code spécial pour vider le dictionnaire.
Max bits 7 Le nombre maximum de bits pouvant permettre d’écrire un code au sein du fichier. Il ne sera pas plus grand que 16 (sur des machines anciennes, ce sera 12). Dans tous les cas, les premiers codes seront encodés sur 9 bits, puis leur taille augmentera.

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

Quelques détails à savoir sur cette implémentation de LZW :

  • Lorsqu’on lit une chaîne de bits qui s’étend sur plusieurs octets, chaque nouvel octet s’ajoute à la gauche du précédent (ordre little endian). Comme ça, on sait que les prochains bits à traiter se trouvent tout à droite de la chaîne de bits lue. (C’est plus efficace à lire que si on faisait l’inverse.)

  • Lorsque qu’à un endroit donné, vous trouvez une référence au code qui doit être construit à partir du code précédent et du code actuel (et donc qui n’est pas encore dans le dictionnare), c’est une référence au précédent code. Ça signifie que vous devez concaténer le précédent code + le premier caractère du précédent code. (c’est un genre d’optimisation)

  • Une condition très particulière de .Z : lorsque le nombre de bits par code change, l’alignement des bits par rapport aux octets est remis à zéro, c’est à dire qu’on repart au début du prochain octet (jusqu’à là, c’est raisonnable). Mais à ce moment-là, on saute aussi des octets, et combien d’octets, autant d’octets qu’il le faut pour que le nombre d’octets émis depuis la dernière fois où le nombre de bits par code a changé soit un multiple du nombre de bits par code actuel. Ne cherchez pas de sens, il n’y en a pas, le développeur a dû se tromper quelque part à l’origine. Cela oblige à l’ajout dans d’un maximum de 15 octets vides (au maximum, et selon le contexte) dans le fichier, quand le nombre de bits par code change (pas souvent).

C’est ça aussi, créer son propre format : si vous introduisez un bug dès le départ, parfois, eh bien vous allez devoir conserver votre bug par la suite dans une certaine mesure juste pour que les versions suivantes de votre programme restent compatibles avec les fichiers déjà émis quand il y avait le bug. C’est pour ça qu’il faut faire très attention.

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.

Dans cet exemple, j’utilise une fonctionnalité un peu avancée de Python qui me permet de faire tenir des boucles et des conditions sur une seule ligne. Les boucles créées de cette manières sont appelées « compréhensions » (ou « intensions », avec un « s ») et les conditions sont appelées « expressions conditionnelles » (ou « ternaires »).

C’est un aspect de Python qui a été un peu hérité de ce qu’on appelle les langages fonctionnels : dans les « langages impératifs », on se contente d’assigner des variables les unes après les autres, comme on le fait le plus souvent en Python. Dans les « langages fonctionnels », les fonctions ne sont que des sortes de grosses variables dans lesquelles on imbrique des conditions et des boucles (qui sont en fait aussi des appels de fonctions) les unes dans les autres. Python vous permet de faire un peu des deux.

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

Que veut dire l’opération nombre1 += -nombre1 % nombre2 en Python ? Ça veut dire : on ajoute à nombre1 ce qu’il faut pour atteindre le prochain multiple de nombre2. Si nombre1 est déjà un multiple de nombre2, on ne change rien.

C’est une opération qui permet de faire ce qu’on appelle « calculer un padding » (padding = bourrage en anglais) : si par exemple il faut que la taille d’un champ de format soit un multiple de 4, on peut utiliser cette opération pour savoir combien d’octets de « bourrage » ajouter.

    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 :magicien: s’affiche :

Et ça fait bim, bam, boum
Ça fait pschhh, et ça fait vroum
Ça fait bim, bam, boum
Dans mate ya 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.

Je commence à m’interroger sur tes goûts musicaux.


Liens intéressants :