La compression numérique : synthèse
HuffmanRLE LZ*

Introduction


Sans perte


Avec pertes


Par type de données


Tableau récapitulatif


Logiciels


Bibliographie


Plan du site


Webmasters

Le codage de Huffman

Cette technique de compression sans perte a hérité du nom de son inventeur, David Huffman. Elle repose sur le codage statistique d'un fichier octet par octet. Plus les octets apparaissent souvent, plus les codes qui les remplacent sont courts. Selon ce point de vue, le codage de Huffman peut être comparé au code Morse. Le codage de Huffman peut être réalisé sur le mode adaptatif, semi-adaptatif ou non adaptatif.

Le codage de Huffman est utilisé pour la compression du son au format MP3 et des images aux formats PNG et JPEG.

Principe de fonctionnement :

L'algorithme parcourt les données d'un fichier et examine chaque octet ainsi que le nombre fois où ce dernier apparaît.

Ensuite, l'algorithme construit un arbre (ou graphe). La construction de l'arbre s'effectue en commençant par ses feuilles jusqu'à sa racine. Pour ce faire, les octets sont classés par ordre décroissant de fréquence d'apparition. Chaque fréquence d'apparition correspond donc à un octet et constitue les feuilles de l'arbre. Elles sont alors liées deux par deux pour former les noeuds du graphe jusqu'à ce qu'il n'y ait plus qu'un seul noeud, soit la racine. Les noeuds sont ainsi formés par la somme de chaque fréquence d'apparition de ses deux feuilles ou de ses deux noeuds-descendants directs. Puis, les branches de l'arbre - c'est à dire les liens qui unissent les noeuds - se voient attribuer soit le chiffre 1, soit le chiffre 0 selon ce principe : le lien qui unit le noeud signifiant la fréquence la plus élevée avec son noeud-ascendant se voit attribuer le chiffre 1, les autres le chiffre 0. En fin de compte, les octets compressés sont par codés par les chiffres attribués aux liens, qui sont alignés en remontant depuis le noeud-racine jusqu'aux feuilles terminales.

Illustration :

Par exemple, le mot "JULONOVO" compte 1 fois les lettres "J, U, L, N, V" et 3 fois la lettre "O". Les lettres sont donc codées comme suit : J : 000 ; U : 001 ; L : 010 ; N : 011 ; V : 10 ; O : 11. Le caractère "O" qui apparaît le plus souvent reçoit un code plus court que les autres.

Exemple de graphe construit par l'algorithme de Huffman*

Haut de la page

 
Toutes les images publiées sur ce site sont la propriété personnelle des auteurs.
* : Image créée avec Microsoft ® Paint v. 5.1
Il est nécessaire de configurer votre navigateur de manière qu'il accepte le javascript pour bénéficier pleinement de ce site.
Comment faire ?
Date de la dernière mise à jour : juin 2006