Ouvrir le menu principal

Compression de données universelle

(Redirigé depuis Paradoxe du compresseur)

Un compresseur sans perte universel ne peut pas exister. Plus précisément, pour tout compresseur sans perte, on est certain que :

  1. il est impossible de compresser strictement tous les mots ;
  2. s'il existe un mot qui est strictement compressé alors il existe un autre mot dont la version compressée est strictement plus grande que le mot lui-même ;
  3. pour n'importe quel mot de départ auquel on applique de manière répétée le compresseur, on est nécessairement dans l'un des cas de figure suivants :
    • soit une suite de mots se répète infiniment,
    • soit les mots successifs obtenus atteignent des tailles arbitrairement grandes.

Ces propriétés sont démontrées ci-après. Cependant, elles n'enlèvent rien à l'intérêt des compresseurs sans perte. En effet, dans la pratique, les mots, messages ou fichiers que l'on souhaite compresser ne sont pas quelconques et choisis aléatoirement parmi tous les mots, messages ou fichiers possibles. Les compresseurs se servent de leurs particularités. Des compresseurs seront alors très bons avec certains types de données, et très mauvais avec d'autres.

Ainsi pour ces types de compresseurs spécialisés, l'information fournie par le contexte est utilisée pour la compression (voir théorie de l'information).

Sommaire

ExpérimentationModifier

On peut aisément vérifier expérimentalement cette impossibilité. Voici un script shell qui crée un fichier comportant 100 fois la ligne "blabla" puis qui effectue 100 compressions successives de ce fichier à l'aide du compresseur gzip et enfin affiche les tailles successives obtenues :

for i in `seq 1 100`; do echo "blabla" >> toto001; done
for i in `seq 1 100`; do gzip -c "toto`printf "%03d" $i`" > "toto`printf "%03d" $((i+1))`"; done
wc -c toto*

On vérifie souvent en pratique qu'un fichier qui est déjà le résultat d'une compression se compresse mal, voire grossit par application du compresseur. D'ailleurs, gzip refuse par défaut de compresser les fichiers comportant l'extension ".gz" qui est le signe d'une précédente application de ce compresseur.

Preuve mathématiqueModifier

Un compresseur sans perte peut être vu comme une injection des mots dans les mots, c'est-à-dire une fonction   telle que

  implique  .

On vérifie alors aisément que, pour tout mot  , l'un des deux cas suivants est vérifié :

  1. la suite   est périodique,
  2. la suite   ne contient jamais deux fois le même mot et donc pour tout entier   il existe un entier   tel que le mot   est de taille supérieure à  .

Ceci montre la troisième propriété de l'impossibilité énoncée ci-dessus. Les deux premières en découlent car, s'il y a compression stricte, c'est-à-dire s'il existe un mot   plus grand que sa version compressée  , alors :

  • soit   est dans un cycle de longueur   et il existe   tel que le mot   est strictement plus petit que sa version compressée  ,
  • soit la suite   ne contient jamais deux fois le même mot donc elle contient un mot strictement plus petit que sa version compressée (car on ne peut pas avoir une suite infinie décroissante, au sens large, de mots tous distincts).

On peut remarquer par ailleurs qu'il est impossible de compresser strictement tous les mots d'une taille   donnée : en effet il y a   mots de taille   pour un alphabet à   lettres et seulement   mots avec strictement moins de   lettres.

Voir aussiModifier