LYCÉE
Données structurées Sciences
Numériques
COLBERT
LORIENT Algorithme de Huffman et Technologie
© Ch. Lauverjat 2020
Compression des données
1 - Introduction
Le volume de données informatiques échangées croit exponentiellement d’année en année, de
même que le besoin de stockage de ces données.
La compression des données est au cœur de nombreux formats de fichiers ZIP, RAR, MP3, MP4, JPG,
PNG…
2 - Ressource
Vous allez tout d’abord regarder la vidéo intitulée « Les marmottes au sommeil léger » disponible en
suivant le lien : https://youtu.be/oqMx1cuw6mo
Le titre et le début de la vidéo peuvent vous intriguer, mais rassurez-vous, au final on parle bien
d’informatique et d’algorithme de compression (à partir de 11’20). Mais regardez-bien le début qui
vous explique de manière ludique la problématique et le principe de traitement de l’information.
3 - Travail demandé
Vous allez appliquer l’algorithme vu dans la vidéo au texte du premier paragraphe page 70 de votre
manuel (texte recopié ci-dessous). Afin de limiter le nombre de caractères à traiter, on ne fera pas la
distinction entre les majuscules et les minuscules, et on enlèvera les accents.
3.1 - Texte à traiter :
AVEC LE DEVELOPPEMENT INDUSTRIEL ET TECHNOLOGIQUE DE NOS SOCIETES, LE
NOMBRE GRANDISSANT D'INFORMATIONS A COLLECTER ET A TRAITER A ENTRAINE LA
CREATION DE MACHINES PLUS RAPIDES, PLUS PRECISES POUR LEUR RECUPERATION ET
LEUR STOCKAGE.
Ce texte comprend 232 caractères. Si chacun de ces caractères était codé sur 8 bits (table ASCII vue
en début d’année), il occuperait donc un espace mémoire de 232 x 8 = 1856 bits.
3.2 - Fréquence d’apparition des différents caractères
Complétez le tableau ci-dessous en indiquant le nombre de fois où chacun des caractères est
présent dans le texte (appelé nombre d’occurrences).
Vous pouvez vérifier votre décompte : la somme doit faire 232 !
A B C D E F G H I J K L M N O
15 1 1 3 2 1
P Q R S T U V W X Y Z Espace , . ‘
1 2 0 0 0 0 33 2 1 1
SNT en 2nde Données structurées – Algorithme de Huffman page 1/3
Nom de fichier : Huffman-Eleve.odt Date d'impression : 25 mai 2020
3.3 - Analyse préliminaire
Combien de caractères n’apparaissent jamais dans le texte ? …
Quels sont les 5 caractères qui apparaissent le plus souvent ? …
3.4 - Algorithme de compression
Sur une feuille, vous allez préparer votre algorithme déterminant le codage compressé de chaque
caractère. A défaut de manipuler des petits papiers comme dans la vidéo, je vous conseille de partir
du bas de la feuille (fréquence d’apparition faible) et d’aller vers le haut. En recherchant le nombre
d’occurrence le plus faible, si plusieurs possibilités équivalentes existent, vous prendrez en priorité la
première lettre dans l’ordre alphabétique du tableau, puis une « bulle » déjà tracée.
Rappel : vous devez à chaque fois « raccorder »entre elles les deux « bulles » (lettre ou nombre
calculé) de valeur la plus faible et calculer la somme des 2 que vous inscrirez dans la « bulle »
symbolisant le regroupement. Inscrivez un « 0 » sur la flèche de gauche et un « 1 » sur la flèche de
droite.
La dernière « bulle » (en haut) doit contenir la valeur 232 représentant les 232 caractères du
document initial. Votre feuille peut commencer ainsi :
7
0 1
4 G:3 4 4
0 1 0 1 0 1
2 H:2 2 V:2 2 , :2
0 1 0 1 0 1
B:1 F:1 K:1 Q:1 . :1 ‘:1
3.5 - Table de correspondance
Recherchez alors dans votre diagramme le code binaire (lu de hait en bas) de chaque caractère et
complétez le tableau ci-dessous (vous pouvez revoir la vidéo à partir de 11’20).
Car. Code compressé Car. Code compressé Car. Code compressé
A K U
B L V
C M W non codé
D N X non codé
E O Y non codé
F P Z non codé
G Q Espace
H R ,
I S .
J T ‘
SNT en 2nde Données structurées – Algorithme de Huffman page 2/3
Remarque : puisque parfois plusieurs « bulles » portent le même nombre, on peut avoir plusieurs
diagrammes différents, mais tous justes et aussi performants en terme de compression !
3.6 - Analyse de la table de correspondance
Quel est le nombre minimal de bits utilisés pour coder un caractère ? …
Quel est le nombre maximal de bits utilisés pour coder un caractère ? …
Le codage ASCII se fait sur 8 bits par caractère. Est-ce qu’il y a des cas où le codage ASCII standard
est plus performant ?
…
3.7 - Application du code
Écrivez ci-dessous le code binaire compressé correspondant aux 2 premiers mots du texte étudié
(AVEC LE).
AVEC LE → …
En ASCII standard, ces 7 caractères seraient codés sur 7 x 8 = 56 bits.
Sur combien de bits sont codés ces deux mots avec le codage compressé ? …
3.8 - Taille du texte codée de manière compressée
En utilisant le nombre de bits de codage compressé de chaque caractère ainsi que le nombre
d’occurrences de chaque caractère, calculez la taille en bits du texte codé de manière compressée.
…
Calculez la taille en octets :
…
Le texte codé en ASCII standard représente 1856 bits (232 octets). Quel est le gain de taille en
pourcentage de la taille initiale ?
…
3.9 - Modification du texte
Si on ajoute au texte étudié les deux paragraphes suivants de la page 70 du livre, peut-on ré-utiliser
la même table de conversion ? Justifier votre réponse.
…
Si on peut réutiliser la même table de conversion, est-elle optimisée pour le nouveau texte ?
…
SNT en 2nde Données structurées – Algorithme de Huffman page 3/3
