[News] Un seul bit vous manque, et ça ne compresse plus

Pour parler math...

Modérateur : Modérateurs

Adrien
Site Admin
Messages : 17178
Inscription : 02/06/2004 - 18:58:53
Activité : Ingénieur
Localisation : 78
Contact :

[News] Un seul bit vous manque, et ça ne compresse plus

Message par Adrien » 26/04/2019 - 8:00:13


Image
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 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.


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 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

Source: CNRS INS2I

Avatar de l’utilisateur
cisou9
Messages : 9879
Inscription : 12/03/2006 - 15:43:01
Activité : Retraité
Localisation : Pertuis en Lubéron
Contact :

Re: [News] Un seul bit vous manque, et ça ne compresse plus

Message par cisou9 » 26/04/2019 - 10:19:55

____________ :_salut:
La vidéo n'explique rien.
Un individu compétent (ou pas) rempli les cases d'un logiciel (formulaire) sans expliquer ce qu'il fait.
C'est nul. ___ :gueule: ____
Un homme est heureux tant qu'il décide de l'être et nul ne peux l'en empêcher.
Alexandre Soljenitsyne.

Répondre