Codage de Huffman

baissaoui Messages postés 498 Date d'inscription jeudi 2 septembre 2021 Statut Webmaster Dernière intervention 21 août 2024 - 23 juin 2022 à 16:03

Le codage de Huffman

<niv1>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.


<niv1>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.


<niv1>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.


<niv1>Soit la phrase suivante : "COMME_CHARMANT_E". Voici les fréquences d'apparitions des lettres


<niv1>
MACE_HONTR
3222211111



<niv1>Voici l'arbre correspondant :


<niv1>
arbre de huffman



<niv1>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 :

<niv1>
MACE_HONTR
001001100100111110111110101011010111



<niv1>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