Compression de données universelle

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

Expérimentation

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

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

C(u) = C(v) implique u = v.

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

1. la suite (Cⁿ(u))_n est périodique,
2. la suite (Cⁿ(u))_n ne contient jamais deux fois le même mot et donc pour tout entier il existe un entier k tel que le mot C^k(u) est de taille supérieure à N.

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 u plus grand que sa version compressée C(u), alors :

• soit u est dans un cycle de longueur k et il existe tel que le mot Cⁱ(u) est strictement plus petit que sa version compressée C^{i + 1}(u),
• soit la suite (Cⁿ(u))_n 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 N donnée : en effet il y a a^N mots de taille N pour un alphabet à a lettres et seulement mots avec strictement moins de N lettres.

Voir aussi

Articles connexes

• Compression de données
• NABOB
• BARF (compresseur)

Liens externes

• (en) « Introduction to Data Compression » par Guy E. Blelloch
• (en) « No magic » par Charles Bloom
• (en) « What is Magic Function Theory » par Mark Nelson
• (en) « Compression of random data », Compression FAQ

• Portail de l’informatique