1. Le principe des tiroirs : pourquoi aucun algorithme ne peut compresser tous les fichiers

Lorsque nous utilisons quotidiennement zip, gzip, zstd, 7z ou PNG pour réduire la taille de nos documents, codes sources ou images sans perdre un seul bit à la décompression (compression sans perte / réversible), une question naturelle surgit : si un compresseur réduit la taille d’un fichier, pourquoi ne pas re-compresser le fichier .zip obtenu dix fois de suite jusqu’à réduire n’importe quel film ou base de données à un seul octet ?

La réponse est formelle : c’est mathématiquement impossible. La démonstration repose directement sur le principe des tiroirs de Dirichlet (Pigeonhole Principle) en combinatoire élémentaire.

Soit $E: \{0,1\}^* \to \{0,1\}^*$ une fonction d’encodage sans perte et $D: \{0,1\}^* \to \{0,1\}^*$ sa fonction de décodage. Pour garantir une réversibilité parfaite $D(E(x)) = x$ pour tout fichier binaire $x$, l’application $E$ doit impérativement être injective (biunivoque) : si deux fichiers distincts $x_1 \ne x_2$ produisaient la même séquence compressée $y = E(x_1) = E(x_2)$, le décodeur recevant $y$ ne pourrait jamais savoir s’il doit restituer $x_1$ ou $x_2$ !

Or, il existe exactement $2^N$ fichiers binaires de longueur $N$ bits, tandis que le nombre total de chaînes binaires strictement plus courtes que $N$ (de longueur $0$ à $N-1$) vaut :

Puisqu’il y a $2^N$ fichiers d’entrée (« pigeons ») pour seulement $2^N - 1$ chaînes plus courtes (« tiroirs »), tout algorithme de compression sans perte qui raccourcit au moins un fichier DOIT nécessairement en allonger d’autres ! Plus encore, la proportion de fichiers de $N$ bits pouvant être réduits d’au moins $c$ bits est strictement bornée par :

La quasi-totalité des suites binaires aléatoires (au sens de la complexité de Kolmogorov) est donc totalement incompressible. Si nos compresseurs fonctionnent si bien au quotidien, c’est parce que les textes humains, les programmes informatiques et les images naturelles occupent un sous-ensemble infinitésimal, hautement structuré et à faible entropie au sein de $\{0,1\}^N$.

2. Le théorème du codage de source de Shannon et l’entropie : la limite absolue

En 1948, dans « A Mathematical Theory of Communication », Claude E. Shannon a établi la limite fondamentale de la compression de données. Pour une source discrète sans mémoire émettant des symboles d’un alphabet $\mathcal{A} = \{s_1, \dots, s_m\}$ selon la loi de probabilité $P = (p_1, \dots, p_m)$, la quantité d’information propre (Surprisal) d’un symbole $s_i$ et son espérance mathématique, l’entropie de Shannon $H(X)$, sont définies par :

Tout code préfixe (instantané) attribuant à chaque symbole $s_i$ un mot de code binaire de longueur $\ell_i$ doit satisfaire l’inégalité de Kraft-McMillan :

En utilisant la non-négativité de la divergence de Kullback-Leibler $D_{\text{KL}}(P \,\|\, Q) \ge 0$ avec $q_i = 2^{-\ell_i}/Z$ ($Z = \sum 2^{-\ell_i} \le 1$), on démontre le théorème du codage de source de Shannon pour la longueur moyenne $L = \sum_{i=1}^m p_i \ell_i$ :

L’entropie $H(X)$ constitue ainsi la borne inférieure infranchissable de tout codage sans perte.

  flowchart TD
    A["Flux de données brut (Texte / Image / Exécutable)"] --> B["Étape 1 : Transformation & Modélisation par dictionnaire (BWT / LZ77)"]
    B --> C["Distribution de probabilité P(s) des symboles et pointeurs (distance, longueur)"]
    C --> D["Étape 2 : Codage entropique statistique (Huffman / Arithmétique / ANS)"]
    D --> E["Flux binaire compact proche de la limite de Shannon N·H(X)"]

3. Trois générations de codage entropique : Huffman, Codage Arithmétique et ANS

3.1 Le codage de Huffman (1952) : arbres préfixes optimaux à longueurs entières

L’algorithme glouton de David A. Huffman construit en temps $O(m \log m)$ l’arbre binaire préfixe optimal en fusionnant itérativement les deux symboles les moins probables. Sa limite fondamentale réside toutefois dans la contrainte que chaque mot de code doit avoir un nombre entier de bits ($\ell_i \ge 1$) : un symbole de probabilité $p_1 = 0,99$ ne porte que $-\log_2(0,99) \approx 0,0145\,\text{bit}$ d’information, mais coûte au minimum $1\,\text{bit}$ entier.

3.2 Le codage arithmétique (Arithmetic Coding) : l’ère des bits fractionnaires

Le codage arithmétique (Rissanen, Pasco, Witten et al.) contourne la barrière entière en projetant la séquence entière du message $x_1 x_2 \dots x_N$ sur un unique sous-intervalle $[L_{\text{low}}, H_{\text{high}}) \subset [0, 1)$ dont la largeur finale $\Delta = \prod_{t=1}^N P(x_t)$ ne requiert que $\lceil -\log_2 \Delta \rceil + 1 \approx N \cdot H(X)$ bits, au prix de multiplications séquentielles coûteuses en temps CPU.

3.3 Les systèmes numériques asymétriques (ANS, Jarek Duda 2009–2014)

Inventés par le physicien et informaticien polonais Jarek Duda, les Asymmetric Numeral Systems (tANS et rANS) réconcilient enfin le taux de compression optimal du codage arithmétique avec la vitesse d’exécution par table de correspondance du codage de Huffman. Lorsqu’un symbole $s$ de probabilité $p_s$ est encodé dans l’état entier $x \in \mathbb{N}$, l’état évolue selon :

Cette avancée propulse aujourd’hui Zstandard (zstd) de Meta, LZFSE d’Apple et JPEG XL de Google.

4. Compression par dictionnaire et transformations : LZ77, DEFLATE, BWT et « Compresser c’est prédire »

Pour exploiter les répétitions de sous-chaînes et les corrélations contextuelles, les compresseurs modernes combinent modélisation séquentielle et codage entropique :

• LZ77 (Lempel & Ziv, 1977) : remplace toute sous-chaîne déjà apparue dans une fenêtre glissante par un pointeur arrière (distance, length). Associé à Huffman, il forme DEFLATE (gzip, zip, PNG) ; associé à ANS, il donne Zstandard (zstd).
• Transformée de Burrows-Wheeler (BWT, 1994, bzip2) : trie lexicographiquement toutes les rotations cycliques d’un bloc et extrait la dernière colonne $L$, regroupant les caractères partageant le même contexte suivant sans augmenter la taille du bloc.

  flowchart TD
    A["Flux d'octets en entrée"] --> B["Recherche de la plus longue correspondance dans la fenêtre glissante (LZ77)"]
    B --> C{"Longueur de correspondance >= 3 ?"}
    C -- "Oui" --> D["Émission d'un pointeur arrière (distance, length)"]
    C -- "Non" --> E["Émission de l'octet littéral (Literal)"]
    D --> F["Codage entropique via Huffman (DEFLATE) ou ANS (Zstandard)"]
    E --> F

En dernière analyse, compresser équivaut exactement à prédire : tout modèle probabiliste (tel qu’un grand modèle de langage Transformer) qui minimise son entropie croisée $-\sum \log_2 P_\theta(x_t \mid x_{