Comment fonctionne la compression de données sans perte | Quanta Magazine

Avec plus de 9 milliards de gigaoctets d'informations circulant sur Internet chaque jour, les chercheurs sont constamment à la recherche de nouvelles façons de compresser les données en paquets plus petits. Les techniques de pointe se concentrent sur les approches avec perte, qui réalisent la compression en « perdant » intentionnellement des informations d'une transmission. Google, par exemple, a récemment dévoilé une stratégie avec perte dans laquelle l'ordinateur expéditeur supprime les détails d'une image et l'ordinateur récepteur utilise l'intelligence artificielle pour deviner les parties manquantes. Même Netflix utilise une approche avec perte, dégradant la qualité vidéo chaque fois que l'entreprise détecte qu'un utilisateur regarde sur un appareil à basse résolution.

En revanche, très peu de recherches sont actuellement menées sur les stratégies sans perte, où les transmissions sont réduites, mais aucune substance n'est sacrifiée. La raison? Les approches sans perte sont déjà remarquablement efficaces. Ils alimentent tout, de la norme d'image JPEG à l'utilitaire logiciel omniprésent PKZip. Et tout cela à cause d'un étudiant diplômé qui cherchait simplement un moyen de sortir d'un examen final difficile.

Il y a soixante-dix ans, un professeur du Massachusetts Institute of Technology nommé Robert Fano a proposé aux étudiants de son cours de théorie de l'information un choix : passer un examen final traditionnel ou améliorer un algorithme de pointe pour la compression de données. Fano a peut-être informé ses étudiants qu'il était l'auteur de cet algorithme existant ou qu'il recherchait une amélioration depuis des années. Ce que nous savons, c'est que Fano a proposé à ses élèves le défi suivant.

Considérez un message composé de lettres, de chiffres et de ponctuation. Un moyen simple d'encoder un tel message serait d'attribuer à chaque caractère un nombre binaire unique. Par exemple, un ordinateur peut représenter la lettre A par 01000001 et un point d'exclamation par 00100001. Il en résulte des codes faciles à analyser - tous les huit chiffres, ou bits, correspondent à un caractère unique - mais horriblement inefficaces, car le même nombre de chiffres binaires est utilisé pour les entrées courantes et inhabituelles. Une meilleure approche serait quelque chose comme le code Morse, où la lettre E fréquente est représentée par un seul point, alors que le Q moins courant nécessite le tiret-tiret-point-tiret plus long et plus laborieux.

Pourtant, le code Morse est également inefficace. Bien sûr, certains codes sont courts et d'autres sont longs. Mais comme les longueurs de code varient, les messages en code Morse ne peuvent être compris que s'ils incluent de brèves périodes de silence entre chaque transmission de caractères. En effet, sans ces pauses coûteuses, les destinataires n'auraient aucun moyen de distinguer le message Morse tiret point-tiret-point point-point tiret point (« banal ») du tiret point-tiret-point point-point-tiret point (« vrai »). ).

Fano avait résolu cette partie du problème. Il s'est rendu compte qu'il pouvait utiliser des codes de longueurs variables sans avoir besoin d'espaces coûteux, tant qu'il n'utilisait jamais le même modèle de chiffres à la fois comme code complet et comme début d'un autre code. Par exemple, si la lettre S était si courante dans un message particulier que Fano lui attribuait le code extrêmement court 01, aucune autre lettre de ce message ne serait encodée avec quoi que ce soit commençant par 01; des codes comme 010, 011 ou 0101 seraient tous interdits. De ce fait, le message codé pouvait être lu de gauche à droite, sans aucune ambiguïté. Par exemple, avec la lettre S attribuée à 01, la lettre A attribuée à 000, la lettre M attribuée à 001 et la lettre L attribuée à 1, du coup le message 0100100011 peut être immédiatement traduit par le mot « petit » même si L est représenté par un chiffre, S par deux chiffres, et les autres lettres par trois chacune.

Pour déterminer réellement les codes, Fano a construit des arbres binaires, plaçant chaque lettre nécessaire à la fin d'une branche visuelle. Le code de chaque lettre était alors défini par le chemin de haut en bas. Si le chemin bifurquait vers la gauche, Fano ajoutait un 0 ; les branches droites ont obtenu un 1. La structure arborescente a permis à Fano d'éviter facilement ces chevauchements indésirables : une fois que Fano a placé une lettre dans l'arbre, cette branche se termine, ce qui signifie qu'aucun code futur ne peut commencer de la même manière.

Pour décider quelles lettres iraient où, Fano aurait pu tester de manière exhaustive tous les modèles possibles pour une efficacité maximale, mais cela n'aurait pas été pratique. Ainsi, à la place, il a développé une approximation : pour chaque message, il organisait les lettres pertinentes par fréquence, puis attribuait des lettres aux branches de sorte que les lettres à gauche dans une paire de branches donnée soient utilisées dans le message à peu près le même nombre de fois que la lettres à droite. De cette façon, les caractères fréquemment utilisés se retrouveraient sur des branches plus courtes et moins denses. Un petit nombre de lettres à haute fréquence équilibrerait toujours un plus grand nombre de lettres à basse fréquence.

Le résultat a été une compression remarquablement efficace. Mais ce n'était qu'une approximation ; une meilleure stratégie de compression devait exister. Alors Fano a mis ses élèves au défi de le trouver.

Fano avait construit ses arbres de haut en bas, en maintenant autant de symétrie que possible entre les branches appariées. Son étudiant David Huffman a renversé le processus, construisant les mêmes types d'arbres mais de bas en haut. L'idée de Huffman était que, quoi qu'il arrive, dans un code efficace, les deux caractères les moins communs devraient avoir les deux codes les plus longs. Huffman a donc identifié les deux caractères les moins courants, les a regroupés en une paire de branchement, puis a répété le processus, cette fois en recherchant les deux entrées les moins courantes parmi les caractères restants et la paire qu'il venait de construire.

Considérez un message où l'approche de Fano vacille. Dans "salle de classe", O apparaît quatre fois et S/C/H/L/R/M apparaissent chacun une fois. L'approche d'équilibrage de Fano commence par attribuer le O et une autre lettre à la branche gauche, les cinq utilisations totales de ces lettres équilibrant les cinq apparitions des lettres restantes. Le message résultant nécessite 27 bits.

Huffman, en revanche, commence par deux des lettres rares - disons, R et M - et les regroupe, traitant la paire comme une seule lettre.

Son tableau de fréquences mis à jour lui propose alors quatre choix : le O qui apparaît quatre fois, le nouveau nœud RM combiné qui est fonctionnellement utilisé deux fois, et les lettres simples S, C, H et L. Huffman choisit à nouveau les deux options les moins courantes, correspondant (dire) H avec L.

Le graphique est à nouveau mis à jour : O a toujours un poids de 4, RM et HL ont maintenant chacun un poids de 2, et les lettres S et C sont indépendantes. Huffman continue à partir de là, regroupant à chaque étape les deux options les moins fréquentes, puis mettant à jour à la fois l'arbre et le tableau des fréquences.

En fin de compte, "salle de classe" devient 11101111110000110110000101, réduisant un peu l'approche descendante de Fano.

Un bit peut ne pas sembler beaucoup, mais même de petites économies augmentent énormément lorsqu'elles sont mises à l'échelle par des milliards de gigaoctets.

En effet, l'approche de Huffman s'est avérée si puissante qu'aujourd'hui, presque toutes les stratégies de compression sans perte utilisent la perspicacité de Huffman en tout ou en partie. Besoin de PKZip pour compresser un document Word ? La première étape implique encore une autre stratégie intelligente pour identifier la répétition et ainsi compresser la taille du message, mais la deuxième étape consiste à prendre le message compressé résultant et à le faire passer par le processus de Huffman. Stocker une image au format JPEG ? Votre ordinateur traduit d'abord l'image en une représentation textuelle, puis utilise à nouveau l'encodage Huffman pour compresser ce texte.

Pas mal pour un projet initialement motivé par le désir d'un étudiant diplômé de sauter un examen final.