Compression de données universelle

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.

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

${\displaystyle C(u)=C(v)}$ implique ${\displaystyle u=v}$.

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

1. la suite ${\displaystyle (C^{n}(u))_{n}}$ est périodique,
2. la suite ${\displaystyle (C^{n}(u))_{n}}$ ne contient jamais deux fois le même mot et donc pour tout entier ${\displaystyle N\in \mathbb {N} }$ il existe un entier ${\displaystyle k}$ tel que le mot ${\displaystyle C^{k}(u)}$ est de taille supérieure à ${\displaystyle 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 ${\displaystyle u}$ plus grand que sa version compressée ${\displaystyle C(u)}$, alors :

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