Question transversaleMathsNSIArbres et structures de données

Comment compresser un texte sans perdre la moindre information ?

Huffman donne des codes courts aux lettres fréquentes, grâce à un arbre construit en fusionnant les deux symboles les plus rares. ABRACADABRA passe de 33 bits (3 bits par lettre) à 23 bits, près de la limite de 22,4 bits fixée par l'entropie de Shannon.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

Quand je compresse un dossier en fichier zip, il devient plus léger, et pourtant je retrouve exactement tous mes fichiers. Je me suis demandé comment on peut réduire la taille sans rien perdre. En NSI, j'ai découvert le codage de Huffman, inventé par un étudiant en 1952, qui utilise un arbre binaire et les fréquences des lettres.

L'enjeu et les notions du programme

Construire un code préfixe optimal à l'aide d'un arbre et comparer sa longueur moyenne à la borne de l'entropie, calculée avec le logarithme.

Mathématiques

Fréquences, moyenne pondérée (seconde)
Logarithme en base 2 (terminale)
Dénombrement des mots binaires (terminale)

Numérique et sciences informatiques

Arbres binaires, feuilles et chemins (terminale)
Représentation des données textuelles (première)

Le plan de l'exposé en 9,5 min

1. Introduction
1 min
Le mot ABRACADABRA utilise 5 lettres différentes. Avec un code de longueur fixe, il faut 3 bits par lettre ( $2^{2} = 4 < 5 \leq 8 = 2^{3}$ 2²=4<5≤8=2³), soit 33 bits. Problématique : peut-on faire plus court en tenant compte des fréquences, sans ambiguïté au décodage ?
2. NSI : construire l'arbre de Huffman
3,5 min
Fréquences : A 5, B 2, R 2, C 1, D 1. On fusionne à chaque étape les deux nœuds de plus faibles poids : C et D (2), puis B et R (4) [ou une autre paire de poids égaux], puis les nœuds de poids 2 et 4 (6), enfin A (5) et le nœud 6 (11).
On lit les codes sur l'arbre : 0 pour gauche, 1 pour droite. On obtient par exemple A = 0, C = 100, D = 101, B = 110, R = 111. Aucun code n'est le début d'un autre (les lettres sont des feuilles) : le décodage est sans ambiguïté, sans séparateur.
Longueur totale : $5 \times 1 + 2 \times 3 + 2 \times 3 + 1 \times 3 + 1 \times 3 = 23$ 5×1+2×3+2×3+1×3+1×3=23 bits, au lieu de 33 : 30 % de gain.
3. Mathématiques : la limite de Shannon
3,5 min
Shannon a montré qu'aucun code sans perte ne peut, en moyenne, utiliser moins de $H = - \sum p_{i} lo g_{2} p_{i}$ H=-Σ pᵢlog₂pᵢ bits par symbole, l'entropie de la source. Ici, avec $p_{A} = \frac{5}{11}$ p_A=5/11, $p_{B} = p_{R} = \frac{2}{11}$ p_B=p_R=2/11, $p_{C} = p_{D} = \frac{1}{11}$ p_C=p_D=1/11, on trouve $H \approx 2, 04$ H≈2,04 bits par lettre, soit environ 22,4 bits pour le mot.
Le code de Huffman atteint $\frac{23}{11} \approx 2, 09$ 23/11≈2,09 bits par lettre : il est à moins de 0,1 bit de la limite. On démontre qu'il est optimal parmi les codes qui attribuent un nombre entier de bits à chaque lettre.
Interprétation : $- lo g_{2} p$ -log₂p est la « quantité d'information » d'un symbole de probabilité $p$ p. Une lettre rare apporte beaucoup d'information et mérite un code long ; une lettre fréquente, peu, et mérite un code court.
4. Conclusion
1,5 min
On compresse sans perte en donnant des codes courts aux symboles fréquents, organisés en arbre pour rester décodables : ABRACADABRA passe de 33 à 23 bits. L'entropie fixe la limite infranchissable, presque atteinte. J'ouvre sur les formats zip et PNG, qui combinent Huffman avec la recherche de répétitions.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

A = 0 C = 100 D = 101 B = 110 R = 111 A =0 C =100 D =101 B =110 R =111 5 \times 1 + 6 \times 3 = 23 bits < 33 H = - \sum p_{i} lo g_{2} p_{i} \approx 2, 04 \Rightarrow 11 H \approx 22, 4 5\times1+6\times3=23 bits <33 H=-Σ pᵢlog₂pᵢ\approx2,04 \Rightarrow 11H\approx22,4

Conclusion : la réponse à la question

Le codage de Huffman compresse sans perte grâce à un arbre et aux fréquences ; l'entropie, un calcul de logarithmes, dit jusqu'où l'on peut aller. La compression a une limite mathématique précise.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Pourquoi le décodage est-il sans ambiguïté ?

Le code est préfixe : chaque lettre est une feuille, donc aucun code n'est le début d'un autre.

Décodez 0110100.

0 → A, 110 → B, 100 → C : ABC.

Que vaut l'entropie si les 5 lettres étaient équiprobables ?

$lo g_{2} 5 \approx 2, 32$ log₂5≈2,32 bits par lettre.

Peut-on compresser un fichier déjà compressé ?

Presque pas : ses symboles sont devenus quasi équiprobables, son entropie est proche du maximum.

Le décodeur doit-il connaître l'arbre ?

Oui : on transmet l'arbre ou les fréquences avec le texte compressé.

Les pièges qui coûtent des points

Fusionner les deux nœuds les plus fréquents au lieu des plus rares.
Construire un code qui n'est pas préfixe.
Croire qu'on peut descendre sous l'entropie.

Revoir les notions

Autres questions : arbres et structures de données

Toutes les questions maths-nsi →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →