Huffman Coding
Le codage de Huffman, publié par David Huffman en 1952, est un algorithme de construction de codes préfixes qui affecte des codes courts aux symboles fréquents et longs aux rares, atteignant la borne inférieure d'entropie.
Objectif
Il construit des codes préfixes optimaux pour la compression sans perte lorsque les fréquences des symboles sont connues, et constitue le moteur de DEFLATE, JPEG et MP3.
Mécanisme
On compte les fréquences des symboles et on construit un arbre de Huffman : on fusionne répétitivement les deux nœuds de plus basse fréquence en un nouveau parent jusqu'à ce qu'il ne reste que la racine ; le chemin racine-vers-feuille (gauche 0, droite 1) donne le code de chaque symbole. Les symboles fréquents obtiennent des chemins courts.
Cas d’usage
- Étape de codage entropique dans DEFLATE
- Étape de codage entropique dans JPEG/MP3
- Moteur de la compression de texte