LZ77 et LZSS : les algorithmes à fenêtre glissante

Imaginons que « AAAA » veuille dire pixel blanc (oui, maintenant on fait plus simple). Maintenant, « BBBB » veut dire pixel noir.

J’ai un carré après six pixels blancs. Je vais écrire « AAAA AAAA AAAA AAAA AAAA AAAA BBBB ».

Ça ne me va pas, je voudrais écrire le moins de « AAAA AAAA » possible, parce que c’est long.

Comment le dire simplement à l’ordinateur ? Je pourrais lui dire simplement : « eh, rappelle-toi, j’ai écrit « AAAA » ici. Juste à cette position ». C’est le principe de base de LZ77, le premier algorithme de Lempel et Ziv.

Par contre, mon ordinateur a une mémoire limitée. Il ne peut se souvenir que des 16 derniers pixels (c’est un petit ordinateur). En plus, si à chaque fois que je lui disais « tiens, voici où était AAAA, mais c’était quelque part plus loin qu’il y a 16 bits », je vais devoir écrire des nombres plus grands que « 16 » pour le dire, et plus mon nombre sera grand, plus il me faudra de bits pour le dire à chaque fois !

Donc mon algorithme de compression sera moins efficace.

Pour écrire un nombre de « 0 » à « 15 » (donc 16 positions possibles), il me faut 4 bits.

Avec LZ77, pour écrire « AAAA AAAA AAAA AAAA AAAA AAAA BBBB », il faut d’abord que je dise « AAAA » une fois à l’ordinateur. Logique, il n’a jamais vu ça. Ensuite, il faut que je lui dise de se rappeler de « AAAA ». Ce sont deux choses différentes à dire, il me faut donc deux manières différentes de le dire.

Avec LZ77, j’envoie trois informations en boucle : position, taille, donnée.

Je veux juste envoyer une donnée que je n’ai jamais vu ? On oublie position et taille. On va juste envoyer une donnée : AAAA.

Donc, pour commencer, je vais écrire :

(0, 0, AAAA)

Vous aurez compris, position et taille ne sont pas utilisés, je le mets à 0.

Ensuite, je vais dire à mon ordinateur d’écrire « AAAA » à nouveau. C’était un bloc de données, une position avant. Juste ensuite, il y a encore « AAAA ». Je vais donc ajouter :

(1, 1, AAAA)

Où « position » est à 1 et « taille » est à 1. Ici, je lui dis deux choses à la fois : répète le « AAAA » que je viens d’envoyer, puis envoie un nouveau « AAAA » (que je réécris une nouvelle fois du coup, parce que « donnée » ne peut pas être vide).

Du coup, avec des deux instructions LZ77, j’ai écrit « AAAA AAAA AAAA ». J’en ai marre de me répéter ! Chance, je peux maintenant lui dire simplement d’écrire trois fois « AAAA » à nouveau, vu que c’est ce que je viens de faire. Et ensuite, d’écrire « BBBB ».

Je vais le faire comme ça :

(3, 3, BBBB)

Ça veut dire « reviens trois positions en arrière, et écris les trois blocs qui se trouvent ici à nouveau (« AAAA AAAA AAAA »). Ensuite, écris « BBBB » ».

Au final, j’écris :

(0, 0, AAAA)
(1, 1, AAAA)
(3, 3, BBBB)

Et si je reprends la logique dans l’autre sens (je décompresse au lieu de compresser), j’obtiens bien :

AAAA AAAA AAAA AAAA AAAA AAAA BBBB

Et une fois que j’ai écrit mon contenu compressé avec avec des 0 et des 1, eh bien il peut prendre un peu moins de place que mon contenu décompressé !

Un algorithme est une suite d’instructions. Ce sont simplement des choses que vous dîtes de faire à votre ordinateur, par exemple : « transforme ce fichier LZ77 en fichier lisible (décompressé) ».

Pour savoir ce que veut dire « fenêtre glissante », il faut considérer que quand j’ai écrit mon programme qui décompresse du LZ77, j’ai appris à mon ordinateur à lire « position », « taille » et « donnée » en boucle. Ce sont trois infomations, en principe, de taille fixe.

J’ai choisi, par contrainte de place (sinon les données compressées prendraient trop de place et compresser ne serait plus intéressant), d’écrire « position » avec seulement 4 bits.

Ici, je dis à mon programme de revenir 3 positions en arrière. Mais si j’écris par exemple « BABA BABA BABA BABA - BABA BABA BABA BABA - BABA BABA BABA BABA - BABA BABA BABA BABA », eh bien après tout ça, j’ai écrit 16 nouvelles positions. Pour retrouver « AAAA AAAA », de la dernière fois que je l’ai répété, il devra donc revenir 19 positions en arrière. C’est plus que 16, c’est un trop grand nombre, je ne peux plus l’écrire !

Du coup, il me faudrait un mot pour désigner les 16 dernières positions que je peux encore demander de répéter. Je vais l’appeler « fenêtre ».

Cette fenêtre ne comprend que les 16 dernières positions, vu que je ne peux pas répéter plus loin. Elle change tout le temps, à chaque fois que j’ajoute des nouvelles positions, on dit qu’elle « glisse » vers la droite : si la taille de ma fenêtre est de 2, et qu’au départ j’ai écrit « [AAAA AAAA] », et qu’ensuite j’ajoute « ABAB », j’aurai « AAAA [AAAA ABAB] ». Si ensuite j’ajoute encore « ABAB », j’aurai « AAAA AAAA [ABAB ABAB] ». Ces crochets représentent ma fenêtre.

C’est pour ça qu’on dit que LZ77 est un « algorithme à fenêtre glissante ».

Lempel et Ziv étaient des chercheurs. Pour décrire leur invention, ils ont écrit un document, où ils désignaient les informations « position, taille, donnée » avec des parenthèses et des virgules, comme je les ai écrites plus haut. Pas avec des 0 et des 1.

Du coup, c’est les gens qui ont écrit des programmes LZ77 ensuite qui ont décidé de comment ordonnancer les 0 et les 1.

Pour écrire notre première version de LZ77 en Python, nous n’allons pas écrire des 0 et des 1 : nous allons utiliser des tuples. Les tuples sont une suite de données de taille invariable : « position, taille, donnée », ça fait exactement trois données.

J’ouvre l’interpréteur Python, et j’écris :

ma_tuple = (0, 0, 'BBBB')

On retrouve « position, taille, donnée », dans le même ordre. « ma_tuple » est le nom de la variable que j’assigne (à laquelle je donne un sens). « 0 » sont deux entiers (des nombres). « 'BBBB' » est une chaîne de caractères (une suite de lettres), délimitée par des apostrophes.

Je mets des parenthèses « ( » et « ) » pour délimiter ma tuple. Des virgules « , » délimitent chaque élément de la tuple. « = » veut dire assigner, donner un sens à ma variable. Jusqu’à là vous suivez ?

Maintenant, je veux écrire plusieurs tuples. Je vais utiliser plusieurs tuples. Pour avoir plusieurs tuples, je vais utiliser une liste : une liste est une suite de données de tailles variables. Je vais écrire :

ma_liste_de_tuples = [
    (0, 0, 'AAAA'),
    (0, 1, 'AAAA'),
    (0, 3, 'BBBB')
]

C’est exactement l’information qu’on a représentée plus haut, mais écrite en Python.

Je vas créer une fonction de compression. Je lui donne la chaîne de caractères qu’on a vue plus haut, « AAAAAAAAAAAAAAAAAAAAAAAABBBB », en entrée, et elle va devoir provoquer la même sortie.

from typing import Tuple, List

def ma_fonction_de_compression(chaine_a_compresser : str) -> List[Tuple]:
   # Mon code sera ici

Commençons par écrire le contenu de ma fonction. Mon ordinateur ne peut regarder qu’à un endroit à la fois dans la chaîne à compresser que je lui envoie, il faut qu’il se souvienne d’une position. Cette position sera compotée en blocs de quatre lettres, car c’est ce qu’on a choisi plus haut. Je vais écrire :

    position_actuelle_en_lettres = 0

Il me faut aussi une variable pour stocker progressivement le contenu compressé. Elle sera vide au début, je vais la remplir peu à peu. Je vais écrire (toujours avec une annotation de types) :

    ma_sortie_compressee : List[Tuple] = []

Tant qu’il y a des blocs de 4 lettres à compresser, on en lire un, et continuer par lire les suivants ensuite, et cela, en boucle. Logique ! Donc on va écrire une boucle :

    while position_actuelle_en_lettres < len(chaine_a_compresser):

…qui fait exactement ça. "Len" veut dire length (taille), "while" veut dire "tant que", "<" veut dire inférieur à (on compare notre position avec la taille de chaîne passée en entrée). On continue tant qu’on n’est pas à la fin de ce qu’il y a à compresser.

Dans notre boucle, la première chose qu’on va faire, c’est vérifier si on n’a pas déjà écrit avant le début de ce qu’il y a à compresser. Histoire de savoir si on ne va pas le répéter, justement.

        TAILLE_DE_LA_FENETRE_EN_BLOCS = 16
            
        blocs_restants_a_compresser = (len(chaine_a_compresser) - position_actuelle_en_lettres) // 4

        blocs_qu_on_peut_repeter = 0

        for taille_a_verifier in range(1, min(blocs_restants_a_compresser, TAILLE_DE_LA_FENETRE_EN_BLOCS)):

Ouh là là, qu’est-ce que c’est que tout ce code ? On créé une nouvelle boucle : on va vouloir tester toutes les tailles possibles pour savoir le nombre de blocs qu’on peut répéter. Tant que ce qui suit constitue une suite de blocs qu’on a déjà vu, on continue. Sinon, on arrête.

« range » veut dire compter un certain nombre de fois (on fait augmenter notre taille progressivement). « min » veut dire « prendre la valeur la plus faible » : en principe on regarde tous les blocs déjà écrits un après un pour savoir si on peut les répéter (moins le dernier, notre dernier champ « position » ne peut pas être vide), mais ce ne sera jamais plus que la taille de la fenêtre, inutile d’essayer plus.

            chaine_deja_compressee = chaine_a_compresser[:position_actuelle_en_lettres]
            morceau_a_compresser = chaine_a_compresser[position_actuelle_en_lettres:position_actuelle_en_lettres + taille_a_verifier * 4]

            if morceau_a_compresser in chaine_deja_compressee:
                blocs_qu_on_peut_repeter += 1
            else:
                break

Que veut dire le contenu de notre nouvelle boucle (qui se trouve dans la première) ? On regarde un bout de ce qu’il y a encore à compresser (d’abord juste le début, puis progressivement le reste aussi). Si ce sont des choses qui ont déjà été compressées, on le remarque et on le note en faisant augmenter « blocs_qu_on_peut_repeter ». Sinon, on arrête et on sort de la boucle.

Pour trouver ce qui se trouve entre deux positions données dans une chaîne, on l’écrit ainsi : « variable_de_la_chaine[position_debut:position_fin] ». On appelle cette syntaxe (syntaxe = façon d’écrire) « slice » (en anglais tranche).

« += » veut dire augmenter un nombre (le mot technique est « incrémenter »). « break » veut dire « sortir de la boucle » (en anglais « casser »).

Maintenant qu’on sait combien de blocs déjà compressés on peut répéter, eh bien on s’exécute ! On dit à notre programme de répéter les blocs à répéter, s’il y en a, dans les champs « position » et « taille », et on ajoute le bloc d’ensuite dans « donnée ».

        if blocs_qu_on_peut_repeter > 0:
            morceau_a_repeter = chaine_deja_compressee[position_actuelle_en_lettres:position_actuelle_en_lettres + blocs_qu_on_peut_repeter * 4]

            position = chaine_deja_compressee.index(morceau_a_repeter)
            taille = blocs_qu_on_peut_repeter
        else:
            position = 0 
            taille = 0

        position_du_bloc_suivant_en_lettres = position_actuelle_en_lettres + blocs_qu_on_peut_repeter * 4

        donnee = chaine_a_compresser[position_du_bloc_suivant_en_lettres:position_du_bloc_suivant_en_lettres + 4]

        prochaine_sortie = (position, taille, donnee)

Vous remarquerez qu’on n’est plus dans la dernière boucle (l’indentation = le nombre d’espaces au début de la ligne a baissé).

Ici, on utilise la méthode « index » pour chercher une chaîne dans une autre chaîne (de « morceau_a_repeter » dans « chaine_deja_compressee »).

Bien, on avance, on est presque à la fin ! On peut déjà sortir notre prochaine instruction LZ77 (position, taille, donnée).

Maintenant, il faut mettre à jour les variables pour que la prochaine fois qu’on passe dans la boucle, notre programme se souvienne de tout ce qu’on a fait.

        position_actuelle_en_lettres += blocs_qu_on_peut_repeter * 4 + 4 # On ajoute la taille de ce qu'on a écrit

        ma_sortie_compressee.append(prochaine_sortie) # On ajoute notre résultat compressé

    return ma_sortie_compressee

Voilà, on est au bout ! À la fin de la boucle, On retourne ce qu’on a compressé. On ajoute notre nouvelle tuple (avec la méthode « append ») « prochaine_sortie » à la liste « ma_sortie_compressee » qu’on a céé au début. Plus on la renvoie : c’est la sortie de notre fonction.

Et après tout ça, en dehors de la fonction, on peut appeler la fonction pour tester notre programme :

print(ma_fonction_de_compression('AAAAAAAAAAAAAAAAAAAAAAAABBBB'))

Voici le code complet :

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

from typing import Tuple, List

def ma_fonction_de_compression(chaine_a_compresser : str) -> List[Tuple]:
    position_actuelle_en_lettres = 0
    ma_sortie_compressee : List[Tuple] = []

    while position_actuelle_en_lettres < len(chaine_a_compresser):
        TAILLE_DE_LA_FENETRE_EN_BLOCS = 16
            
        blocs_restants_a_compresser = (len(chaine_a_compresser) - position_actuelle_en_lettres) // 4

        blocs_qu_on_peut_repeter = 0

        for taille_a_verifier in range(1, min(blocs_restants_a_compresser, TAILLE_DE_LA_FENETRE_EN_BLOCS)):
            chaine_deja_compressee = chaine_a_compresser[:position_actuelle_en_lettres]
            morceau_a_compresser = chaine_a_compresser[position_actuelle_en_lettres:position_actuelle_en_lettres + taille_a_verifier * 4]

            if morceau_a_compresser in chaine_deja_compressee:
                blocs_qu_on_peut_repeter += 1
            else:
                break

        if blocs_qu_on_peut_repeter > 0:
            morceau_a_repeter = chaine_deja_compressee[position_actuelle_en_lettres:position_actuelle_en_lettres + blocs_qu_on_peut_repeter * 4]

            position = chaine_deja_compressee.index(morceau_a_repeter)
            taille = blocs_qu_on_peut_repeter
        else:
            position = 0 
            taille = 0

        position_du_bloc_suivant_en_lettres = position_actuelle_en_lettres + blocs_qu_on_peut_repeter * 4

        donnee = chaine_a_compresser[position_du_bloc_suivant_en_lettres:position_du_bloc_suivant_en_lettres + 4]

        prochaine_sortie = (position, taille, donnee)
        
        position_actuelle_en_lettres += blocs_qu_on_peut_repeter * 4 + 4 # On ajoute la taille de ce qu'on a écrit

        ma_sortie_compressee.append(prochaine_sortie) # On ajoute notre résultat compressé

    return ma_sortie_compressee


print(ma_fonction_de_compression('AAAAAAAAAAAAAAAAAAAAAAAABBBB'))

Et voici le résultat quand on l’exécute :

[(0, 0, 'AAAA'), (0, 1, 'AAAA'), (0, 3, 'BBBB')]

C’est bien beau tout ça, mais pour faire un vrai algorithme de compression, il faut écrire des 0 et des 1, pas des tuples ! Et puis, pourquoi écrire « (position, taille, donnée) » en boucle ? Pourquoi pas « (position, taille) » et « (donnée) » séparément ? Comme ça, « donnée » pourrait être plus longue. Si ça se trouve, on se répète trop !

Du calme ! Pour répondre à ces deux problèmes, des gens ont créé LZSS. LZSS est un algorithme créé en 1982, et son nom est la contraction encore plus obscure du nom de quatre chercheurs (« Lempel–Ziv–Storer–Szymanski » - pour prononcer le nom du dernier, bon courage).

Le principe de LZSS est assez semblable à celui de LZ77. Sauf que quand vous décompressez, vous ne lisez pas des tuples : vous lisez d’abord un octet, appelé « flags », dont chaque bit est une instruction pour l’ordinateur. Si le bit est « 1 », ça veut dire lire une donnée, et si ce bit est « 0 », ça veut dire lire une position et une taille (pour faire une répétition).

Du coup, ce qu’on commence à faire, quand on veut décompresser un fichier en LZSS, c’est qu’on lit d’abord les « flags ». Vu que chaque bit est une instruction, on saura quoi faire huit fois de suite ! On le fait. Une fois qu’on l’a fait, qu’est-ce qui se passe ? On prend un nouvel octet de flags, et ainsi de suite, et ce jusqu’à la fin du fichier.

Tout de suite !

En fait, quand vous écrivez du code (que ce soit en Python, en C) ou autre chose, il est transformé en langage machine (encore une autre sorte de 0 et de 1) qui va au microprocesseur, la pièce de votre ordinateur qui lui permet de « réfléchir ». Dans le langage machine, vous ne pouvez pas demander au microprocesseur de ne lire qu’un bit. Il ne sait pas faire. Il lit forcément au moins un octet à la fois, parce qu’il est fait comme ça (et par souci d’économie de ressources, et parce que tous les programmeurs codent des choses sur des groupes de 8 bits, ou de multiples de 8, depuis longtemps).

Du coup, pour lire un bit de flag, il faut d’abord lire un octet de 8 bits, et en extraire 1 bit. Ça fait deux opérations. Si on groupe les flags ensemble et les données ensemble, on n’a à faire ces deux opérations que lorsqu’on lit les flags, on n’a pas besoin de faire des opérations en plus lorsqu’on lit les données ! Autrement, ça nous ralentirait. Comme ça, on évite de faire des opérations d’extractions de bits inutiles, et un octet de données lu devient tout de suite un octet de données décompressé et écrit.

Tout de suite !

LZ77 a inspiré beaucoup d’autres algorithmes, mais n’est pas tellement utilisé « en vrai ». LZSS, lui, est déjà un peu plus utilisé, pour la décompression de programmes par exemple.

Également, des algorithmes que vous retrouvez partout sont basés sur LZSS, comme DEFLATE (utilisé par .ZIP, .GZ, .PNG, pour compresser les pages web et plein d’autres applications !) ou celui de RAR. Nous les découvrirons plus tard.

Tout à l’heure, vous vous souvenez, nous avons compressé. Maintenant, pour changer, nous allons décompresser ! C’est toujours gratifiant de partir d’un résultat illisible et de finir par avoir la « clef du mystère » qui s’affiche, un peu comme une énigme. C’est pour ça aussi que j’aime la programmation.

Si vous êtes déjà bon en Python, vous pouvez déjà suivre l’algorithme que j’ai décrit plus haut et essayer de décompresser vous-même. Sinon, on va le faire pas à pas.

Il y a un petit détail à savoir, dans tous les cas. Quand on faisait LZ77, on indiquait nos positions depuis la fin de la fenêtre glissante. Maintenant, on va l’indiquer depuis le début d’un ring buffer de taille fixe, de la taille de la fenêtre glissante, dans lequel on va écrire progressivement nos données décompressées. Qu’est-ce qu’un ring buffer ?

Le principe est très simple : buffer veut dire, grosso modo, espace de taille fixe (ce sera la taille de notre fenêtre). Ring veut dire circulaire. Un ring buffer est, grosso modo, un espace de taille fixe (qui fait par exemple 4096 octets) où, qu’est-ce qu’on fait une fois qu’on a écrit tous nos 4096 octets ? On revient au début (en réécrivant par-dessus les données déjà écrites), tout simplement.

Les principales implémentations de LZSS utilisent un ring buffer. Comme ça, elles sortent le contenu décompressé aussitôt qu’il est produit, elles ne le gardent pas en mémoire, et ne gardent en mémoire « que » un espace de la taille de la fenêtre glissante. D’où une notation inhabituelle pour calculer une position.

Il existe plusieurs variantes de LZSS, mais contrairement à LZ77, la grande majorité des implémentations fonctionnent pareil. Elles émanent du code d’un programmeur japonais, qui a écrite la sienne en 1989 avant de la partager sur l’Internet de l’époque.

Nous allons travailler sur cette variante. Attention, elle a quelques bizarreries que vous devez connaître, sinon votre code ne marchera pas.

• Bizarrerie n° 1 : dans cette implémentation, la position initiale du ring buffer ne commence pas à 0, mais à 4078. Pourquoi 4078 ? Il s’agit de 4096 - 18, où 4096 est la taille du ring buffer, et 18 est la taille maximale d’une répétition. D’accord, mais pourquoi pas 0 ? On ne sait pas trop. Mais son code marchait. (Et pour que votre code soit compatible, ça vous oblige à le faire aussi).

• Bizarrerie n° 2 : dans le flux à décompresser, la taille et la position de la répétition sont agencés comme il suit :

• Bizarrerie n° 3 : vous devez ajouter 3 à la taille de la répétition que vous obtenez. Pourquoi 3 ? Parce que la programmeur a décidé que la taille minimum d’une répétition était de 3 (autrement on ne gagne pas de place). Cela fait trois valeurs possibles qui ne seront jamais utilisées (0, 1, 2), donc il s’est dit, autant gagner de la place dans mon demi-octet (!). Comme ça, votre demi-octet peut contenir une valeur allant de 3 à 18, au lieu de 0 à 15. La compression est un art qui se rapproche de la magie noire et je suis sûr que vous porterez une grande robe sombre à la fin de ce tutoriel !

On va commencer à écrire notre programme. Mais il nous faut déjà savoir quoi décompresser !

Je vais vous donner un extrait de texte à décompresser. Et pas n’importe comment, je vais vous le donner, en hexadécimal :

ff49276d20626c7565ff2064612062612064bd65f5f661610a44f8ff2c40f6ff1c0f050f2c0f520f3b0b0aeeff003e0f650fa90fbb0fa40fcb0ff10fda06

Souvenez-vous : en binaire, vous avez deux chiffres, 0 et 1 (et pour le reste c’est comme le décimal, qui lui 10 chiffres, de 0 à 9). Eh bien, en hexadécimal, vous avez 16 chiffres, de 0 à f. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f.

Pourquoi cette notation bizarre ? Eh bien, figurez vous que deux chiffres en hexadécimal, ça fait très exactement un octet. En effet, un octet va de 0 à 255, soit 256 valeurs possibles, et 16 × 16, ça fait 256. Cette notation est donc très pratique pour représenter une suite d’octets : il suffit de diviser par deux le nombre de caractères hexadécimaux pour connaître le nombre d’octets.

Ah, ils sont bizarres ces informaticiens à ne pas utiliser les mêmes chiffres que tout le monde… Ou plutôt, ne serait-ce pas vous qui êtes bizarre à avoir 10 doigts plutôt que 8 ? Vous pourriez être un Simpson !

Bref, notre fonction va commencer presque comme l’autre.

def mon_decompresseur_lzss(octets_a_decompresser : bytes) -> bytes:
    # Mon code sera ici

On prend des octets (en anglais « bytes », à ne pas confondre avec bits) à décompresser en entrée et on va sortir des octets décompressés en sortie, jusqu’à là fort logique.

    ma_position = 0

    octets_decompresses = b''

Comme toujours, notre ordinateur ne peut regarder qu’à un seul endroit à la fois, donc on lui garde une petite variable pour qu’il se souvienne où il en est. La position est exprimée en octets. On alloue aussi une variable qui stockera les données décompressées.

Vous remarquerez que notre chaîne d’octets vide s’écrit « b’' », alors qu’une chaîne de caractères normale vide s’écrirait « '' ». Quelle est la différence ? Les octets vont de 0 à 255. Vous pouvez stocker une lettre sans accent ou un chiffre dans un octet (par exemple « a », « A » ou « 0 »), Python considérera que vous utilisez alors ce qu’on appelle l’encodage ASCII. Regardez bien ce tableau :

Ici, ce tableau nous explique que la lettre « A » majuscule correspond à l’octet « 0x41 » en encodage ASCII. L’encodage ASCII n’a rien de magique, c’est juste le standard le plus répandu (avant les années 2000) pour représenter des lettres comme des octets.

Mais dans une chaîne d’octets, vous pouvez aussi mettre des octets qui ne veulent rien dire en encodage ASCII. Par exemple, vous pouvez écrire « b’\xdf' » pour créer une chaîne d’octets qui contiendra juste l’octet « 0xDF » (oui, c’est toujours de l’hexadécimal), et ça continuera à marcher. Bref, une chaîne d’octets stocke juste des octets.

Alors que dans une chaîne de caractères normales, que vous pouvez par exemple écrire « '' » (chaîne de caractères vide) ou « 'abcdÉ' » (chaîne de caractères avec plusieurs lettres), vous pouvez aussi mettre des accents. Alors que les accents, dans une chaîne d’octets ce n’est pas possible : ils n’existent pas en ASCII. À contrario, les chaînes de caractères normales n’utilisent pas ASCII, mais un encodage plus complexe qui s’appelle UTF-8 et qui gère (entre autres) les accents ou les emojis. Vous suivez ?

UTF-8 est basé sur ASCII. Pourquoi on n’utilise pas des chaînes de caractères normales pour stocker nos octets, du coup ? Parce que UTF-8 est un encodage où un caractère peut s’étendre sur plusieurs octets, tout simplement. Du coup, on doit utiliser des chaînes d’octets (comme on vient d’en créer, en écrivant « b’' ») pour créer des vrais octets.

    mon_ring_buffer = bytearray(b' ' * 4096)

En plus de la variable pour stocker nos octets décompressés, on va créer un ring buffer, qui représentera donc notre fenêtre glissante.

En Python, lorsque vous créer une chaîne d’octets, comme je l’ai fait en écrivant « b' ' » puis « b' ' * 4096 » (ça a répété mon octet contenant unz 4096 fois), les octets ne sont pas réinscriptibles. Je peux lire une chaîne d’octets, prendre une partie de cette chaîne d’octets, prendre un seul octet, fusionner deux chaînes d’octets ou deux parties de chaînes d’octets entre elles, mais pas modifier un octet sur place.

C’est une limitation du type bytes (le type de variable qui se créé lorsque j’écris « b' ' »). Pour remédier à cela, il existe un second type, le type bytearray, ou chaque octet est réinscriptible. Je pourrai donc faire « ma_bytearray[4] = 0x43 » pour remplacer le cinquième octet (comme toujours en Python, les index commencent à zéro) par « 0x43 ». On dit que bytearray est « mutable » alors que bytes est « immutable ».

On peut créer un bytearray à partir d’un bytes (le bytes d’origine est copié). La ligne ci-dessus signifie donc : créé une chaîne de 4096 octets, qui valent tous un espace ASCII, puis rends ces octets réinscriptibles.

    bits_de_flags_restants = 0
    octet_de_flags = 0

    while ma_position < len(octets_a_decompresser):

        if bits_de_flags_restants == 0:
            octet_de_flags = octets_a_decompresser[ma_position]
            bits_de_flags_restants = 8
            ma_position += 1

On entre dans une nouvelle boucle, et on commence par écrire le code pour obtenir le premier octet de flags, le cas échéant. On avance alors d’un octet.

        position_du_bit_a_lire_depuis_la_droite = (8 - bits_de_flags_restants)

        if octet_de_flags & (1 << position_du_bit_a_lire_depuis_la_droite):

On vérifie si le prochain bit de flags vaut 0, ou 1. Si vous ne comprenez pas le code que j’ai écrit, lisez attentivement le bloc d’information ci-dessous.

            mon_ring_buffer[(len(octets_decompresses) + 4078) % 4096] = octets_a_decompresser[ma_position]

Le bit de flags vaut 1 : on inscrit dans notre ring buffer un octet décompressé, directement depuis les données d’entrée. On remarque le fameux décalage à 4078 dont je vous ai parlé plus haut.

Vous remarquerez que l’espace du ring buffer étant limité, on revient au début une fois qu’il n’y a plus de place (c’est effectivement le principe), et pour cela on utilise l’opérateur « % » : modulo. Le modulo, c’est grosso modo le reste d’une division.

« 4094 % 4096 » fait 4094, « 4095 % 4096 » fait 4095, puis… « 4096 % 4096 » fait 0. « 4097 % 4096 » fait 1, « 4098 % 4096 » fait 2, puis ainsi de suite.

            octets_decompresses += bytes([octets_a_decompresser[ma_position]])
            ma_position += 1

On l’ajoute aussi à notre chaîne d’octets décompressés. Puis on avance d’une position.

        else:
            position_et_taille = int.from_bytes(octets_a_decompresser[ma_position:ma_position + 2], 'big')
            ma_position += 2

            position_repetition = (position_et_taille >> 8)  | ((position_et_taille & 0xf0) << 4)
            taille_repetition = (position_et_taille & 0x000f) + 3

Le bit de flags vaut 0 : il va falloir faire une répétition. Pour ça, on lit deux octets, qu’on découpe en 1,5 octet pour le position, et 0,5 octet pour la taille. On retrouve les deux autres « bizzareries » dont je vous ai parlé plus haut.

Vous avez retenu ce que je vous ai dit plus haut sur les opérateurs binaires ? Ça devient un peu plus technique !

Une fois notre nombre de deux octets lu, il faut donc le couper en deux. On va utiliser l’opérateur Binary AND, cette fois pas pour isoler un bit, mais pour isoler plusieurs bits.

Notre nombre fait 2 octets, donc 16 bits.

• La position, c’est les 12 bits les plus à gauche (« les plus hauts »). Les 4 bits les plus hauts se trouvent après les 8 bits les plus bas pour une raison obscure (le code original lit les deux octets séparément), on s’occupe donc de les extraire et de remettre le tout dans l’ordre.

L’opérateur « | » (binary OR) permet de fusionner deux octets, en laissant à « 1 » les bits qui sont à 1 dans n’importe lequel des deux octets. Dans ce cas précis, une addition aurait aussi fonctionné.

• La taille, c’est les 4 bits les plus à droite. Ici, j’ai écrit mon masque directement en hexadécimal : « 0x000f », mais j’aurais aussi pu l’écrire en binaire : « 0b1111 », ou calculer mon masque : « (1 << 4) - 1 » (eh oui, 10000 moins un, en binaire, cela fait 1111 ! o_O ).

            a_repeter = mon_ring_buffer[position_repetition:position_repetition + taille_repetition]

            if position_repetition + taille_repetition > len(mon_ring_buffer):
                a_repeter += mon_ring_buffer[:(position_repetition + taille_repetition) % len(mon_ring_buffer)]

Maintenant qu’on connaît la position et la taille des données à répéter, on les utilisent pour copier les données depuis le ring buffer. Si jamais la partie du ring buffer qu’on doit lire va plus loin que la taille du ring buffer, on fait comme lorsque l’on écrit : on revient au début.

Du coup, si on doit revenir au début du ring buffer pour lire, on s’exécute.

            for position_ecriture in range(len(a_repeter)):
                mon_ring_buffer[(len(octets_decompresses) + 4078 + position_ecriture) % 4096] = a_repeter[position_ecriture]

            octets_decompresses += a_repeter

On prend soin de recopier ce qu’on a lu et dans le ring buffer, et dans la sortie décompressée.

        bits_de_flags_restants -= 1

    return octets_decompresses

Paf, c’est fini ! On peut retourner nos octets décompressés. On n’oublie pas de prévenir notre programme de passer au bit de flag suivant au prochain passage dans la boucle, quand même !

Ce fut long, mais ne vous inquiétez pas, maintenant que j’ai pu vous apprendre plein de choses "simples" sur les opérations binaires en général et en Python, je n’aurai plus à les répéter ! Et vous avez un premier moyen de décompresser des octets en Python !

C’est le moment de voir ce que signifient nos données décompressées.

print(mon_decompresseur_lzss(bytes.fromhex('ff49276d20626c7565ff2064612062612064bd65f5f661610a44f8ff2c40f6ff1c0f050f2c0f520f3b0b0aeeff003e0f650fa90fbb0fa40fcb0ff10fda06')).decode('utf8'))

Vous remarquerez que pour convertir une chaîne hexadécimal en chaîne d’octets, on peut utiliser la fonction bytes.fromhex.

On prend aussi soin de re-convertir en chaîne de caractères les octets décompressés retournés par notre fonction, en faisant « .decode('utf8') ». Car si on passe une chaîne d’octets bruts à print(), les retours à la ligne ne sont pas reproduits, par exemple

Voici ce que donne notre programme en entier :

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


def mon_decompresseur_lzss(octets_a_decompresser : bytes) -> bytes:
    ma_position = 0

    octets_decompresses = b''

    mon_ring_buffer = bytearray(b' ' * 4096)

    bits_de_flags_restants = 0
    octet_de_flags = 0

    while ma_position < len(octets_a_decompresser):

        if bits_de_flags_restants == 0:
            octet_de_flags = octets_a_decompresser[ma_position]
            bits_de_flags_restants = 8
            ma_position += 1
        
        position_du_bit_a_lire_depuis_la_droite = (8 - bits_de_flags_restants)

        if octet_de_flags & (1 << position_du_bit_a_lire_depuis_la_droite):

            mon_ring_buffer[(len(octets_decompresses) + 4078) % 4096] = octets_a_decompresser[ma_position]
            
            octets_decompresses += bytes([octets_a_decompresser[ma_position]])
            ma_position += 1

        else:
            position_et_taille = int.from_bytes(octets_a_decompresser[ma_position:ma_position + 2], 'big')
            ma_position += 2

            position_repetition = (position_et_taille >> 8)  | ((position_et_taille & 0xf0) << 4)
            taille_repetition = (position_et_taille & 0x000f) + 3
            
            a_repeter = mon_ring_buffer[position_repetition:position_repetition + taille_repetition]
            if position_repetition + taille_repetition > len(mon_ring_buffer):
                a_repeter += mon_ring_buffer[:(position_repetition + taille_repetition) % len(mon_ring_buffer)]

            for position_ecriture in range(len(a_repeter)):
                mon_ring_buffer[(len(octets_decompresses) + 4078 + position_ecriture) % 4096] = a_repeter[position_ecriture]

            octets_decompresses += a_repeter

        bits_de_flags_restants -= 1

    return octets_decompresses

print(mon_decompresseur_lzss(bytes.fromhex('ff49276d20626c7565ff2064612062612064bd65f5f661610a44f8ff2c40f6ff1c0f050f2c0f520f3b0b0aeeff003e0f650fa90fbb0fa40fcb0ff10fda06')).decode('utf8'))

Voici ce qui s’affiche dans notre terminal lorsqu’on exécute notre programme :

I’m blue da ba dee da ba daa
Da ba dee da ba daa, da ba dee da ba daa, da ba dee da ba daa
Da ba dee da ba daa, da ba dee da ba daa, da ba dee da ba daa

I’m blue da ba dee da ba daa
Da ba dee da ba daa, da ba dee da ba daa, da ba dee da ba daa
Da ba dee da ba daa, da ba dee da ba daa, da ba dee da ba daa

Vous avez peut-être reconnu ces paroles, il s’agit du refrain d’un célèbre hit techno un brin répétitif des années 2000 !

Ces répétitions font que le refrain se compresse pas trop mal : on passe de 307 octets à 62 octets (!). C’est presque cinq fois plus petit, on dit que le ratio de compression est de 1:4,95 environ.

Une sliding window (fenêtre glissante) c’est un historique des derniers octets décompressés, dans lequel un algorithme de ce type peut aller piocher des extraits pour les répéter.

LZ77 (1977) est un algorithme de compression sans perte qui n’est pas très utilisé, mais qui est important parce qu’il en a inspiré beaucoup d’autres.

LZSS (1982) est un algorithme qui est basé sur LZ77, mais qui dispose de plus d’implémentations concrètes. Surtout, LZSS a servi de base pour DEFLATE, qui est un algorithme de compression très important (.ZIP, .PNG..).