Dans un monde où la quantité d’information numérique qui transite dépasse l’imagination (en une seconde, le trafic internet dépasse les 60,000 gigaoctets : plus de 2,000,000 de mails sont envoyés, Google répond à environ 70,000 requêtes, pas loin de 80,000 vidéos youtube sont regardées, etc.), des algorithmes de compression de données efficaces sont indispensables. Ces derniers ont pour rôle de représenter de manière compacte nos fichiers, que ce soit vidéos, textes, musiques etc., afin de nous faire gagner à la fois du temps – lors du partage de nos stories préférées à nos amis par exemple – mais aussi de l’espace sur nos chers disques durs.
Les plus populaires d’entre eux sont certainement ceux basés sur les
algorithmes dits de Lempel-Ziv – du nom de leurs créateurs
Abraham Lempel et Jacob Ziv – qui font d’ailleurs partie de la
prestigieuse liste des IEEE
milestones qui
recense les avancées historiques majeures en ingénierie électrique et
électronique. On les retrouve par exemple dans le format d’image gif
ou encore dans les archives zip. Nous nous intéressons ici à l’un
d’entre eux, LZ’78 de son petit nom.
Un scénario pour le moins étrange
Supposons ce qui suit : vous utilisez votre algorithme de compression favori pour compresser un fichier plutôt volumineux, disons 1 To pour se donner une idée, et vous obtenez une compression de 100 Mo. Cette nouvelle taille étant très petite – vous gagnez un facteur 10000 par rapport à l’original – vous devriez être plutôt content. Imaginez maintenant qu’un Sherlock de la grammaire vous fasse remarquer une petite coquille. Aucun problème, vous corrigez votre fichier original, vous le compressez à nouveau… mais cette fois… la nouvelle compression n’est que de 0.9 To ! Quoi ?? Perdre quasiment votre facteur 10000 pour une seule lettre de différence ?! Heureusement, la plupart des algorithmes n’ont pas ce comportement étrange, mais si votre algorithme favori s’appelle LZ’78, l’un des plus étudiés et utilisés, alors ceci pourrait bien arriver. En gros, c’est ce qui est montré dans cet article publié et présenté à la conférence SODA en 2018, et que j’aimerais brièvement expliquer dans ce post.
Mais comment ça fonctionne d’ailleurs, ce fameux LZ’78 ?
Vous pouvez passer cette section si les détails techniques de l’algorithme ne vous intéressent pas particulièrement.
Son fonctionnement est très simple. LZ’78 compresse des fichiers, un fichier étant une suite de 0 et de 1 pour un ordinateur, je vais vous montrer comment l’algorithme compresse ce qu’on appelle en informatique un mot, qui n’est en fait rien d’autre qu’une séquence de 0 et de 1. Prenons un exemple concret de mot m, disons $$m = 000101101000010011$$
Première étape : on va lire le mot de gauche à droite et placer un curseur dès que l’on voit un bloc que l’on n’a pas encore vu.
- La première lettre lue est 0, c’est un bloc que l’on n’a pas encore vu, alors on place un petit curseur juste après. Ce qui donne $$0 - 00101101000010011$$
- La deuxième lettre lue est 0, c’est un bloc connu, alors on continue. On lit ensuite un 0, ce qui forme le bloc encore inconnu 00, on ajoute donc un curseur. $$0 - 00 - 101101000010011$$
- On continue le processus jusqu’à la fin, ce qui donne le découpage suivant $$0 - 00 - 1 - 01 - 10 - 100 - 001 - 0011$$
Deuxième étape : on numérote chaque bloc dans l’ordre d’apparition, ce qui se schématise sous la forme du tableau suivant.
| Bloc | 0 | 00 | 1 | 01 | 10 | 100 | 001 | 0011 |
|---|---|---|---|---|---|---|---|---|
| Numéro de bloc | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
- Troisième étape : remarquons maintenant que chaque bloc (sauf 0 et 1) est l’extension d’un bloc qui le précède. Par exemple le bloc numéro 6 est l’extension du bloc numéro 5 par l’ajout d’un 0 à sa droite. Nous représentons ceci par le couple (5,0) et nous disons que 100 = (5,0). Le bloc numéro 4 est l’extension du bloc numéro 1 par l’ajout d’un 1. Donc 01 = (1,1) . On applique cette nouvelle représentation à chaque bloc du mot m, ce qui donne l’encodage final suivant :
$$m = (\star,0).(1,0).(\star,1).(1,1).(3,0).(5,0).(2,1).(7,1)$$ où les blocs avec les étoiles représentent les blocs qui n’ont pas de prédecesseurs.
L’avantage de cette représentation est que des blocs potentiellement très grands vont pouvoir être représentés en n’utilisant que deux nombres, d’où la compression.
La catastrophe du premier bit
Il est raisonnable de demander à un algorithme de compression d’être robuste et stable, i.e., de demander à ce que 2 fichiers très semblables soient compressés de manière plus ou moins similaire - au moins en taille mémoire. Pourtant, bien que LZ’78 soit très utilisé, sa robustesse était encore mal établie. La one-bit catastrophe question, introduite par Jack Lutz vers la fin des années ‘90, soulève le problème suivant : « est-il possible qu’un mot très compressible puisse devenir incompressible en ne changeant que sa première lettre ? » Le résultat principal de cet article est de montrer que c’est le cas. Il est possible de construire un mot très compressible mais que la perturbation – quand on change le premier bit – rend incompressible. La situation est en fait un peu plus critique puisqu’il existe une infinité de tels mots. Pour autant, doit-on arrêter l’utilisation de LZ’78 ? Absolument pas. Les algorithmes de Lempel-Ziv ont prouvé de bien des manières leur efficacité. De plus, la structure des mots « catastrophiques » est hautement spécifique et il est bien peu probable de les rencontrer en pratique. Évidemment, nous pouvons voir des variations dans les tailles de compressions de fichiers proches, mais ces comportements ne sont en aucun cas comparables à de vraies catastrophes.
Pour aller plus loin: