Un seul bit vous manque, et ça ne compresse plus…
Pour décrire cette suite à un ami : 11111111111111111111111111111111, probablement lui diriez-vous qu’elle contient uniquement 32 fois le bit 1. Vous venez alors de faire une compression en décrivant cette suite plus succinctement que l’énumération de tous ses bits un à un. Mais que penseriez-vous d’un algorithme de compression qui soit si peu robuste que le changement d’un seul bit à un fichier détériorerait drastiquement le taux de compression ? C’est pourtant ce qu’ont pu prouver des chercheurs de l’Institut de Recherche en Informatique Fondamentale (IRIF - CNRS/Université Paris-Diderot).
Un algorithme de compression est une méthode générale qui essaie de décrire de manière concise le fichier qu’elle reçoit en entrée, afin de réduire l’espace de stockage ou l’utilisation de la bande passante dans les réseaux, entre autres.
On n’en a pas toujours conscience, mais ces méthodes sont omniprésentes, sous la forme de compresseurs génériques (Huffman et Lempel-Ziv par exemple, avec des formats comme zip, bz2…) ou spécifiques à certains types de fichiers comme la musique (mp3…), la vidéo (mp4…), les images (jpg, png, gif…), etc. Tous ne sont pas équivalents, certains sont sans perte d’information (lossless), pour le texte notamment, d’autres réduisent légèrement la qualité (sonore, visuelle) au profit d’un meilleur taux de compression.
Mais que penseriez-vous d’un algorithme de compression qui soit si peu robuste que le changement d’un seul bit à un fichier détériorerait drastiquement le taux de compression ? Cela ne semble pas raisonnable. Heureusement, il est facile de voir que ce phénomène, appelé « one-bit catastrophe », ne survient pas pour la plupart des algorithmes classiques ; cependant, dans le cas particulier d’un algorithme très utilisé appelé « LZ’78 », cette question posée par Jack Lutz (Iowa State University) à la fin des années 1990 n’avait toujours pas trouvé de réponse. Guillaume Lagarde et Sylvain Perifel de l’IRIF ont montré dans ce cadre qu’une telle catastrophe est possible : la modification d’un bit peut rendre incompressible un fichier qui était compressible initialement (!).
Lempel-Ziv
Les algorithmes de Lempel et Ziv font référence à une famille de méthodes de compression sans perte pouvant travailler sur n’importe quel format de fichiers. Ils occupent une place importante en informatique, non seulement pour leur côté pratique (on les retrouve dans le format d’image GIF, dans l’archiveur zip, etc.), mais ils sont également très étudiés d’un point de vue théorique pour leurs bonnes propriétés (compression optimale de suites provenant d’une source aléatoire, liens avec la théorie des automates finis et la dimension de classes complexité, factorisation de mots, entre autres). Les deux algorithmes originaux datent de 1977 et 1978 (LZ’771 et LZ’782 respectivement) mais de nombreuses variantes existent. L’encadré ci-dessous décrit le fonctionnement de l’algorithme LZ’78 dont le principe fondamental est de tirer parti de répétitions dans le fichier. Cela explique en partie pourquoi les textes (français, anglais…), comportant naturellement des motifs répétitifs, se compressent bien par cette méthode.
- 1Jacob Ziv et Abraham Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3):337–343, Septembre 1977
- 2Jacob Ziv et Abraham Lempel. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24(5):530–536, Septembre 1978
Algorithme LZ’78
Afin de compresser une suite w de 0 et de 1, w est lu de gauche à droite et découpé en blocs de la manière suivante : chaque bloc est le plus petit qui n’a pas été vu précédemment.
Exemple : w=0011010111111111 est découpé en 0.01.1.010.11.111.1111.
Ainsi, chaque bloc de taille au moins 2 est l’extension par un bit sur la droite d’un bloc précédent appelé antécédent. On numérote les blocs de la gauche vers la droite. Pour « compresser », il suffit maintenant de décrire chaque bloc par le numéro de son antécédent et le bit qui le complète.
Exemple : la compression de w est 0.(1,1).1.(2,0).(3,1).(5,1).(6,1).
Remarque : un argument simple montre que, pour certaines suites, leur taille n’est pas réduite ainsi. Ceci est en fait valable pour n’importe quelle méthode de compression sans perte.
Audiodescription
Catastrophe
Les résultats des chercheurs caractérisent la variation possible de la taille de la compression par LZ’78 avant et après modification d’un bit du fichier initial. Plus précisément, si une suite de n bits a une compression de taille t, alors la suite modifiée aura une compression d’une taille au plus $\sqrt{n \cdot t \cdot \log n}$ (à une constante près). Par ailleurs, les chercheurs montrent que dans certains cas, cette borne est atteinte. Par exemple, un fichier de 10 Go ($n = 10 \times 8 \times 2^{30}$ bits) dont la compression aurait une taille de 10 Mo ($t = 10 \times 8 \times 2^{20}$ bits), peut potentiellement, après modification d’un bit, ne plus se compresser qu’en 1,9 Go environ ! Cela répond affirmativement à la question de la one-bit catastrophe de Jack Lutz.
Néanmoins, les fichiers amenant à des catastrophes de ce genre ont des structures tellement particulières qu’il est relativement peu probable de s’y confronter en pratique. Pourtant, conscients de ce problème, les programmeurs de ces outils de compression utilisent tout de même certaines techniques permettant de réduire le risque d’obtenir une telle catastrophe, en testant par exemple différents « points de départ » pour la compression et en sélectionnant le meilleur.
Publication
Guillaume Lagarde et Sylvain Perifel. Lempel-Ziv: a "one-bit catastrophe" but not a tragedy. SODA 2018, pp. 1478–1495. https://arxiv.org/abs/1707.04312