Un seul bit vous manque, et ça ne compresse plus
Publié par Adrien le 26/04/2019 à 08:00
Source: CNRS INS2I

Photo Pixabay
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 ( Un fichier est un endroit où sont rangées des fiches. Cela peut-être un meuble, une pièce, un bâtiment, une base de données informatique. Par exemple : fichier des patients d'un médecin, fichier des...) détériorerait drastiquement le taux de compression (Le taux de compression est une mesure de la performance d'un algorithme de compression de données informatiques. Il est généralement exprimé en pourcentage, et noté τ. Deux...) ? C'est pourtant ce qu'ont pu prouver des chercheurs de l'Institut (Un institut est une organisation permanente créée dans un certain but. C'est habituellement une institution de recherche. Par exemple, le Perimeter Institute for Theoretical Physics est un tel...) de Recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche scientifique désigne également le cadre...) en Informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le...) Fondamentale (En musique, le mot fondamentale peut renvoyer à plusieurs sens.) (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 (La bande passante (angl. bandwidth) est un intervalle de fréquences pour lesquelles la réponse d'un appareil est supérieure à un minimum. Elle est généralement confondue avec la largeur de 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 (La vidéo regroupe l'ensemble des techniques, technologie, permettant l'enregistrement ainsi que la restitution d'images animées, accompagnées ou non de son, sur un support adapté à l'électronique et non...) (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 (Guillaume est un prénom masculin d'origine germanique. Le nom vient de Wille, volonté et Helm, heaume, casque, protection.) 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 (Graphie) de vue (La vue est le sens qui permet d'observer et d'analyser l'environnement par la réception et l'interprétation des rayonnements lumineux.) théorique pour leurs bonnes propriétés (compression optimale de suites provenant d'une source aléatoire, liens avec la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée...) des automates finis et la dimension (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur, ou bien son diamètre si c'est une...) de classes complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en...), 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.

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 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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) 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
Page générée en 0.211 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique