Probleme – Aucun compresseur sans perte ne réduit tous les fichiers

1. L'argument de comptage. « Sans perte » signifie que la compression $C$ est injective : deux fichiers distincts ont des compressés distincts, faute de quoi le décompresseur ne saurait lequel rendre.

Supposons que $C$ raccourcisse strictement tout fichier de longueur $\le n$. Il y a $2^{n+1}-1$ tels fichiers (longueurs $0$ à $n$). Leurs images ont toutes une longueur $\le n-1$, or il n'existe que $2^n-1$ mots binaires de longueur $\le n-1$. Comme

$$2^{n+1}-1>2^n-1,$$

le principe des tiroirs donne deux fichiers de même image : $C$ n'est pas injective. Contradiction.

La conséquence est plus forte qu'il n'y paraît : tout compresseur qui raccourcit un fichier doit en allonger un autre. Il n'y a pas de compression universelle ; il n'y a que des compressions qui parient sur une classe d'entrées — les textes, les images, les journaux. Un compresseur est donc un modèle de ce qu'il compresse, et rien d'autre.

2. La proportion. Un fichier de $n$ bits raccourci d'au moins $k$ bits a une image de longueur $\le n-k$. Il y a $2^{n-k+1}-1$ mots binaires de cette longueur au plus. Par injectivité, au plus autant de fichiers de $n$ bits peuvent gagner $k$ bits, d'où la proportion

$$\frac{2^{n-k+1}-1}{2^n}<2^{1-k}.$$

Gagner ne serait-ce qu'un kilo-octet sur un fichier « quelconque » est un événement de probabilité $2^{-8191}$. Que les compresseurs réels y parviennent tous les jours dit seulement une chose : les fichiers réels ne sont pas quelconques.

3. La vérification sur lzw. On compresse des suites binaires tirées uniformément au hasard, et l'on compte les bits produits en supposant que chaque code s'écrit sur $\lceil {\log }_2(|D|+1)\rceil$ bits, où $|D|$ est la taille finale du dictionnaire :

longueur    source    codes emis   bits par code   total
   20        20 bits      11             4          44 bits
   50        50 bits      21             5         105 bits
  100       100 bits      34             6         204 bits
  400       400 bits      98             7         686 bits

lzw double la taille, régulièrement, sur des données incompressibles. Ce n'est pas un défaut de l'algorithme : c'est le théorème de la question 1, observé. lzw parie sur la répétition ; quand il n'y en a pas, le dictionnaire ne sert à rien et l'on paie ses numéros au prix fort.

Ce que font les formats réels, et c'est la seule réponse possible : ils détectent l'échec et le contournent. Un bloc deflate porte un en-tête à trois valeurs — non compressé, Huffman fixe, Huffman dynamique — et le compresseur choisit la moins mauvaise bloc par bloc. Le surcoût dans le pire cas tombe alors à quelques bits par bloc au lieu d'un facteur deux. Le théorème interdit de toujours gagner ; il n'interdit pas de ne presque jamais perdre.