Comment fonctionne la compression de fichiers
Un zip est plus petit que ce qui y est entré, et rien n'a été jeté. L'astuce est que les données ordinaires sont bien plus prévisibles que la façon dont nous les écrivons d'habitude.
Pourquoi des codes courts pour les lettres fréquentes gagnent
Niveau Débutant — langage simple, sans maths
Normalement chaque lettre que vous stockez occupe la même place : huit bits chacune, que ce soit un e ou un q. C'est pratique et c'est aussi du gaspillage, parce que ces deux lettres ne sont pas aussi fréquentes l'une que l'autre. En français, le e apparaît environ cent fois plus souvent que le q. Leur donner la même place, c'est utiliser le même carton pour poster un canapé et une carte postale.
Faites donc la chose évidente : donnez des codes courts aux lettres fréquentes et des codes longs aux rares. Donnez trois bits au e et laissez onze bits au q. Vous perdez un peu sur chaque q et gagnez un peu sur chaque e, et comme il y a infiniment plus de e, le total sort plus petit. Rien n'a été jeté : chaque lettre est toujours là, exactement telle qu'elle était.
Il reste un problème à régler. Si les codes ont des longueurs différentes, comment savoir où l'un s'arrête et où le suivant commence ? La réponse est de s'assurer qu'aucun code n'est le début d'un autre code. Si 10 est une lettre entière, alors aucun autre code ne peut commencer par 10. Une méthode appelée codage de Huffman construit exactement cela, en collant à répétition les deux lettres les plus rares et en remontant, ce qui met automatiquement les rares au fond d'un arbre et les fréquentes près du sommet.
Jouez avec le curseur de répétition et regardez les barres. Plus votre message est prévisible, plus il y a à gagner. Une page de la même lettre se comprime presque à rien. Une page de pur hasard ne se comprime pas du tout, et cela se révèle être un fait profond plutôt qu'un désagrément.
Bon à savoir
- Dans un texte français, les six lettres les plus fréquentes - e a s i n t - font environ 45 % de tout l'écrit. Ce déséquilibre est toute la source du gain.
- Le code Morse est une version artisanale de la même idée : le E est un seul point, le Q est trait-trait-point-trait. Samuel Morse a compté les lettres dans la casse d'un imprimeur pour décider lesquelles devaient être courtes.
- Un fichier de nombres vraiment aléatoires ne se comprime pas du tout. Si un programme prétend réduire n'importe quel fichier, il se trompe : il n'y a pas assez de fichiers courts pour contenir tous les longs.
Entropie, codes préfixes et la frontière entre avec et sans perte
Niveau Élève — les équations essentielles
La quantité exploitée a un nom et un nombre. L'entropie de Shannon mesure l'information moyenne par symbole : \(H = -\sum p_i \log_2 p_i\) bits. Pour les lettres d'un texte avec leurs fréquences réelles, elle vaut environ 4,1 bits par caractère au lieu des 8 que vous dépensez en les stockant naïvement, et si l'on tient compte du fait qu'un q est presque toujours suivi d'un u, elle tombe à environ 1,5 bit par caractère. L'entropie est le plancher : aucune méthode sans perte ne peut utiliser en moyenne moins de bits par symbole que l'entropie de la source, et le codage de Huffman arrive à moins d'un bit de là.
L'algorithme de Huffman est une construction gloutonne à partir des feuilles. Prenez les deux symboles les moins fréquents, fusionnez-les en un nœud dont le poids est leur somme, remettez-le dans le tas, répétez jusqu'à ce qu'il ne reste qu'un nœud. En lisant l'arbre depuis la racine, une branche gauche est un 0 et une branche droite un 1, et comme chaque symbole est une feuille, aucun code n'est le préfixe d'un autre : le décodeur peut descendre l'arbre bit par bit et sait toujours quand il est arrivé.
Les vrais formats superposent d'autres astuces. Le codage par plages remplace les répétitions par un compteur. LZ77, le cœur de ZIP, PNG et gzip, remplace un morceau répété par une référence en arrière - recule de 214 octets et copies-en 9 - ce qui explique pourquoi le texte et le code se compriment si bien, et pourquoi un fichier compressé deux fois ne rétrécit presque plus la seconde. DEFLATE, c'est simplement LZ77 suivi de Huffman.
Tout cela est sans perte : l'original revient bit pour bit. Les photographies et la musique utilisent plutôt des méthodes avec perte, qui jettent l'information que l'œil ou l'oreille ne remarquent pas : JPEG transforme chaque bloc de 8×8 pixels en fréquences et rend grossières les hautes, MP3 jette les sons masqués par des voisins plus forts. C'est pourquoi un JPEG enregistré à répétition se dégrade et un ZIP jamais.
Formules clés
| Entropie | \(H = -\sum_i p_i \log_2 p_i\) | bits par symbole, le plancher dur |
|---|---|---|
| Longueur idéale | \(\ell_i = -\log_2 p_i\) | symbole plus rare, code plus long |
| Borne de Huffman | \(H \le \bar{\ell} < H + 1\) | |
| Taux de compression | \(R = \dfrac{\text{bits originaux}}{\text{bits codés}}\) | |
Bon à savoir
- Le codage de Huffman est démontrablement optimal parmi les méthodes qui attribuent à chaque symbole un nombre entier de bits. Le codage arithmétique le bat précisément en échappant à cette contrainte et en codant le message entier comme un seul nombre fractionnaire.
- Compresser un fichier déjà compressé le rend généralement un peu plus gros, parce que le conteneur ajoute des en-têtes à des données qui n'ont plus de redondance à retirer.
- PNG est sans perte et JPEG avec perte, et c'est pourquoi les captures d'écran vont en PNG et les photographies en JPEG. Enregistrer une capture en JPEG produit des franges visibles autour du texte pour un gain qui ne vaut rien.
Complexité de Kolmogorov, l'argument de comptage et les compresseurs modernes
Niveau Expert — profondeur mathématique complète
01Pourquoi aucun compresseur ne peut tout réduire
La démonstration est un argument de comptage et tient en une ligne. Il y a \(2^n\) chaînes de longueur \(n\) mais seulement \(2^n - 1\) chaînes plus courtes que \(n\). Tout compresseur sans perte est une injection, il ne peut donc pas envoyer chaque chaîne de longueur \(n\) sur une plus courte : certaines entrées doivent grandir. La compression n'est donc jamais une propriété du seul algorithme ; c'est un pari sur la distribution des entrées. Un bon compresseur est celui dont le modèle implicite correspond aux données qu'on lui donne effectivement.
02Comprimer, c'est prédire
Les codeurs arithmétiques et par intervalles coupent le lien entre symbole et bits entiers, codant un message comme un seul nombre dans \([0,1)\) dont l'intervalle est rétréci par chaque symbole proportionnellement à sa probabilité. La conséquence est que la modélisation et le codage deviennent des problèmes séparés, et tout le gain restant est dans le modèle. Les compresseurs à mélange de contextes comme PAQ font tourner des centaines de modèles prédictifs en parallèle et les fondent avec un réseau de neurones ; les meilleurs compresseurs de texte d'aujourd'hui sont, fonctionnellement, des modèles de langue. L'équivalence vaut dans les deux sens : un modèle qui prédit bien le jeton suivant est un compresseur, et le taux de compression est une mesure légitime de ce qu'un modèle comprend de ses données.
03La complexité de Kolmogorov
La limite théorique pour une chaîne particulière est la longueur du plus court programme qui la produit, \(K(x)\). Une chaîne structurée - un milliard de décimales de π - a une complexité de Kolmogorov minuscule malgré une entropie énorme sous n'importe quel modèle de symboles, parce qu'un court programme l'engendre. L'ennui est que \(K\) n'est pas calculable : aucun algorithme ne peut trouver en général le plus court programme, résultat qui découle du problème de l'arrêt. La compression pratique est la recherche d'approximations calculables d'un idéal non calculable.
04Ce que font vraiment les formats modernes
Zstandard associe un chercheur de correspondances de style LZ77 à la finite state entropy, une implémentation des systèmes numériques asymétriques qui atteint l'efficacité du codage arithmétique à la vitesse d'une lecture de table - un progrès véritable, puisque pendant trente ans le choix a été entre rapide et petit. Brotli embarque un dictionnaire de 120 ko de chaînes web courantes, si bien que de courtes réponses HTTP se compriment contre du texte qu'elles n'ont jamais contenu. Pour les images, le codage intra-image d'AV1 sous-tend AVIF et bat JPEG d'environ la moitié à qualité perçue égale, en utilisant une prédiction intra directionnelle plutôt qu'en s'appuyant sur la seule transformée.
05Le codage avec perte comme problème débit-distorsion
Formellement, la compression avec perte est le problème débit-distorsion : minimiser le débit binaire sous une contrainte de distorsion, où la distorsion est définie par un modèle perceptuel plutôt que par l'erreur quadratique. La matrice de quantification de JPEG est un modèle fait main de la sensibilité au contraste - la réponse déclinante de l'œil aux hautes fréquences spatiales - et les successeurs modernes remplacent le réglage manuel par des métriques perceptuelles apprises. Le point conceptuel important est que l'information jetée est choisie par un modèle de l'observateur, ce qui explique pourquoi un codec réglé pour l'œil humain abîme une image médicale d'une façon qu'un radiologue remarquera.
Formules clés
| Borne de comptage | \(|\{x : |x| = n\}| = 2^n > 2^n - 1 = |\{y : |y| < n\}|\) | |
|---|---|---|
| Complexité de Kolmogorov | \(K(x) = \min\{|p| : U(p) = x\}\) | non calculable |
| Codage arithmétique | \(\text{longueur} \approx \left\lceil -\log_2 \prod_i p(x_i) \right\rceil + 2\) | |
| Débit-distorsion | \(R(D) = \min_{p(\hat{x}|x):\,\mathbb{E}[d] \le D} I(X;\hat{X})\) | |
Bon à savoir
- La complexité de Kolmogorov n'est pas calculable, et la démonstration se ramène au problème de l'arrêt. Le paradoxe de Berry - "le plus petit nombre non descriptible en moins de douze mots" - est la même idée en français.
- Le prix Hutter paie pour compresser un extrait fixe d'un gigaoctet de Wikipédia, sur la thèse explicite que mieux compresser un texte équivaut à mieux le comprendre.
- Les systèmes numériques asymétriques, publiés en 2009, ont donné la compression du codage arithmétique à une vitesse proche de Huffman et sont aujourd'hui dans Zstandard, LZFSE et AV1. C'est l'une des rares idées vraiment neuves dans un domaine mûr.