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 271 éléments (256 éléments plus les retours chariots) compressée en 156 éléments, soit environ 57.6% 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.