Compression de données/Codage de Huffman

Compression de données

• Introduction
• Types de compression
• Techniques de compression sans perte
  • Codage par répétition
    • Run-length encoding
  • Codage entropique
    • Codage de Huffman
    • Codage de Shannon-Fano
  • Codage par dictionnaire
    • Lempel-Ziv-Welch (LZW)
  • Codage par modélisation de contexte
  • Transformée de Burrows-Wheeler
  • Archive de fichiers
• Techniques de compression avec pertes
  • Le format JPEG 2000
• Taux de compression
• Bibliographie et liens

Le codage de Huffman est un algorithme de compression de données sans perte. Le codage de Huffman utilise un code à longueur variable pour représenter un symbole de la source (par exemple un caractère dans un fichier). Le code est déterminé à partir d'une estimation des probabilités d'apparition des symboles de source, un code court étant associé aux symboles de source les plus fréquents.

Un code de Huffman est optimal au sens de la plus courte longueur pour un codage par symbole, et une distribution de probabilité connue. Des méthodes plus complexes réalisant une modélisation probabiliste de la source permettent d'obtenir de meilleurs ratios de compression.

Il a été inventé par David Albert Huffman, et publié en 1952.

Principe

Le principe du codage de Huffman repose sur la création d'une structure d'arbre composée de nœuds.

Supposons que la phrase à coder est « this is an example of a huffman tree ». On recherche tout d'abord le nombre d'occurrences de chaque caractère. Dans l'exemple précédent, la phrase contient 2 fois le caractère h et 7 espaces. Chaque caractère constitue une des feuilles de l'arbre à laquelle on associe un poids égal à son nombre d'occurrences.

this is an example of a huffman tree

Occurence de chaque caractère, trié du plus fréquent au moins fréquent :

Nœud		a	e	f	h	i	m	n	s	t	l	o	p	r	u	x
Occurrence	7	4	4	3	2	2	2	2	2	2	1	1	1	1	1	1

L'arbre est créé de la manière suivante, on associe chaque fois les deux nœuds de plus faibles poids, pour donner un nouveau nœud dont le poids équivaut à la somme des poids de ses fils.

Premier nœud avec u et x (de poids 2 = 1 + 1), avec mise à jour de l'ordre de tri :

Nœud		a	e	f	h	i	m	n	s	t	┌─┐ u x	l	o	p	r
Occurrence	7	4	4	3	2	2	2	2	2	2	2	1	1	1	1

On réitère ce processus jusqu'à n'avoir plus qu'un seul nœud : la racine.

Deuxième nœud avec p et r :

Nœud		a	e	f	h	i	m	n	s	t	┌─┐ u x	┌─┐ p r	l	o
Occurrence	7	4	4	3	2	2	2	2	2	2	2	2	1	1

Troisième nœud avec l et o :

Nœud		a	e	f	h	i	m	n	s	t	┌─┐ u x	┌─┐ p r	┌─┐ l o
Occurrence	7	4	4	3	2	2	2	2	2	2	2	2	2

Quatrième nœud avec p-r et l-o de poids total 4 :

Nœud		a	e	┌───┐ ┌┴┐ ┌┴┐ p r l o	f	h	i	m	n	s	t	┌─┐ u x
Occurrence	7	4	4	4	3	2	2	2	2	2	2	2

Cela continue jusqu'à ce qu'il ne reste plus que l'arbre de codage (dont le poids est le nombre de caractères). On associe ensuite par exemple le code 0 à chaque embranchement partant vers la gauche et le code 1 vers la droite. Pour l'exemple précédent, on obtient cet arbre :

          0┌──────────┴──────────┐
   0┌──────┴──────┐           ┌──┴──┐
0┌──┴───┐1     0┌─┴───┐1         ┌──┴──┐
 e  0┌──┴──┐1   a  ┌──┴──┐     ┌─┴─┐ ┌─┴─┐
   ┌─┴─┐ ┌─┴─┐   ┌─┴─┐ ┌─┴─┐   n   s t ┌─┴─┐
   p   r l   o   f   h i   m           u   x

Et cette table de codage binaire :

Caractère	Code binaire
e	000
p	00100
r	00101
l	00110
o	00111
a	010
f	01100
h	01101
i	01110
m	01111
	10
n	1100
s	1101
t	1110
u	11110
x	11111

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 selon la branche suivie. Il est nécessaire de partir de la racine pour obtenir les codes binaires car sinon lors de la décompression, partir des feuilles peut entraîner une confusion lors du décodage.

La phrase « this is an example of a huffman tree » se code alors sur 137 bits au lieu de 288 bits (si le codage initial des caractères tient sur 8 bits).

 t     h     i    s        i    s       a   n       e    x    a    m     p     l    e    
1110 01101 01110 1101 10 01110 1101 10 010 1100 10 000 11111 010 01111 00100 00110 000 10

  o     f       a       h     u     f     f     m    a   n       t     r    e   e
00111 01100 10 010 10 01101 11110 01100 01100 01111 010 1100 10 1110 00101 000 000

L'algorithme génère des codes non ambigus pour le décodeur : chaque code généré (Par exemple : 10 pour espace) n'est le préfixe d'aucun autre.

Différentes méthodes de construction de l'arbre

Il existe trois variantes de l'algorithme de Huffman, chacune d'elles 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 français, où les fréquences d'apparition du 'e' sont énormes ; celui-ci aura donc un code très court) ;

semi-adaptatif

Le fichier est d'abord lu, de manière à calculer les occurrences 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. Cette compression occasionnera un gain de bits supérieur ou égal au codage de Huffman statique mais il sera nécessaire, pour la décompression, de transmettre l'arbre, ce qui annulera généralement le gain obtenu ;

adaptatif

C'est la méthode qui offre a priori les meilleurs taux de compression car il utilise un arbre connu (et ainsi non transmis) qui sera ensuite modifié de manière dynamique au fur et à mesure de la compression du flux selon les symboles précédemment rencontrés. Cette méthode représente cependant le gros désavantage de devoir modifier souvent l'arbre, ce qui implique un temps d'exécution plus long. Par contre, la compression est toujours optimale et il n'est pas nécessaire que le fichier soit connu avant de compresser. En particulier, l'algorithme est capable de travailler sur des flux de données (streaming), car il n'est pas nécessaire de connaître les symboles à venir.

Propriétés

Un code de Huffman est un code de source. Pour une source $S$, représentée par une variable aléatoire $X$, de distribution de probabilité $p$, l'espérance de la longueur d'un code $C$ est donnée par

$L(C)=\sum _{x\in \Omega }p(x)\cdot l(x)$

Où $l(x)$ est la longueur du mot de code, $C(x)$ le code associé au symbole de source $x$, et $\Omega$ est l'ensemble des symboles de source.

Un code de Huffman est un code préfixe à longueur variable. Il est optimal, au sens de la plus courte longueur, pour un codage par symbole. C'est-à-dire que pour un code de Huffman $C^{*}$, et pour tout code $C$ uniquement décodable, alors :

$L(C^{*})\leq L(C)$

Limitations du codage de Huffman

On peut montrer que pour une source X, d'entropie H(X) la longueur moyenne L d'un mot de code obtenu par codage de Huffman vérifie :

$H(X)\leq L<H(X)+1$

Cette relation montre que le codage de Huffman s'approche de l'entropie de la source et c'est-à-dire du code optimum mais cela peut s'avérer en fait assez peu intéressant dans le cas où l'entropie de la source est forte, et où un surcoût de 1 bit devient important. De plus le codage de Huffman impose d'utiliser un nombre entier de bit pour un symbole source, ce qui peut s'avérer peu efficace.

Une solution à ce problème est de travailler sur des blocs de n symboles. On montre alors qu'on peut s'approcher de façon plus fine de l'entropie :

$H(X)\leq L<H(X)+{\frac {1}{n}}$

mais le processus d'estimation des probabilités devient plus complexe et coûteux.

De plus, le codage de Huffman n'est pas adapté dans le cas d'une source dont les propriétés statistiques évoluent au cours du temps, puisque les probabilités des symboles se modifient et le codage devient inadapté. La solution consistant à ré-estimer à chaque itération les probabilités symboles est impraticable du fait de sa complexité en temps. La technique devient alors le codage Huffman adaptatif : à chaque nouveau symbole la table des fréquences est remise à jour et l'arbre de codage modifié si nécessaire. Le décompresseur faisant de même pour les mêmes causes… il reste synchronisé sur ce qu'avait fait le compresseur.

En pratique, lorsque l'on veut s'approcher de l'entropie, on préfèrera un codage arithmétique qui est optimal au niveau du bit.

Des méthodes plus complexes réalisant une modélisation probabiliste de la source et tirant profit de cette redondance supplémentaire permettent d'améliorer les performances de compression de cet algorithme (voir Compression de données/LZ77, prédiction par reconnaissance partielle, pondération de contextes).

Code canonique

Pour un même ensemble de symbole à coder, plusieurs codes de Huffman différents peuvent être obtenus.

Il est possible de transformer un code de Huffman en un code de Huffman canonique qui est unique pour un ensemble de symboles d'entrée donné. Le principe est d'ordonner au départ les symboles dans l'ordre lexical.

Remarque : entre deux symboles S1 et S2 qui, dans un code de Huffman spécifique, sont codés de la même longueur sont toujours codés de la même longueur dans le code Huffman canonique. Dans le cas où deux symboles ont la même probabilité et deux longueurs de code différentes, il est possible que le passage d'un code de Huffman à un code de Huffman canonique modifie la longueur de ces codes, afin de garantir l'attribution du code le plus court au premier symbole dans l'ordre lexicographique.

Cette section est vide, pas assez détaillée ou incomplète.

Utilisations

Le codage de Huffman ne se base que sur la fréquence relative des symboles d'entrée (suites de bits) sans distinction pour leur provenance (images, vidéos, sons, etc.). C'est pourquoi il est en général utilisé au second étage de compression, une fois la redondance propre au média mise en évidence par d'autres algorithmes. On pense en particulier à la compression JPEG pour les images, MPEG pour les vidéos et MP3 pour le son, qui peuvent retirer les éléments superflus imperceptibles pour les humains. On parle alors de compression non conservative (avec pertes).

D'autres algorithmes de compression, dits conservatifs (sans pertes), tels que ceux utilisés pour la compression de fichiers, utilisent également Huffman pour comprimer le dictionnaire résultant. Par exemple, LZH (Lha) et deflate (ZIP, gzip, PNG) combinent un algorithme de compression par dictionnaire (LZ77) et un codage entropique de Huffman.

Histoire

Le codage a été inventé par David Albert Huffman, lors de sa thèse de doctorat au MIT. L'algorithme a été publié en 1952 dans l'article A Method for the Construction of Minimum-Redundancy Codes, dans les Proceedings of the Institute of Radio Engineers.

Les premiers Macintosh de la société Apple utilisaient un code inspiré de Huffman pour la représentation des textes : les 15 caractères les plus fréquents d'une langue étaient codés sur 4 bits, et la 16^ème configuration servait de préfixe au codage des autres sur un octet (ce qui faisait donc tantôt 4 bits, tantôt 12 bits par caractère voir UTF-8). Cette méthode simple se révélait économiser 30 % d'espace sur un texte moyen, à une époque où la mémoire vive restait encore un composant coûteux.

Voir aussi

Chapitres connexes

• Codage entropique
• Codage de Shannon-Fano, similaire au codage de Huffman mais où la méthode de calcul des codes diffère et peut aboutir à un arbre de codage différent.

Liens externes

• Generateur interactif de l'arbre de Huffman
• Generateur visuel de l'arbre d'Huffman

Bibliographie

• anglais D.A. Huffman, "A method for the construction of minimum-redundancy codes" (PDF), Proceedings of the I.R.E., septembre 1952, pp 1098-1102
• anglais Thomas M. Cover, Joy A. Thomas, Elements of Information Theory, Wiley-Interscience, 2006 (ISBN 978-0-471-24195-9) [détail des éditions]