#Codage de HuffmanCopier le lien

Prérequis : arbres binaires (parcours, profondeur) ; file de priorité (tas) ; chapitre Algorithmes gloutons pour l'argument d'échange.

Objectifs d'apprentissage : construire l'arbre de Huffman à la main et en code ; expliquer pourquoi le code obtenu est un code préfixe ; prouver l'optimalité par échange ; encoder, décoder et sérialiser le tout.

#1. PrincipeCopier le lien

Un codage à longueur fixe (ASCII : 8 bits par caractère, quel que soit le caractère) paie le même prix pour 'e' très fréquent et 'z' rare. L'idée de Huffman : des codes de longueur variable, d'autant plus courts que le symbole est fréquent, avec une contrainte forte : le code doit être préfixe, c'est-à-dire qu'aucun code n'est le préfixe d'un autre. Sans elle, le décodage serait ambigu ; avec elle, le flux se lit de gauche à droite sans délimiteur.

Sur « ABRACADABRA » (11 caractères, 5 occurrences de A, 2 de B, 2 de R, 1 de C, 1 de D), l'ASCII dépense 88 bits ; un code de Huffman en utilise 23. Le gain vient du déséquilibre des fréquences : plus la distribution est biaisée, meilleure est la compression.

#Animation interactiveCopier le lien

Entrées : un texte (modifiable) à compresser. Sorties : l'arbre construit, la table code de chaque symbole et la taille compressée. Lecture conseillée : repérez les deux symboles les plus rares ; ils doivent terminer frères, aux profondeurs maximales. C'est le cœur de l'argument d'optimalité.

#Pas-à-pas : construire l'arbreCopier le lien

Formalisé : créer une feuille par symbole pondérée par sa fréquence ; tant que la file contient plus d'un nœud, extraire les deux plus légers, en faire les fils d'un nouveau nœud de fréquence somme, réinsérer ce père. L'arbre résultant donne le code de chaque symbole par le chemin racine vers sa feuille.

#2. Pourquoi le code est préfixeCopier le lien

Chaque symbole correspond à une feuille, et un code est le chemin de la racine à cette feuille. Un chemin vers une feuille ne peut pas contenir une autre feuille sur son trajet (les feuilles n'ont pas de fils) : aucun code n'est donc le préfixe d'un autre. Conséquence directe pour le décodage : on descend dans l'arbre bit à bit, on émet le symbole atteint, on repart de la racine. Le décodage est entrelacé et sans ambiguïté.

#3. Implémentation en PythonCopier le lien

1import heapq2from collections import Counter3 4class Noeud:5    def __init__(self, symbole=None, freq=0, gauche=None, droite=None):6        self.symbole = symbole7        self.freq = freq8        self.gauche = gauche9        self.droite = droite10 11    def __lt__(self, autre):          # le tas compare les fréquences12        return self.freq < autre.freq13 14def construire_arbre(texte):

Le prefixe or "0" traite le cas dégénéré d'un texte formé d'un seul symbole répété : l'arbre est une feuille unique sans arête, on lui attribue explicitement un code d'un bit. Le décodage est en O(longueur du flux), la construction en O(k log k) pour k symboles distincts.

#4. Optimalité : l'argument d'échangeCopier le lien

Le codage de Huffman minimise la longueur totale parmi les codes préfixes binaires, pour une source sans mémoire (symboles indépendants, fréquences connues). L'argument se déroule en deux pas :

1. Il existe un code optimal où les deux symboles les moins fréquents sont frères, aux profondeurs maximales. Si un code optimal plaçait un symbole moins fréquent moins profond qu'un symbole plus fréquent, l'échange de leurs codes raccourcirait le total : contradiction. Et deux symboles de moindre fréquence peuvent toujours être poussés en bas de l'arbre sans allonger le reste.
2. La fusion préserve l'optimalité. Remplacer les deux frères par leur père (de fréquence somme) donne un problème de taille k-1 ; un code optimal pour le petit problème, re-déplié, est optimal pour le grand, puisque les deux feuilles ajoutent exactement une somme de fréquences commune à toutes les solutions.

L'induction sur le nombre de symboles referme la preuve. C'est la même famille d'argument que pour les algorithmes gloutons du chapitre correspondant.

#5. Exercice : format autonome avec arbre sérialiséCopier le lien

Un fichier compressé ne sert à rien sans sa table de codes. Sérialisons l'arbre dans le flux : une feuille s'encode en '1' suivi du symbole sur 8 bits, un nœud interne en '0' suivi des encodages des deux fils.

1def serialiser_arbre(noeud):2    if noeud.symbole is not None:3        return '1' + format(ord(noeud.symbole), '08b')4    return '0' + serialiser_arbre(noeud.gauche) + serialiser_arbre(noeud.droite)5 6def deserialiser_arbre(bits, index=0):7    if bits[index] == '1':8        symbole = chr(int(bits[index + 1:index + 9], 2))9        return Noeud(symbole=symbole), index + 910    gauche, apres_g = deserialiser_arbre(bits, index + 1)11    droite, apres_d = deserialiser_arbre(bits, apres_g)12    return Noeud(gauche=gauche, droite=droite), apres_d13 14def compresser_avec_arbre(texte):

Vérification observable : le round-trip renvoie True et la longueur d'en-tête stockée sur 16 bits limite l'arbre sérialisé à 65535 bits, largement suffisant pour un alphabet de 256 symboles (au plus 256 feuilles, soit environ 257 nœuds et 257 bits de structure plus 2048 bits de données). Comparez : pour un texte court, l'en-tête peut dépasser le gain de compression ; c'est exactement pourquoi les formats réels regroupent les symboles et comparent plusieurs modèles avant de choisir.

#6. ComplexitéCopier le lien

• Construction de l'arbre : O(k log k) pour k symboles distincts (k-1 fusions, chacune en O(log k)).
• Génération des codes : O(k) par le parcours de l'arbre.
• Encodage et décodage : O(longueur du texte) bit à bit (les implémentations réelles traitent des octets et des tables, avec des constantes bien meilleures).

#7. ApplicationsCopier le lien

1. Formats d'archives et d'images : DEFLATE (ZIP, gzip, PNG) combine LZ77 pour les répétitions et Huffman pour les symboles restants.
2. Transmission : HTTP/2 et HTTP/3 utilisent justement HPACK et QPACK, des codages Huffman pour la compression des en-têtes.
3. Multimédia : JPEG et MP3 codent en Huffman les symboles produits par la quantification.
4. Pédagogie : cas d'école d'un glouton optimal avec une preuve courte mais complète.