Français

Compression des données

LycéeInformatiqueCodage par plages et codage de Huffman d’un court texte, comparés aux caractères sur 8 bits et à l’entropie de Shannon

Débloquez ce laboratoire avec un pass

Un pass donne accès à toutes les simulations du site, y compris au mode Présentation pour les cours. Les ressources pédagogiques ci-dessous restent gratuites pour tout le monde.

Voir les passJ’ai déjà un pass

Paiement unique, sans abonnement.

À propos de cette expérience

Chaque fichier ZIP, chaque image PNG et chaque piste MP3 est plus petite que les données brutes, car ces formats éliminent les répétitions. Essaie deux méthodes classiques sans perte sur ton propre message. Le codage par plages remplace une suite de symboles identiques par un nombre ; il est excellent pour les images simples et inutile pour le texte courant. Le codage de Huffman attribue des codes courts aux symboles fréquents et des codes longs aux symboles rares. Ces codes sont construits progressivement à partir d’un arbre, et le résultat se situe à moins d’un bit par symbole de la limite théorique découverte par Claude Shannon en 1948.

Objectifs pédagogiques

  • Explique la différence entre la compression sans perte et la compression avec perte
  • Encode et décode un message avec le codage par plages et explique dans quels cas il est utile
  • Construis un arbre de Huffman en réunissant à plusieurs reprises les deux symboles les moins fréquents
  • Lis les mots de code dans l’arbre et explique pourquoi aucun code ne commence par un autre
  • Compare les tailles compressées à la limite d’entropie et calcule un taux de compression

Comment l’utiliser

  1. 1Choisis la ligne Pixel et le codage par plages. De combien de bits la ligne a-t-elle besoin avant et après ? Pourquoi cela fonctionne-t-il si bien ?
  2. 2Passe à Hamlet avec le codage par plages. Pourquoi le message devient-il plus volumineux ?
  3. 3Choisis Mississippi et clique sur « Construire l’arbre ». Quels sont les deux arbres fusionnés à chaque étape, et pourquoi ?
  4. 4Une fois l’arbre terminé, trouve le mot de code de la lettre la plus fréquente et celui de la plus rare. Compte les bits.
  5. 5Décode à la main les premiers bits du message encodé en parcourant l’arbre depuis la racine.
  6. 6Saisis un message qui n’utilise qu’une seule lettre, puis un autre où toutes les lettres sont différentes. Dans les deux cas, compare le codage de Huffman à la limite d’entropie.

Le modèle

Combien de fois la taille des données a été réduite
Entropie de Shannon : le plus petit nombre moyen de bits par symbole qu’un code symbole par symbole peut atteindre
En moyenne, les codes de Huffman sont à moins d’un bit de l’entropie
Code le plus court où chaque symbole a la même longueur

Hypothèses

  • Le message d’origine utilise 8 bits par caractère, comme en ASCII.
  • Chaque paire longueur de séquence est stockée sous la forme d’un compteur de 8 bits et d’un caractère de 8 bits ; les séquences de plus de 255 caractères sont donc découpées.
  • La taille Huffman ne compte que le message encodé. Un fichier réel doit aussi stocker la table des codes ou les fréquences, ce qui compte pour les messages courts.
  • Lorsque deux arbres ont le même poids, celui qui a été créé en premier est choisi en premier, et l’arbre le plus léger devient la branche 0. D’autres règles de départage donnent des codes différents de même longueur totale.

À essayer en classe

  1. Q1Encodez BBBBBWWWBBBBBBBB avec un codage par longueur de séquence. De combien d’octets a-t-on besoin ?
  2. Q2Construisez l’arbre de Huffman pour les fréquences A 5, B 2, R 2, C 1, D 1 et trouvez le nombre total de bits pour ABRACADABRA.
  3. Q3Pourquoi un code de Huffman doit-il être un code préfixe ? Que se passerait-il si A était codé par 0 et B par 01 ?
  4. Q4Un texte utilise 8 lettres différentes, toutes aussi fréquentes. Quelle est son entropie, et Huffman peut-il le compresser ?
  5. Q5JPEG et MP3 compressent beaucoup plus que le codage de Huffman. À quoi renoncent-ils pour y parvenir ?

Foire aux questions

Où le codage de Huffman est-il utilisé aujourd’hui ?

Dans de nombreux formats courants : ZIP et gzip (la méthode DEFLATE), les images PNG, les images JPEG après l’étape avec perte et l’audio MP3. C’est généralement la dernière étape, après qu’une autre méthode a converti les répétitions en nombres.

Peut-on compresser n’importe quel fichier ?

Non. Une méthode sans perte qui réduirait la taille de chaque fichier permettrait de compresser le résultat encore et encore, ce qui est impossible puisqu’il existe moins de fichiers courts que de fichiers longs. Les données aléatoires et les fichiers déjà compressés ne deviennent généralement pas plus petits.

L’arbre de Huffman est-il unique ?

Pas toujours. En cas d’égalité des fréquences, des choix différents donnent des arbres et des mots de code différents, mais tous les arbres de Huffman correspondant aux mêmes fréquences donnent le même nombre total de bits.