Compression de l'information: plus que de rendre les fichiers plus petits

La compression de l'information, souvent appelée compression des données, est l'art et la science de réduire le nombre de bits nécessaires pour représenter les données. C'est une pierre angulaire de l'informatique moderne, permettant tout de la diffusion vidéo sur bande passante limitée au stockage de photographies haute résolution sur un smartphone. Bien que l'objectif pratique est de réduire la taille des fichiers, les fondements théoriques sont profondément enracinés dans les probabilités et les statistiques.

Si chaque caractère d'un message était également probable et indépendant de ses voisins, aucune compression significative ne serait possible. Mais les données naturelles – texte, images, audio, vidéo – sont pleines de motifs. La lettre «e» apparaît beaucoup plus souvent que «z» en anglais. Les pixels adjacents d'une image sont généralement similaires. Les images consécutives d'une vidéo changent rarement complètement.

Ces régularités sont ce que les codecs utilisent pour réduire les données, et la probabilité fournit le langage mathématique pour les décrire et les quantifier.

Probabilité : Le langage de la prévisibilité

Une distribution de probabilité simple pour le texte anglais pourrait attribuer une forte probabilité à «e» (environ 12,7%), une probabilité modérée à «t» (9,1%), et une très faible probabilité à «z» (0,074%). Un algorithme de compression peut utiliser cette connaissance pour attribuer des codes binaires courts à des symboles fréquents et des codes plus longs à des symboles rares, un principe connu sous le nom de codage à longueur variable. C'est la base intuitive pour de nombreux schémas de compression, mais la relation est beaucoup plus profonde.

Shannon , le théorème de codage de source: la limite fondamentale

Claude Shannon, le père de la théorie de l'information, a fourni le lien définitif entre la probabilité et la compression dans son article de 1948 Une théorie mathématique de la communication. Il a défini le entropie Pour une source qui émet des symboles avec probabilités p1, p2, ..., pn, l'entropie H est donnée par H = --- pi log2 pi. L'entropie mesure l'incertitude ou la surprise moyenne par symbole. Un lancer de pièce juste a entropie 1 bit; une pièce biaisée qui débarque toujours les têtes a entropie 0 bits.

Shannon , source codant théorème (le théorème sans bruit codant) déclare que tout schéma de compression sans perte ne peut pas comprimer les données à moins de bits que son entropie. En d'autres termes, l'entropie représente le nombre minimum absolu de bits nécessaires pour représenter chaque symbole. Inversement, pour toute source avec entropie H, il existe un schéma de codage qui peut le compresser arbitrairement à proximité des bits H par symbole. Ce théorème place une limite dure sur la compression sans perte – peu importe à quel point l'algorithme est intelligent, vous ne pouvez pas battre l'entropie de la source.

Ce résultat est profond : les distributions de probabilité déterminent directement le meilleur rapport de compression théorique. Les données avec une entropie élevée (par exemple, le bruit aléatoire) sont essentiellement incompressibles, tandis que les données avec une faible entropie (par exemple, une longue chaîne d'octets identiques) peuvent être compressées énormément.

Comment les algorithmes de compression utilisent la probabilité

Les algorithmes de compression pratiques implémentent les principes Shannon. L'approche la plus directe est de créer un codebook qui map les symboles à bit les séquences de longueurs variables, avec des codes plus courts assignés aux symboles plus probables. codage entropie- Oui.

Codage Huffman

Inventé par David A. Huffman en 1952, le codage Huffman construit un code optimal sans préfixe pour un ensemble donné de probabilités de symboles. Un code sans préfixe signifie qu'aucun mot de code n'est un préfixe d'un autre, de sorte que le bitstream encodé peut être décodé sans ambiguïté. L'algorithme construit un arbre binaire basé sur les probabilités : les symboles avec les probabilités les plus élevées finissent plus près de la racine, recevant les codes les plus courts. Le codage Huffman est largement utilisé dans les formats de fichiers JPEG, MPEG et ZIP. Il fonctionne bien lorsque les probabilités de symboles sont connues ou peuvent être estimées.

Codage arithmétique

Le codage arithmétique est une technique plus sophistiquée qui peut atteindre la compression arbitrairement près de la limite entropie, même pour les sources avec des probabilités de symboles non entiers. Au lieu d'attribuer un code fixe à chaque symbole, le codage arithmétique représente l'ensemble du message en tant que numéro de point flottant unique dans l'intervalle [0,1]. L'intervalle est subdivisé en fonction de la distribution de probabilité cumulative des symboles, et le nombre final encode uniquement la séquence.

Famille Lempel-Ziv (LZ)

Les algorithmes comme LZ77 et LZ78 (et leurs dérivés LZW, LZSS, Deflate) adoptent une approche différente : ils construisent un dictionnaire de séquences précédemment vues et remplacent les occurrences répétées par de courtes références. Bien qu'ils ne modélisent pas explicitement les probabilités, leur efficacité dépend de la probabilité de rencontrer des motifs répétés. Les algorithmes de style LZ sont particulièrement bons pour la manipulation des données où les motifs sont distribués contextuellement plutôt que sur la base de fréquences de symboles statiques. Ils forment la base de ZIP, PNG et GIF.

Modélisation du contexte et prévision

Les schémas modernes de compression vont plus loin en estimant les probabilités de symboles en fonction du contexte – les symboles précédents. Par exemple, dans la compression de texte, la probabilité de la lettre «u» est beaucoup plus élevée après un «q» qu'après un «z». prévision par correspondance partielle (PPM) et pondération des arbres contextuels (CTW). Les compresseurs de pointe comme le PAQ ou le ZPAQ utilisent des modèles de contexte sophistiqués et un codage arithmétique pour obtenir des rapports de compression records, mais à un coût de calcul élevé.

Compression de perte: Trading Probabilité pour la qualité perceptuelle

Bien que la compression sans perte préserve chaque bit de données originales, la compression sans perte permet de rejeter certaines informations en échange de taux de bit beaucoup plus faibles. La principale idée est que toutes les informations ne sont pas tout aussi importantes pour l'observateur humain – il est défini par une distribution de probabilité perceptuelle. Les codecs audio comme MP3 et AAC utilisent des modèles psychoacoustiques pour identifier les sons masqués par des sons plus forts et peuvent être rejetés.

En compression de perte, probabilité et statistiques sont utilisés pour concevoir distortion des taux optimisation : avec un budget cible de bits, l'algorithme décide quelles parties du signal pour préserver plus précisément et lesquelles pour approximation plus grossière. Les quantificateurs en JPEG (coefficients de transformation de cosine discret) ou en codecs basés sur l'apprentissage profond sont adaptés à la distribution statistique des données d'image. La connexion entre probabilité et compression va au-delà de l'entropie simple ; elle s'étend aux modèles perceptuels et à la théorie de décision.

Théorie des distorsions de taux

La théorie de la distorsion des taux, fondée également par Shannon, étend la source codant le théorème aux situations de perte. Elle définit le taux de bit minimum requis pour atteindre un niveau donné de distorsion (ou vice versa). L'échange est régi par l'information mutuelle entre la source et sa reconstruction, qui est une quantité probabiliste.

Applications réelles du monde de la compression probabiliste

Le mariage de la probabilité et de la compression touche tous les coins de la technologie.

  • Compresse d'image & #160;: JPEG utilise le codage Huffman après quantification des coefficients de fréquence. JPEG 2000 utilise le codage arithmétique avec une transformation de vaguelet. WebP et AVIF combinent des prédicteurs avancés avec le codage entropy.
  • Diffusion vidéo : Netflix et YouTube comptent sur des codecs comme H.264, H.265, et AV1, qui effectuent l'estimation du mouvement (prédicatif des cadres futurs des précédents) et compressent ensuite les résidus de prédiction en utilisant le codage arithmétique. L'estimation du mouvement lui-même est une recherche probabiliste: l'algorithme assigne une probabilité plus élevée à de petits mouvements locaux.
  • Compression audio : MP3 utilise le codage Huffman sur les données de domaine de fréquence après avoir appliqué un modèle psychoacoustique qui masque les composants inaudibles. Opus utilise un hybride de codecs SILK (discours) et CELT (musique), tous deux fortement motivés par les probabilités.
  • Stockage des données: Les systèmes de fichiers et les outils de sauvegarde utilisent des compresseurs LZ (comme zstd ou LZ4) pour échanger de l'espace contre du temps. Les bases de données utilisent la compression pour réduire les empreintes de stockage; les bases de données colonneuses encodent souvent des valeurs répétées consécutives – une forme simple de compression basée sur la probabilité.
  • L'apprentissage automatique: La compression de l'information est profondément liée à l'apprentissage. Le principe de la longueur minimale de la description (LDM) indique que le meilleur modèle pour un ensemble de données est celui qui minimise la longueur de la description combinée du modèle et des données données fournies par le modèle. Il s'agit d'une perspective probabiliste de compression sur la surcomposition et la généralisation.
  • Biologie et génomique : Les séquences d'ADN sont compressées à l'aide d'algorithmes spécialisés qui exploitent la forte probabilité de motifs répétés (p. ex., les îles CG) et de corrélations à longue distance.

Sujets avancés : Inférence bayésienne et compression universelle

Les structures de compression les plus sophistiquées traitent le codage comme un problème d'inférence bayésienne. Elles maintiennent une distribution de probabilité sur des séquences possibles conditionnées sur les données vues jusqu'à présent, et utilisent cette distribution pour conduire un codeur arithmétique. codage adaptatif ou universel – l'algorithme n'a pas besoin de connaître les statistiques sources à l'avance; il les apprend à la volée.

Par exemple, Transformation des terriers-roues (utilisé dans bzip2) réorganise les données d'entrée pour produire des exécutions de symboles identiques, rendant les données plus compressibles par un codeur entropie ultérieur. La transformation repose sur la propriété statistique qui partage souvent le contexte local. Transformations de la vague Gram-Schmidt les données de décorrelate de sorte que les coefficients résultants aient une entropie plus faible.

Une autre technique avancée est détection comprimée, qui exploite le fait que de nombreux signaux naturels sont clairsemés sur une certaine base (la plupart des coefficients proches de zéro, donc la probabilité élevée d'être négligeable). En utilisant des mesures linéaires randomisées, la détection comprimée peut récupérer le signal original à partir d'échantillons beaucoup moins nombreux que le taux de Nyquist suggère, effectuant efficacement la détection et la compression simultanées.

Défis et orientations futures

Bien que le lien entre probabilité et compression soit bien compris, de nombreux problèmes ouverts restent. Un défi est d'atteindre la compression universelle qui fonctionne bien sur tous les types de données sans réglage manuel. Un autre est la gestion de ensembles de données massives avec des exigences de faible latence; aujourd'hui, les compresseurs les plus rapides comme (a) (b) (b) (b) (b) (b)) (b) (b)) (b)) (b)) (b) (b)) (b)) (b)) (b)) (b)) (b)) (b)) (b)) (b)) (b))) (b)) (b))) (b))) (b))) (b))) (b)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) et LZ4 sacrifier un certain taux de compression pour la vitesse, mais les modèles probabilistes qu'ils utilisent sont relativement simples.

Les compresseurs neuraux en réseau sont un domaine de recherche actif. Les modèles d'apprentissage profond peuvent apprendre des distributions de probabilité très complexes sur des données à haute dimension (p. ex. images ou audio) et les utiliser pour atteindre des taux de compression à la fine pointe de la technologie. Codecs appris Souvent, les modèles hyperprécédents et les cartes d'importance sont utilisés pour attribuer des bits en fonction de l'incertitude locale (entropie) du signal. Ils représentent une fusion directe de l'apprentissage machine et de la théorie de l'information, où le modèle probabiliste n'est pas fabriqué à la main mais découvert à partir de données.

La théorie de l'information quantique promet également de nouvelles idées, bien que la compression quantique pratique soit loin de la réalité. Les concepts de von Neumann entropie et de codage de source quantique généralisent les idées Shannon aux états quantiques, laissant entendre que les liens entre probabilité, physique et compression sont encore plus profonds.

Conclusion : Pourquoi cette connexion est importante

La relation entre la probabilité et la compression de l'information n'est pas seulement une curiosité théorique; c'est le moteur derrière presque toutes les technologies numériques que nous utilisons quotidiennement. De la photo JPEG que vous avez vue pour la dernière fois à la chanson MP3 que vous avez diffusée, les modèles de probabilité ont déterminé l'efficacité de cette donnée stockée et transmise.

La probabilité fournit la matière première pour la compression – les attentes quant à ce que les symboles apparaîtront et à leur rapport les uns aux autres. La compression, à son tour, offre une mesure concrète et opérationnelle de l'aléa et de la structure des données. Ensemble, ils forment un cadre unifié pour penser à l'information, à la complexité et à l'efficacité.

Ressources extérieures :