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'77 et LZ'78 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.

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 racine(n * t * 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 * 8 * 2^30 bits) dont la compression aurait une taille de 10 Mo (t = 10 * 8 * 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