Codage de Huffman

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>

M	A	C	E	_	H	O	N	T	R
3	2	2	2	2	1	1	1	1	1

<niv1>Voici l'arbre correspondant :


<niv1>


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

M	A	C	E	_	H	O	N	T	R
00	100	110	010	011	1110	1111	1010	10110	10111

<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