Codage de Huffman

Mai 2015

Le codage de Huffman

David Huffman a proposé en 1952 une méthode statistique qui permet d'attribuer un mot de code binaire aux différents symboles à compresser (pixels ou caractères par exemple). La longueur de chaque mot de code n'est pas identique pour tous les symboles: les symboles les plus fréquents (qui apparaissent le plus souvent) sont codés avec de petits mots de code, tandis que les symboles les plus rares reçoivent de plus longs codes binaires. On parle de codage à longueur variable (en anglais VLC pour variable code length) préfixé pour désigner ce type de codage car aucun code n'est le préfixe d'un autre. Ainsi, la suite finale de mots codés à longueurs variables sera en moyenne plus petite qu'avec un codage de taille constante.

Le codeur de Huffman crée un arbre ordonné à partir de tous les symboles et de leur fréquence d'apparition. Les branches sont construites récursivement en partant des symboles les moins fréquents.

La construction de l'arbre se fait en ordonnant dans un premier temps les symboles par fréquence d'apparition. successivement les deux symboles de plus faible fréquence d'apparition sont retirés de la liste et rattachés à un noeud dont le poids vaut la somme des fréquences des deux symboles. Le symbole de plus faible poids est affecté à la branche 1, l'autre à la branche 0 et ainsi de suite en considérant chaque noeud formé comme un nouveau symbole, jusqu'à obtenir un seul noeud parent appelé racine.
Le code de chaque chaque symbole correspond à la suite des codes le long du chemin allant de ce caractère à la racine. Ainsi, plus le symbole est "profond" dans l'arbre, plus le mot de code sera long.

Soit la phrase suivante : "COMMENT_CA_MARCHE". Voici les fréquences d'apparitions des lettres

MACE_HONTR
3222211111

Voici l'arbre correspondant :

arbre de huffman

Les codes correspondants à chaque caractère sont tels que les codes des caractères les plus fréquents sont courts et ceux correspondant aux symboles les moins fréquents sont longs :

MACE_HONTR
001001100100111110111110101011010111

Les compressions basées sur ce type de codage donnent de bons taux de compressions, en particulier pour les images monochromes (les fax par exemple). Il est notamment utilisé dans les recommandations T4 et T5 de l'ITU-T

Pour une lecture illimitée hors ligne, vous avez la possibilité de télécharger gratuitement cet article au format PDF :
Codage-de-huffman .pdf

Réalisé sous la direction de , fondateur de CommentCaMarche.net.

A voir également


Huffman coding
Huffman coding
Código Huffman
Código Huffman
Huffman-Kodierung
Huffman-Kodierung
Codifica di Huffman
Codifica di Huffman
Codificação de Huffman
Codificação de Huffman
Ce document intitulé «  Codage de Huffman  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.