• Compression de données, Huffman (2025-11-15)

  Voici un nouvel article de la série sur la compression de données, qui fait suite à celui sur la compression RLE, la compression LZ et la compression ZX0.

  À la fin de l'article sur la compression LZ, il avait été question de fréquence d'apparition des nombres pour les offsets de référence et les longueurs de motif. Cette constatation avait amené lors de l'article sur ZX0 à regarder le codage gamma, qui permet de coder des entiers avec un nombre de bits variable afin d'optimiser la taille des petits nombres (qui sont plus fréquents).

  Revenons sur cette histoire de fréquence en l'étendant à tous les symboles présents dans les données à compresser. Il serait intéressant d'avoir un codage dépendant de la fréquence d'apparition des symboles : plus le symbole est fréquent, plus son code est court.

  Ce codage est obtenu avec l'algorithme de Huffman.

  En plus d'avoir des codes de longueurs variables en fonction de la fréquence, Huffman garantit qu'aucun code n'est le préfixe d'un autre code, ce qui rend l'algorithme de décodage très facile. Le codage est aussi optimal : il n'y a pas de codage préfixe plus court pour les fréquences données.

  Algorithme de compression de Huffman

  L'idée générale de l'algorithme est la suivante : après avoir calculé les fréquences d'apparition des symboles, on construit un arbre binaire où chaque symbole est une feuille de l'arbre, avec les symboles les plus fréquents proches de la racine. Le code d'un symbole correspond alors au parcours depuis la racine jusqu'à la feuille, en prenant 0 pour une branche et 1 pour l'autre.

  Pour initier la construction de l'arbre, on crée une liste de nœuds, un par symbole associé à sa fréquence. Ensuite et itérativement jusqu'à avoir l'arbre complet, on prend les deux nœuds de plus petite fréquence et on crée un nouveau nœud parent avec comme fréquence la somme des deux fréquences.

  Reprenons l'exemple qui nous suit depuis le début. Pour rappel, il s'agit de cette image :

  ................
  ....#######.....
  ..##@@@@@@@##...
  .##@OOOOOOO@##..
  .#@OoooooooO@#..
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  .#@OoooooooO@#..
  .##@OOOOOOO@##..
  ..##@@@@@@@##...
  ....#######.....
  ................
  

  On commence donc par calculer les fréquences (ou occurrences, cela revient au même) des symboles :

  Fréquences des symboles :
    '.': 78 (28.78%)
    'o': 68 (25.09%)
    '#': 46 (16.97%)
    '@': 34 (12.55%)
    'O': 30 (11.07%)
    '\\n': 15 (5.54%)
  

  Donc, plein de '.' et de "o", et pas beaucoup de retours à la ligne. À noter qu'avec 6 symboles différents, on pourrait utiliser un codage fixe sur 3 bits par symbole (2^3 = 8 possibilités). Voyons ce que donne Huffman en déroulant l'algorithme :

  • On prend les deux nœuds de plus petites occurrences : '\n' (15) et 'O' (30)
  • On crée un nœud parent "\nO" avec occurrences 45 (15 + 30)
  • On prend les deux nœuds de plus petites occurrences : '@' (34) et le "\nO" (45)
  • On crée un nœud parent "@\nO" avec occurrences 79 (34 + 45)
  • On prend les deux nœuds de plus petites occurrences : '#' (46) et 'o' (68)
  • On crée un nœud parent "#o" avec occurrences 114 (46 + 68)
  • On prend les deux nœuds de plus petites occurrences : '.' (78) et le "@\nO" (79)
  • On crée un nœud parent ".@\nO" avec occurrences 157 (78 + 79)
  • On prend les deux nœuds de plus petites occurrences : "#o" (114) et ".@\nO" (157)
  • On crée un nœud racine avec occurrences 271 (114 + 157)

  Ce qui nous amène à l'arbre suivant :

              [271]
             /     \
     <-- 0  /       \  1 -->
           /         \
        [114]        [157]
       /     \      /     \
     [46]   [68]  [78]   [79]
       #      o     .   /    \
                      [34]  [45]
                        @  /    \
                          [15] [30]
                           \n    O
  

  Pour trouver les codes associé à chaque symbole, on parcourt l'arbre depuis la racine jusqu'à chaque feuille, en prenant 0 pour la branche de gauche et 1 pour la branche de droite. Et cela donne :

    '.'  : 10   (longueur=2)
    'o'  : 01   (longueur=2)
    '#'  : 00   (longueur=2)
    '@'  : 110  (longueur=3)
    'O'  : 1111 (longueur=4)
    '\\n': 1110 (longueur=4)
  

  En prenant la moyenne des longueurs pondérées par les occurrences, on obtient une taille moyenne de 2.45 bits environ par symbole. C'est mieux que les 3 bits fixes, mais pas extraordinaire non plus en considérant que 3 bits auraient pu coder 8 symboles.

  Cependant, il n'y a pas besoin de faire l'analyse au préalable et à la main pour savoir combien de bits sont nécessaires. L'algorithme de Huffman le fait tout seul.

  La compression elle-même consiste ensuite à remplacer chaque symbole par son code binaire. Pour notre exemple, cela donne pour la première ligne la suite de bits suivante : 10101010101010101010101010101010, ce qui fait une suite d'octets : 0xAA 0xAA 0xAA 0xAA. On passe de 16 octets à 4. On voit aussi qu'un motif se répète... intéressant non ? J'évoquerai cela à la fin de l'article.

  Algorithme de décompression

  La décompression est très simple : avec le flux compressé et l'arbre, on parcours l'arbre en lisant les bits un par un. À chaque 0, on descend sur la branche de gauche, à chaque 1 sur la branche de droite. Lorsqu'on atteint une feuille, on émet le symbole correspondant et on repart de la racine.

  Je vous laisse faire l'exercice avec 0xAA (c'est-à-dire 10101010) pour retrouver une série de quatre '.'.

  Et l'arbre ?

  C'est bien beau d'avoir codé les données grâce à l'arbre. Mais il nous faut l'arbre pour décoder le flux compressé. Il est donc nécessaire de le transmettre avec les données compressées. Il y a plusieurs manières de faire, mais voici une approche simple :

  • Pour chaque nœud interne, on écrit un 0 (en bit) et on sérialise récursivement les deux nœuds enfants.
  • Pour chaque feuille, on écrit un 1 suivi du code du symbole (sur 8 bits).

  En commençant par la racine, on obtient un parcours en profondeur de l'arbre. Pour notre exemple, cela donne la séquence de bits suivante (les caractères sont ici pour la lisibilité, mais en pratique ce sont leur représentation binaire qui est utilisée) :

  0
    0
      1 `#`
      1 `o`
    0
      1 `.`
      0
        1 `@`
        1 `\n`
      1 `O`
  

  Cela fonctionne puisque, par construction, chaque nœud interne a toujours deux enfants, sauf s'il n'y a qu'un seul symbole dans les données.

  L'exemple ici prend 8 octets (avec quelques bits non utilisés dans le dernier octet). C'est assez petit par rapport aux données, ça va.

  Les chiffres

  Avec les données de l'exemple,. on obtient les résultats suivants :

  • Taille originale : 271 octets (2168 bits)
  • Taille compressée : 666 bits (84 octets, avec 6 bits de padding)
  • Taille de l'arbre : 8 octets
  • Taille totale compressée : 92 octets

  Ce qui donne une taille finale compressée, arbre compris, de 33.95% de la taille originale.

  Combinaisons

  Si on regarde le flux compressé (hors arbre), voici ce que cela donne en hexadécimal :

  0xAA 0xAA 0xAA 0xAA 0xEA 0xA0 0x00 0x2A 0xAE 0xA0 0xDB 0x6D 0xB0 0x55 0xD0 0x6F 0xFF 0xFF 0xFF 0xC1 0x5D 0x1B 0xD5 0x55 0xFC 0x57 0x1B 0xD5 0x55 0x5F 0xC5 0xC6 0xF5 0x55 0x57 0xF1 0x71 0xBD 0x55 0x55 0xFC 0x5C 0x6F 0x55 0x55 0x7F 0x17 0x1B 0xD5 0x55 0x5F 0xC5 0xC6 0xF5 0x55 0x57 0xF1 0x74 0x6F 0x55 0x57 0xF1 0x5D 0x06 0xFF 0xFF 0xFF 0xFC 0x15 0xD4 0x1B 0x6D 0xB6 0x0A 0xBA 0xA8 0x00 0x0A 0xAB 0xAA 0xAA 0xAA 0xAA 0x80 
  

  Comme indiqué plus haut, on remarque des motifs qui se répètent. Ce flux est donc probablement un bon candidat pour une compression supplémentaire avec LZ par exemple. Pourquoi pas ?

  L'algorithme DEFLATE (utilisé dans le format .zip par exemple) fait le contraire : il applique d'abord LZ77 pour compresser les motifs répétitifs, puis applique Huffman pour compresser les symboles résultants. C'est un peu plus compliqué que cela, mais c'est l'idée générale, et c'est l'idée générale derrière plusieurs formats de compressions : des mélanges d'algorithmes.

  Conclusion

  Huffman est un algorithme de compression efficace sur des données avec des fréquences d'apparition de symboles non uniformes. Si tous les symboles sont également fréquents, il n'y aura pas d'avantage à utiliser Huffman par rapport à un codage fixe. De plus, il faut stocker l'arbre, il est donc important de vérifier que la taille gagnée par la compression compense la taille de l'arbre (il est aussi possible d'utiliser des arbres statiques connus à l'avance pour certains types de données, mais cela sera potentiellement moins efficace).

  On retrouve cet algorithme dans de nombreux formats de compression, souvent combiné avec d'autres algorithmes. C'est une des bases de la compression de données, il est donc intéressant de connaître son principe de fonctionnement.

  Cet article termine la petite série sur la compression de données sans perte.

  Supplément

  Le code que j'ai utilisé lors de l'écriture pour vérifier les exemples est disponible ici.

  ---

• Compression de données, le format ZX0 (2025-11-02)

  Après avoir présenté dans l'article précédent sur la compression LZ l'idée générale de référencement arrière de données déjà présentes en mémoire, cet article va se concentrer sur une implémentation spécifique de la famille LZ : le ZX0, un algorithme développé par Einar Saukas avec pour double objectif une taille très compacte pour le code de décompression et une recherche des choix optimaux lors de la compression.

  Au niveau du code de décompression, sur Z80 et pour reprendre les exemples fournis dans le README officiel, on a les chiffres suivants :

  • Routine "Standard" : 68 octets
  • Routine "Turbo" : 126 octets, environ 21% plus rapide
  • Routine "Fast" : 187 octets, environ 25% plus rapide
  • Routine "Mega" : 673 octets, environ 28% plus rapide

  Pour obtenir un code de décompression aussi compact, les choix faits dans le format ZX0 sont adaptés à un décodage avec peu de calculs et des calculs simples.

  Rentrons dans les détails.

  Le double flux

  ZX0 utilise deux flux de données distincts. Le premier flux contient les informations sur les blocs : quel type de bloc (littéral ou référence arrière), les offsets et les longueurs. Ce flux est lu bit par bit. Le second flux contient les données littérales elles-mêmes, lues octet par octet.

  Il suffit donc d'avoir une routine qui lit le bit suivant du premier flux et une routine qui lit l'octet suivant du second flux. Un pointeur suffit pour le second flux. Le premier flux est un peu plus complexe : il nécessite un pointeur, un octet courant et un compteur de bits restants dans l'octet courant. Cela reste très simple.

  Ces deux flux sont entrelacés. Lorsque l'une des deux routines a besoin d'un nouvel octet, elle le lit depuis les données compressées. Cela signifie qu'en fait, un seul pointeur est nécessaire pour parcourir les deux flux. De manière symétrique, cela signifie que lors de la compression, les données doivent être écrites en un seul flux en entrelaçant les deux types de données au fur et à mesure qu'elles forment un octet complet.

  Encodage des nombres

  À la fin de l'article précédent, la constatation était que les références avaient souvent des petites longueurs et qu'il pouvait être intéressant de trouver un moyen d'encoder ces petites longueurs de manière efficace.

  ZX0 prend acte et utilise un codage nommé « codage gamma » ou encore « codage gamma d'Elias » ("Elias Gamma coding").

  Principe du codage gamma

  Le codage gamma propose d’écrire un nombre en deux parties : la longueur binaire nécessaire et la valeur restante depuis la puissance de 2 inférieure.

  La longueur du nombre en binaire est encodée de manière unaire : on regarde combien de bits sont nécessaires pour écrire le nombre en binaire, on écrit cette valeur moins un en unaire (avec autant de 0 que le nombre voulu), puis on termine avec un 1. Incidemment, cela représente la puissance de deux inférieure nécessaire pour coder le nombre.

  Par exemple, pour le nombre 3, qui s'écrit 11 en binaire (2 bits), on écrit 01 (un 0 suivi d'un 1). Pour le nombre 10, qui s'écrit 1010 en binaire (4 bits), on écrit 0001 (trois 0 suivis d'un 1).

  Pour la valeur restante, on prend le nombre, on enlève la plus grande puissance de 2 qui ne dépasse pas ce nombre, puis on écrit le reste en binaire, sur le nombre de bits calculé précédemment (le nombre de fois où on a trouvé 0 avant le 1).

  Par exemple, pour le nombre 3, la plus grande puissance de 2 inférieure est 2 (\(2^1\)), donc le reste est \(3 - 2 = 1\), qui s'écrit 1 en binaire sur 1 bit. Pour le nombre 10, la plus grande puissance de 2 inférieure est 8 (\(2^3\)), donc le reste est \(10 - 8 = 2\), qui s'écrit 010 en binaire sur 3 bits.

  Ainsi on a :

  3  ->   01 1    (pour un total de 3 bits)
  10 -> 0001 010  (pour un total de 7 bits)
  

  Ce codage est efficace pour les petits nombres (jusqu'à 15), car il peut les écrire avec moins de 8 bits. En revanche, il devient moins efficace pour les nombres plus grands (par exemple 16 occupe 9 bits en codage gamma).

  Ce codage offre aussi l'avantage d'être sur un nombre de bits variable et de permettre la « découverte » de cette taille lors de la lecture.

  Mais pour rendre le décodage encore plus simple, ZX0 utilise une variante appelée « codage gamma entrelacé » qui permet de lire tous les bits dans l'ordre en une seule passe. L'entrelacement se fait entre la partie unaire et la partie binaire (dans le sens du plus petit bit vers le plus grand). Les bits de la première partie (unaire) sont les bits impaires et les bits de la seconde partie (binaire) sont les bits paires.

  Exemples :

  3  codé   01 1   devient 011
  10 codé 0001 010 devient 0001001
  

  Avec ce système, il suffit de lire un bit et s'arrêter s'il est à 1, sinon lire un autre bit pour la partie binaire, l'ajouter à l'accumulateur préalablement décalé vers la gauche. Puis recommencer jusqu'à trouver un 1. Pour que l'algorithme fonctionne, l'accumulateur doit être initialisé à 1.

  Par exemple, pour décoder 011 :

  • Lire 0 (unaire), on continue
  • Lire 1 (binaire), accumulateur = 1 << 1 | 1 = 3
  • Lire 1 (unaire), on s'arrête, valeur finale = 3

  Et pour décoder 0001001 :

  • Lire 0 (unaire), on continue
  • Lire 0 (binaire), accumulateur = 1 << 1 | 0 = 2
  • Lire 0 (unaire), on continue
  • Lire 1 (binaire), accumulateur = 2 << 1 | 1 = 5
  • Lire 0 (unaire), on continue
  • Lire 0 (binaire), accumulateur = 5 << 1 | 0 = 10
  • Lire 1 (unaire), on s'arrête, valeur finale = 10

  Les types de blocs

  Maintenant que l'on sait qu'il y a deux flux et comment encoder les nombres, voyons comment ZX0 organise les blocs de données. Il existe trois types de blocs :

  • Bloc littéral : contient les données littérales. Est associé à une longueur.
  • Bloc de référence : référence une séquence de données précédemment rencontrée. Est associé à un offset et une longueur.
  • Bloc de référence de même offset : tout comme un bloc de référence, mais réutilise le dernier offset utilisé et ne spécifie donc que la longueur.

  Pour différencier ces trois types de blocs, ZX0 utilise un seul bit. Un seul bit pour désigner trois types de blocs ? Cela est possible car certaines contraintes logiques existent entre les blocs :

  • Deux blocs littéraux ne peuvent pas se suivre (sinon ils seraient fusionnés en un seul bloc littéral).
  • Un bloc de référence de même offset ne peut apparaître qu'après un bloc littéral.
  • Le premier bloc est toujours un bloc littéral (et d'ailleurs le tout premier bit qui devrait indiquer le type de bloc est omis).

  Ainsi, le bloc littéral et le bloc de référence de même offset sont tous deux indiqués par un 0 et le bloc de référence avec nouvel offset est indiqué par un 1. Le contexte permet de savoir quel type de bloc est concerné entre les deux premiers.

  Les longueurs sont encodées en utilisant le codage gamma entrelacé décrit précédemment. Pour les offsets, c'est un peu plus compliqué : l'offset est divisé en deux parties, le MSB (Most Significant Byte) utilise le codage gamma entrelacé, tandis que le LSB (Least Significant Byte) est stocké tel quel sur 7 bits (au lieu de 8). Comme on ne peut pas encoder 0 en gamma, le MSB de l'offset est stocké avec une valeur augmentée de 1.

  Autre petite optimisation : puisqu'une référence avec nouvel offset a toujours une longueur minimale de 2, la longueur stockée pour une référence est en fait la longueur moins 1.

  Exemples :

  0 011               -> bloc littéral de longueur 3
                         (ou bien référence de longueur 3 selon le contexte)
  1 1 0000011 0001001 -> bloc de référence avec nouvel offset de longueur 3
                         (1 en codage gamma pour MSB = 0)
                         (0000011 pour LSB = 3)
                         et longueur 11 (10 + 1)
  

  Recherche optimale

  Lors de l'article précédent qui présentait l'idée derrière la compression LZ, il avait été question de prendre en référence arrière la plus grande séquence identique possible. Cela fonctionne : c'est un type d'algorithme glouton (greedy). Cependant, cette méthode n'est pas forcément (pas souvent ?) optimale. Peut-être que prendre à un endroit le motif le plus long empêche de faire un meilleur choix de référence un peu plus loin. Ou bien peut-être que cela cause des codages gamma sur trop de bits. L'algorithme ZX0 fait le choix de trouver la solution optimale.

  Pour cela, à chaque position lors de la compression, l'algorithme va examiner tous les offsets possible et regarder s'il est possible de faire une référence arrière et maintenir une chaîne optimale en calculant le coût total si une référence devait être faite à cet endroit.

  L'algorithme fait appel à de la programmation dynamique pour obtenir un code compact et efficace. Efficace, mais pas rapide : la compression avec ZX0 est lente avec des fichiers un peu conséquents, c'est son principal inconvénient. Mais en échange, on est assuré que, avec les choix de codage de ce format, le résultat est le plus compact possible.

  Test sur l'exemple

  Reprenons à nouveau l'image en niveaux de gris des deux articles précédents et voyons ce que cela donne avec le format ZX0.

  L'exemple, pour rappel :

  ................
  ....#######.....
  ..##@@@@@@@##...
  .##@OOOOOOO@##..
  .#@OoooooooO@#..
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  .#@OoooooooO@#..
  .##@OOOOOOO@##..
  ..##@@@@@@@##...
  ....#######.....
  ................
  

  Le résultat de la compression avec ZX0 est le suivant :

  File compressed from 272 to 51 bytes! (delta 3)
  

  Soit un fichier final ayant un peu moins de 19% de la taille originale. Pour rappel, la compression RLE et LZ « naïve » avaient donné un fichier de 57% la taille originale. C'est nettement mieux.

  Voici le contenu de fichier final :

  0000000  95  2e  89  0a  2e  a4  23  f7  de  b9  ed  40  fe  ff  ef  de
  0000010  ee  e0  4f  fe  7f  dc  fb  de  e1  6f  9f  fe  dd  fc  de  e0
  0000020  f7  dc  91  de  1f  12  5d  d7  ce  75  8a  d9  46  1d  d7  02
  0000030  55  55  80  
  

  On peut s'amuser à décoder le début à la main.

  On garde le premier octet $95 (10010101 en binaire) en mémoire, il s'agit des informations de blocs. Le premier bloc est toujours un bloc littéral, on commence donc par une longueur en codage gamma entrelacé. 1 signifie une longueur de 1. On lit donc le premier octet du flux littéral : $2e (le caractère .). Nous voici avec notre premier caractère décodé.

  On continue à lire ce qu'il reste de notre octet $95 : le bit suivant est un 0. Puisque le bloc précédent était un bloc littéral, ce 0 indique un bloc de référence de même offset. Le offset précédent est initialisé à 1 en début d'algorithme. On a donc une référence de 1 en arrière (le caractère . déjà décodé). Reste à lire la longueur en codage gamma entrelacé : 010101... le nombre n'est pas terminé, il nous faut un nouvel octet depuis le flux. C'est $89 (10001001 en binaire).

  On continue la lecture : 1. Le bit de fin du codage gamma. Ce qui donne au final 0101011, soit 0001 111 en désentrelacé, soit une longueur de 15. On copie donc 15 fois le caractère trouvé une position avant. Nous voici avec 16 caractères . décodés. À noter qu'il n'y avait qu'un seul octet dans le flux littéral, mais la copie avance en recopiant le caractère déjà décodé. Avec une référence arrière de 1, il y a autant de copie de . que nécessaire.

  Continuons. Le prochain bloc est indiqué par le bit suivant : 0. Puisque le bloc précédent était une référence, ce 0 indique un bloc littéral. On lit la longueur en codage gamma entrelacé : 001, soit 01 0 en non entrelacé, ce qui signifie 2. On lit donc les deux octets suivants dans le flux littéral : $0a (le caractère de retour chariot) et $2e (le caractère .). Nous venons de compléter la première ligne de l'image et de débuter la seconde.

  Vous pouvez continuer si vous le souhaitez, mais je m'arrête ici pour cet exemple.

  Fonctionnalités avancées

  Avant de refermer cet article, il est intéressant de noter que ZX0 propose quelques fonctionnalités supplémentaires.

  La compression à rebours

  Plutôt que de compresser les données du début à la fin du fichier d'entrée, ZX0 permet de compresser les données en commençant par la fin du fichier d'entrée. L'algorithme est le même, sauf que le flux commence par la fin et que les références « arrières » sont « plus loin » en mémoire (puisque le début du flux est à la fin du fichier).

  Cela est intéressant dans des scénarios où les données compressées et décompressées se recouvrent (ce qui est tout à fait possible aussi avec la compression standard) et que l'on veut « viser » l'adresse mémoire la plus haute disponible.

  En effet, lors d'un recouvrement, l'algorithme à besoin d'un « décalage minimum » entre les deux flux de données (indiqué par le « delta » affiché lors de la compression). Pour bien comprendre ce que signifie ce delta et l'intérêt de la compression à rebours, le mieux est de consulter les diagrammes fournis dans le README.

  Compression avec préfixe

  Très pratique pour des décompressions « par morceaux », il est possible de fournir au compresseur un préfixe de données que l'on sait seront déjà présentes en mémoire lors de la décompression juste avant les nouvelles données à décompresser.

  Le compresseur pourra donc piocher les références dans ce préfixe, sans pour autant inclure ces données dans le flux compressé. Bien entendu, il faut garantir que ces données seront bien présentes en mémoire lors de la décompression, puisque le décompresseur va les référencer.

  Mode rapide

  Enfin, du fait de la recherche optimale, la compression avec ZX0 peut être assez lente. Le compresseur propose donc une option « rapide » pour diminuer le temps de compression. L'option -q a pour effet de réduire fortement la fenêtre de recherche des références arrière qui est normalement de 32640 octets et passe à 2176 octets.

  La recherche optimale est toujours effectuée, mais en allant chercher beaucoup moins loin les blocs pouvant être référencés. Cela diminue fortement le temps de compression, mais potentiellement aussi le taux de compression.

  Pour l'exemple ci-dessus, dont la taille totale est bien inférieure à 2176 octets, cela ne change rien du tout. Ni en temps, ni en taille finale.

  Conclusion

  ZX0 est un algorithme de compression assez populaire sur les machines 8 bits. Le code source est disponible, il est simple à mettre en oeuvre, le code de décompression est très compact. Il a même été porté sur d'autres processeurs que le Z80.

  Bien qu'un peu lent à compresser, le résultat de compression est bon et la décompression rapide. Ça en fait un très bon choix.

  J'espère avoir pu vous donner une idée des choix faits par cet algorithme de compression/décompression et de son fonctionnement. Pas de code source dans cet article, j'ai directement utilisé l'implémentation officielle.

  ---

• Compression de données, référencer les répétitions (2025-10-24)

  Dans l'article précédent sur la compression, l'idée était de remplacer les successions d'éléments identiques par un couple (nombre de répétitions, valeur). Cela fonctionne bien avec des plages de données contenant un même élément, mais beaucoup moins bien lorsque les données changent fréquemment.

  La séquence suivante, par exemple, sera très mal compressée par cette méthode RLE :

  .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
  

  En effet, cette séquence ne contient aucune répétition d'un élément unique. Chaque élément est différent du précédent. Avec la méthode RLE, on devrait écrire :

  (1, .), (1, #), (1, .), (1, #), ... 
  

  On peut avoir envie de se dire, avec cette séquence, que le motif à répéter est .# et qu'on le répète 16 fois. Mais on pourrait aussi se dire que c'est 4 fois le motif .#.#.#.#. Ou encore 2 fois le motif .#.#.#.#.#.#.#.#. Dans tous les cas, il nous faudrait une sorte de dictionnaire pour référencer les motifs que l'on voudrait répéter.

  Et c'est une manière assez courante de compresser des données : référencer un dictionnaire.

  Cependant, un dictionnaire, ça prend de la place. Et dans la compression que nous allons voir aujourd'hui, la méthode est d'utiliser les données elles-mêmes comme dictionnaire pour éviter de construire (et stocker) un dictionnaire à part. C'est la méthode LZ (Lempel-Ziv), du nom de ses inventeurs, ou en tout cas une manière dérivée de LZ.

  Le dictionnaire

  L'idée est la suivante : lorsque l'on en est à un point du flux de décompression, toutes les données précédemment décompressées sont disponibles en mémoire.

  Imaginons par exemple, avec la séquence précédente, que l'on a déjà décompressé les deux premiers caractères : .#. On peut tout à fait commencer à référencer ce motif dans le flux à decompresser qui arrive. La séquence à décompresser suivante pourrait être « répète le motif de longueur 2 qui commence 2 positions avant ». Ce qui donnerait, une fois ajouté aux données déjà décompressées : .#.#.

  À l'étape suivante, on pourrait avoir : « répète le motif de longueur 4 qui commence 4 positions avant ». On aurait à présent : .#.#.#.#

  Et ainsi de suite.

  Codage général

  Ainsi, il nous faut construire un flux compressé qui est une suite d'éléments unitaires (des séquences qui n'ont pas encore été vues) et de références à des motifs déjà vus (avec une paire (position en amont, longueur)).

  Sans entrer dans une implémentation précise, pour le motif précédent, on pourrait avoir ceci :

  .# (suite d'éléments unitaires)
  (-2,2) (référence au motif de longueur 2, 2 positions avant)
  (-4,4) (référence au motif de longueur 4, 4 positions avant)
  (-8,8) (référence au motif de longueur 8, 8 positions avant)
  (-16,16) (référence au motif de longueur 16, 16 positions avant)
  

  Si on utilise un élément marqueur pour indiquer si ce qui suit est une suite d'éléments unitaires ou une référence, cela donnerait globalement 15 éléments pour représenter les 32 éléments de l'original. Soit une taille finale d'un peu plus de 40% de l'original.

  Pas mal.

  Note : en vrai, on ne référencera pas des motifs aussi petits que deux éléments, car le gain en taille ne serait pas suffisant. Avec ce codage simpliste, il faut au moins 4 éléments pour référencer un motif de manière efficace.

  Méthode de compression

  Afin de compresser un flux de données avec cette méthode, à chaque étape, il faut chercher dans le flux en entrée si le motif qui suit est présent dans les données précédentes. Et ce pour la longueur la plus grande possible.

  Pour l'exemple, lorsque l'on commence le flux, le premier caractère est un .. Ce caractère n'est pas encore dans les données présentes (puisque c'est le premier). On l'écrit donc comme élément unitaire dans le flux compressé. De même pour le caractère suivant, un #, que l'on écrit aussi en tant qu'élément unitaires à la suite du premier.

  Pour la suite, on a dans le buffer à traiter une séquence .#.#.#.#.... On cherche le plus long motif qui est déjà dans les données. Ici, c'est .#, que l'on trouve à la position -2 (2 positions avant). On écrit donc la référence (-2,2) dans le flux compressé.

  Et ainsi de suite, jusqu'à la fin du flux d'entrée.

  Essai sur la séquence de l'article précédent

  Je reprends l'image en niveaux de gris de l'article précédent sur la compression RLE :

  ................
  ....#######.....
  ..##@@@@@@@##...
  .##@OOOOOOO@##..
  .#@OoooooooO@#..
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  .#@OoooooooO@#..
  .##@OOOOOOO@##..
  ..##@@@@@@@##...
  ....#######.....
  ................
  

  Dans le cas RLE, j'avais supprimé les sauts de ligne pour ne garder qu'une suite d'éléments et profiter des plages formées par la fin d'une ligne et le début de la ligne suivante. Ici, je vais les garder, c'est beaucoup moins génant puisque la méthode compresse les séquences répétées.

  Passé par l'algorithme décrit précédemment, voici ce que l'on obtient :

    Littéral:  (0, '....')
    Référence: (1, (-4, 4))
    Référence: (1, (-8, 8))
    Littéral:  (0, '\n')
    Référence: (1, (-5, 4))
    Littéral:  (0, '#######')
    Référence: (1, (-17, 8))
    Littéral:  (0, '##@@@@@@@')
    Référence: (1, (-19, 5))
    Littéral:  (0, '\n')
    Référence: (1, (-16, 4))
    Littéral:  (0, 'OOOOOOO')
    Référence: (1, (-18, 5))
    Littéral:  (0, '\n.#@OoooooooO@')
    Référence: (1, (-17, 4))
    Référence: (1, (-16, 10))
    Référence: (1, (-18, 6))
    Référence: (1, (-17, 17))
    Référence: (1, (-34, 34))
    Référence: (1, (-34, 34))
    Littéral:  (0, '\n.')
    Référence: (1, (-18, 10))
    Référence: (1, (-16, 4))
    Référence: (1, (-17, 4))
    Littéral:  (0, '#@OOOOOOO@#')
    Référence: (1, (-17, 5))
    Référence: (1, (-18, 4))
    Littéral:  (0, '@@@@@')
    Référence: (1, (-16, 5))
    Référence: (1, (-17, 4))
    Référence: (1, (-19, 4))
    Littéral:  (0, '###')
    Référence: (1, (-15, 5))
    Référence: (1, (-17, 7))
    Référence: (1, (-10, 5))
    Référence: (1, (-7, 7))
  

  Ce qui donne une entrée de 272 éléments (256 éléments plus les retours chariots) compressée en 156 éléments, soit environ 57% de la taille initiale.

  C'est légèrement moins bien que la méthode RLE pour ce cas qui avait été construit spécialement pour que ça fonctionne bien en RLE. Donc... ce n'est pas mal du tout (et on a les retours chariots en bonus).

  Peut-on faire mieux ?

  Comme la dernière fois, pour le moment, on a une implémentation assez générique que l'on compte en éléments. Si on considère que ces éléments sont en fait des octets, il y a beaucoup de place perdue, ne serait-ce que par l'utilisation d'un octet complet pour différencier les littéraux des références.

  De même, on peut se poser la question de l'utilisation d'un octet complet pour la position et la longueur dans les références, alors que les plus grandes valeurs absolues utilisées dans cet exemple sont 34. On pourrait limiter ces valeurs à 4 bits chacun pour coder les deux valeurs sur un seul octet.

  J'ai fait l'essai... et ce n'est pas brillant. La compression est alors assez mauvaise, passant alors à un résultat compressé de 225 octets.

  Par contre, en utilisant une valeur maximale de 32, alors on retrouve le taux de compression précédente.

  Mais plus que la valeur maximale, il est intéressant de s'intéresser à la répartition des valeurs utilisées.

  Grâce à un petit programme d'analyse, voici ce que j'obtiens pour cet exemple :

  Distribution des longueurs de référence:
    Valeur | Occurrences | Histogramme
    -------|-------------|------------
         4 |           9 | #########
         5 |           6 | ######
         6 |           1 | #
         7 |           2 | ##
         8 |           2 | ##
        10 |           2 | ##
        17 |           1 | #
        34 |           2 | ##
    Statistiques: Min=4, Max=34, Moyenne=8.28, Médiane=5.0
  
  Distribution des positions de référence (valeurs absolues):
    Valeur | Occurrences | Histogramme
    -------|-------------|------------
         4 |           1 | #
         5 |           1 | #
         7 |           1 | #
         8 |           1 | #
        10 |           1 | #
        15 |           1 | #
        16 |           4 | ####
        17 |           7 | #######
        18 |           4 | ####
        19 |           2 | ##
        34 |           2 | ##
    Statistiques: Min=4, Max=34, Moyenne=16.40, Médiane=17.0
  
  Distribution combinée (longueurs + positions):
    Valeur | Occurrences | Histogramme
    -------|-------------|------------
         4 |          10 | ##########
         5 |           7 | #######
         6 |           1 | #
         7 |           3 | ###
         8 |           3 | ###
        10 |           3 | ###
        15 |           1 | #
        16 |           4 | ####
        17 |           8 | ########
        18 |           4 | ####
        19 |           2 | ##
        34 |           4 | ####
    Statistiques: Min=4, Max=34, Moyenne=12.34, Médiane=10.0
  

  On peut remarquer que même si l'amplitude des valeurs est grande (de 4 à 34), la moitié des valeurs utilisées sont plutôt petites (entre 4 et 10), et la moyenne n'est pas très élevée non plus. Est-ce que ça ne vaudrait pas le coup d'utiliser un codage variable pour ces valeurs, afin de privilégier les petites valeurs ?

  C'est sur cette piste que part l'algorithme ZX0, que nous verrons dans un prochain article.

  À noter que une piste est possible en calculant une représentation des valeurs adaptée à leurs distributions. Pour cela, on peut utiliser un codage de Huffman, et c'est la piste utilisée par l'algorithme DEFLATE (utilisé dans les fichiers ZIP et PNG entre autres).

  Conclusion

  Avec cette méthode de compression par références dans un dictionnaire construit, il est possible de compresser des flux de données avec beaucoup plus de variations qu'avec la méthode RLE. LZ est en fait la base de beaucoup d'algorithmes de compression sans pertes. Le temps de compression est « élevé » car il est nécessaire de chercher des motifs dans des plages de données (la recherche peut d'ailleurs être paramétrée selon ce que l'on veut). La décompression est en revanche assez rapide, il n'y a pas de calculs ou d'opérations complexes à faire.

  Supplément

  Le code que j'ai utilisé lors de l'écriture pour vérifier les exemples est disponible ici.

  ---

• Briques Stellaires, jeu pour PHC-25 (2025-10-12)

  Avec la publication de la version 0.9 de Briques Stellaires, ma contribution à la Game Jam « Retro Programmers United for Obscure Systems » session PHC-25 est l'occasion de revenir sur cette session et ma proposition.

  Vu les caractéristiques modestes mais sympathiques du PHC-25, j'ai eu envie de faire un jeu plutôt action. Exercice toujours délicat pour ces machines peu utilisées dont les émulateurs sont très très perfectibles, pour ne pas dire à côté de la plaque. Mais ayant eu un accès temporaire à la machine, je ne me suis dit que... allez pourquoi pas.

  J'étais parti sur un twist du classique casse-brique. Au final, le temps passant toujours à sa proverbiale vitesse, le jeu est... un casse-brique tout ce qu'il y a de plus standard.

  Mais voyons un peu les détails potentiellement intéressants du développement.

  L'environnement de développement

  Je suis parti pour cette contribution sur un développement en assembleur Z80. Je le regretterai plus d'une fois, quand il m'a fallu mettre au point la routine de rebond. Mais comme je savais que cela serait potentiellement compliqué avec des regressions très probables, j'ai cherché dès le début un environnement me permettant de faire des tests unitaires.

  J'avais déjà mis en place des tests unitaires pour le jeu sur VG5000, cependant, ils devaient être lancés en même temps que l'exécutable principal. Puis c'était un bricolage rapide qui manquait de fonctionnalités.

  Je suis donc parti sur un environnement déjà fait : DeZog. C'est un environnement intégré à Visual Code, initialement fait et spécialisé pour le ZX Spectrum, mais qui peut être utilisé comme environnement Z80 générique. DeZog supporte l'exécution de tests unitaires, avec de nombreuses assertions, le tout pouvant tourner dans un émulateur interne.

  DeZog implémente aussi un lien de debuggage avec différents émulateurs, dont MAME. Parfait pour la mise au point.

  Les choix pour le PHC-25

  Il y a plusieurs modes graphiques sur le PHC-25, qui utilise comme VDP un clone du MC6847 avec le maximum de RAM vidéo supportée. On peut considérer qu'il y a deux grandes classes de modes graphiques : des modes alpha-numérique/semi-graphique, et des modes bitmap, avec des variations dans les contraintes.

  Pour le jeu, j'ai choisi un mode alpha-numérique/semi-graphique qui permet d'avoir une résolution en « gros pixels » de 68x48. C'est suffisant pour un casse-brique.

  Pas de son ni de joystick, car le PHC-25 a besoin d'une extension pour cela. Et puis... le temps, toujours le temps.

  Liste d'affichage

  Sur le PHC-25, le MC6847 utilise pour RAM vidéo une mémoire directement accessible par le bus du Z80. Et lorsqu'il y a arbitrage, c'est le Z80 qui gagne. Ainsi, des accès à la mémoire vidéo pendant le rafraîchissement de l'écran provoquent des parasites bien visibles.

  Il faut donc absolument éviter d'accéder à la mémoire vidéo pendant le rafraîchissement. C'est d'ailleurs ce que fait la ROM du PHC-25 où les commandes graphiques sont appliquées progressivement pendant l'interruption (INT), branchée sur VBLANK.

  Et c'est aussi ce que je fais dans Briques Stellaires. Après avoir passé le Z80 en mode d'interruption IM2 (il n'y a pas de possibilité prévue par le système pour s'accrocher à l'interruption en IM1), je déroule des listes d'affichages au moment de l'interruption. Ces listes d'affichages sont elles-mêmes construites pendant le reste du temps, par des accès en RAM normale exclusivement.

  Ces listes d'affichages sont de type : afficher une brique, effacer une brique, effacer et afficher la balle,...

  Le traitement de l'affichage du contour de jeu ainsi que des pages de titre et de score est un peu différent : je prépare l'affichage dans un buffer auxiliaire de la taille de l'écran, puis je copie ce buffer en RAM vidéo pendant le VBLANK, petit à petit.

  L'affichage de la raquette est similaire : il est fait dans le buffer auxiliaire, puis la ligne correspondante est copiée en RAM vidéo pendant le VBLANK systématiquement. C'est un choix que j'ai fait assez tôt car je ne savais pas trop à quelle vitesse la raquette allait bouger et je voulais un système simple, avec un temps fixe pendant la VBLANK.

  La physique

  Voilà qui m'a pris plus de temps que prévu. Je savais que cela allait être délicat, avec des rebonds particuliers et des vitesses non entières. En effet, les coordonnées de la balle sont en virgule fixe, 8 bits pour la partie entière, 8 bits pour la partie fractionnaire. Là encore, c'est un choix que j'ai fait assez tôt, car je ne savais pas quelle vitesse de balle allait être intéressante. Et avec la résolution de l'écran, des vitesses entières allaient donner des mouvements bien trop rapides.

  Pour les collisions, je trace une ligne entre la position précédente et la position actuelle de la balle, point par point, en testant les collisions avec les briques, la raquette et les bords. La ligne ne fait rarement plus de deux pixels, mais là encore, cela permet de gérer différentes vitesses, donc des vitesses supérieures à 1 par axe.

  Par contre, j'ai simplifié : une collision arrête immédiatement la trajectoire. Je ne cherche pas à compléter le mouvement restant après le rebond. Aux vitesses utilisées au final par le jeu, la différence est imperceptible.

  La gestion de variables

  Puisque le jeu est sur cassette, il est toujours intéressant de minimiser la taille des données encodées. Pour gagner de la place, j'ai implémenté avec le système de STRUCT et de macros de sasmjsplus qui permet de « déclarer » des variables près du code, mais qui sont toutes regroupées à la fin du code lors de l'assemblage.

  Au démarrage du programme, je fixe toute la zone à zéro. Un peu à la manière d'une section BSS dans un programme C.

  J'avais envisagé d'utiliser un système de compression, surtout pour les niveaux. Mais le manque de temps et finalement la taille relativement modeste du programme (moins de 3ko) m'ont fait abandonner cette idée.

  Conclusion

  Briques Stellaires est un casse-brique très rudimentaire. Et autant que je puisse m'en souvenir, c'est la première fois que je programme un casse-brique. Je me suis perdu dans la gestion de collisions et malgré les tests unitaires qui m'ont gardé sur les rails, j'y ai passé beaucoup de temps. Un peu avant la date limite de la jam, j'ai coupé dans toutes mes idées un peu originales pour me concentrer sur l'essentiel : un jeu auquel on peut jouer.

  

  ---

• Compression de données, compter les répétitions (2025-07-28)

  Dès le début de l'informatique, même si je ne saurais pas dater exactement quand, il a été question de stocker ou transmettre des données de manière efficace. Comment stocker ou transmettre un maximum de données avec un minimum d'espace ou de bande passante ? La compression de données répond à cette problématique avec des algorithmes qui repèrent l'information redondante pour la représenter de manière plus concise, ou bien qui éliminent des données jugées'(selon certains critères) moins utiles que d'autres.

  Dans ce premier article, nous allons voir ce que j'imagine être la plus simple des méthodes et qui vient souvent à l'esprit en premier lorsque l'on découvre le sujet : la compression RLE (Run Length Encoding).

  Le flux d'entrée

  Imaginons une image en niveaux de gris que l'on pourrait représenter de cette manière :

  ................
  ....#######.....
  ..##@@@@@@@##...
  .##@OOOOOOO@##..
  .#@OoooooooO@#..
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  #@OoooooooooO@#.
  .#@OoooooooO@#..
  .##@OOOOOOO@##..
  ..##@@@@@@@##...
  ....#######.....
  ................
  

  Les niveaux de gris sont représentés par des caractères, et chaque caractère représente un pixel de l'image. L'image est de 16 lignes et 16 colonnes, soit 256 éléments. Ne nous occupons pas pour le moment de comment coder ces éléments. Ce sont juste des éléments.

  L'idée générale

  L'idée de la compression RLE vient de la constatation rapide qu'il existe des suites de données identiques dans les données, et que l'on peut même facilement énoncer. Par exemple, sur la première ligne, on peut dire qu'il y a 16 fois la valeur .. Sur la deuxième ligne, on peut dire qu'il y a 4 fois la valeur . puis 7 fois la valeur # puis 5 fois la valeur .. Et ainsi de suite.

  C'est le principe de la compression RLE : on va remplacer les suites d'éléments identiques par deux éléments : le nombre de répétitions et la valeur répétée. Par exemple, la première ligne devient (16, '.'), la deuxième ligne devient (4, '.'), (7, '#'), (5, '.').

  Voilà ce que cela donne pour l'image complète, si on met toutes les lignes bout à bout (sans les sauts de ligne) :

  (20,.), (7,#), (7,.), (2,#), (7,@), (2,#), (4,.), (2,#), (1,@), (7,O), (1,@), (2,#), (3,.), (1,#), (1,@), (1,O), (7,o), (1,O), (1,@), (1,#), (2,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (2,.), (1,#), (1,@), (1,O), (7,o), (1,O), (1,@), (1,#), (3,.), (2,#), (1,@), (7,O), (1,@), (2,#), (4,.), (2,#), (7,@), (2,#), (7,.), (7,#), (21,.)
  

  Ce qui donne 89 couples de valeurs, soit 178 éléments au total. Contre 256 éléments dans l'image d'origine. On a donc bien réduit le nombre d'éléments nécessaires pour représenter l'image.

  Mais attention, ce qui permet la réduction, ce sont les suites de même valeur.

  Si les données sont constituées de valeurs souvent changeantes, la compression ne va pas bien fonctionner, voire donner plus d´éléments en sortie. Par exemple, si l'image n’était constituée que de valeurs différentes de leurs précédentes, on devrait à chaque fois écrire (1, élément), et donc au final doubler le nombre d'éléments nécessaires. Pas très efficace.

  Codage du flux compressé

  Jusqu'à maintenant, on n'a parlé que d'éléments. Cependant, ces éléments doivent être codés d'une manière ou d'une autre pour être stockés sur la machine. Par exemple, on peut considérer assez facilement que le flux d'entrée est codé en caractères sur 8 bits. C'est trop pour 4 valeurs différentes (2 bits sont suffisants), mais on peut imaginer avoir d'autres valeurs sur les 256 possibles dans d'autres images.

  On va donc garder cette représentation en 8 bits pour les éléments valeurs. Même en sortie.

  Pour le nombre de répétitions, il faut faire un choix sur le plus grand nombre de répétitions possibles. Ces choix vont dépendre de la nature des données. Pour un premier choix, on va faire simple : 256 répétition maximum. Une image de 16x16 éléments monochrome serait donc codée par deux valeurs en 8 bits : (0, valeur). En effet, comme une répétition de 0 n'a pas de sens, on se sert du 0 pour coder 256.

  Deux octets au lieu de 256, c'est pas mal. Mais on peut aussi imaginer que les images monochromes ne sont pas représentatives.

  En prenant un octet pour les répétitions et un octet pour la valeur, le codage et le décodage sont très simples et la taille pour l'image exemple est de 178 octets, soit 178 octets pour 256 éléments.

  Peut-on faire mieux ?

  Oui. Il y a plusieurs manières différentes de coder un flux compressé RLE. La méthode indiquée précédemment est la plus simple. Mais on peut en imaginer d'autres.

  Par exemple, on peut réserver une plage de nombres dans l'indication des répétitions pour indiquer un nombre d'octets à suivre qui seront recopiés tels quels (parce qu'ils ne présentaient pas de répétition en entrée).

  Par exemple, sur un morceau en entrée comme :

  ....#.#.#.....
  

  On code les valeurs

  (r4, '.'), (c5, '#.#.#'), (r3, '.')
  

  Où r signifie "répétition" et c signifie "copie".

  D'un point de vue codage, on peut choisir que les valeurs 0 à 127 représentent des répétitions, et les valeurs 128 à 255 représentent des copies.

  Voilà ce que cela donne pour l'image complète avec cette méthode :

  (20,.), (7,#), (7,.), (2,#), (7,@), (2,#), (4,.), (2,#), (129,@), (7,O), (129,@), (2,#), (3,.), (131,#@O), (7,o), (131,O@#), (2,.), (131,#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (131,O@#), (2,.), (131,#@O), (7,o), (131,O@#), (3,.), (2,#), (129,@), (7,O), (129,@), (2,#), (4,.), (2,#), (7,@), (2,#), (7,.), (7,#), (21,.)
  

  47 éléments au lieu de 89. Des éléments de taille variable cependant. Ici la taille en octets est de 136 plutôt que 178. Ce qui est un nouveau gain (au prix d'une toute petite complexité supplémentaire à traiter à la décompression)

  Peut-on faire encore mieux ?

  Vous pouvez trouver d'autres manières de coder un flux compressé RLE. En fonction de la plateforme, de la nature des données, de la taille des éléments, etc, il est possible de trouver des ajustements et des variations qui permettent de gagner de la place.

  Conclusion

  La compression RLE est une méthode simple à comprendre et à implémenter. Le temps de compression et de décompression sont très rapides car les calculs sont très simples.

  Elle peut donner de bons résultats sur des données avec beaucoup de plages de même valeur. C'est aussi une méthode non destructive : une fois décompressées, les données sont identiques à l'original avant compression.

  Dans un prochain article, nous verrons une autre méthode de compression classique et qui fonctionne bien sur des répétitions de motifs.

  Supplément

  Le code que j'ai utilisé lors de l'écriture pour vérifier les exemples est disponible ici.

  ---

Page 1 / 24 (suivant) »