Vidéo et imagerie numérique - Codage de Huffman

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

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

Voici l'arbre correspondant :

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 :

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

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

Discussions pertinentes trouvées dans le forum

26/05 15h52	codage de huffman	Développement	31/05 15h53->sebsauvage	11
09/01 11h48	Algo de Huffman en C	Développement	09/01 11h55->sebsauvage	1
03/04 16h44	Algo de Huffman en ADA	Windows	19/02 17h59->winnie	1
30/05 10h26	[c++ Huffman] algorithme de compression	Développement	30/05 14h44->ollie314	1
17/02 14h49	De l'aide sur Huffman s'il vous plait!!!	Développement	17/02 14h49->winnie	0
08/12 13h34	Compression de huffman	Développement	08/12 13h34->brunbe	0
21/02 11h13	En-tête de HUFFMAN	Développement	21/02 11h13->Cahls	0
17/04 17h02	Parcourir arbre de huffman	Développement	17/04 17h02->Lord Van	0
30/01 19h05	probleme (algorithme de Huffman en C)	Développement	30/01 19h05->touf_truc	0
Discussion fermée Problème résolu		Plus de discussions sur « Huffman »