Codage de Huffman
Définition
Le codage de Huffman est un algorithme de compression qui fut mis au point en 1952 par David Huffman. C'est une compression de type statistique qui grâce à une méthode d'arbre que nous allons détailler plus loin permet de coder les octets revenant le plus fréquemment avec un code de bit beaucoup plus court. Cet algorithme offre des taux de compression assez bon et est utilisé dans de nombreux formats de compression (MP3, bzip2 etc.)
Principe
Le principe du codage de Huffman repose sur la création d'un arbre composé de nœuds.
Supposons que la phrase à coder est « Wikipédia ». On recherche tout d'abord le nombre d'occurrences de chaque caractère (ici les caractères 'a', 'd', 'é', 'k', 'p' et 'w' sont représentés chacun une fois et le caractère 'i' trois fois). Chaque caractère constitue une des feuilles de l'arbre à laquelle on associe un poids valant son nombre d'occurrence.
Puis l'arbre est créé suivant un principe simple : on associe à chaque fois les deux nœuds de plus faibles poids pour donner un nœud de poids équivalent à la somme de ses fils jusqu'à n'en avoir plus qu'un, la racine. On associe ensuite à chaque branche la plus faible d'un nœud le code 0 et la plus forte le code 1, comme sur le schéma :
Image manquante
Arbre_huffman.png
Image:arbre_huffman.png
Pour obtenir le code binaire de chaque caractère on remonte l'arbre à partir de la racine jusqu'aux feuilles en rajoutant à chaque fois au code un 0 ou un 1. Il est en effet nécessaire de partir de la racine pour obtenir les codes binaires car lors de la décompression, partir des feuilles entrainerait une confusion lors du décodage. Ici, pour coder 'Wikipédia', nous obtenons donc en binaire : 101 11 011 11 100 010 001 11 000.
Il existe trois variantes de l'algorithme de Huffman, chacune d'elle définissant une méthode pour la création de l'arbre :
- statique : chaque octet a un code prédéfini par le logiciel. L'arbre n'a pas besoin d'être transmis, mais la compression ne peut s'effectuer que sur un seul type de fichier (ex: un texte en francais, où les fréquences d'apparition du 'e' sont énormes, celui-ci aura un code très court)
- semi-adaptatif : le fichier est d'abord lu, de manière à calculer les récurrences de chaque octet puis l'arbre est construit à partir des poids de chaque octet. Cet arbre restera le même jusqu'à la fin de la compression. Il sera nécessaire pour la décompression de transmettre l'arbre.
- adaptatif : c'est la méthode qui offre à priori les meilleurs taux de compression car l'arbre est construit de manière dynamique au fur et à mesure de la compression du flux. Cet méthode représente cependant le gros désavantage de devoir reconstruire l'arbre à chaque fois, ce qui implique un temps d'exécution énorme.
| Image manquante Symbole-ordinateur.png | Portail Informatique - Accédez d'un seul coup d’œil à toute la série des articles de Wikipédia concernant l'informatique. |