Compression
On a (cf. figure 2) donc un taux de compression de 50 % sur cette chaîne de caractères. Ce taux varie en fonction de la répétition des caractères ; pour une chaîne ne comportant aucune redondance (par exemple : ABCDEF) on a un gain de taille nul (la sortie dans ce cas sera ABCDEF).
Figure 2 : Compression
L’algorithme de décompression (cf. figure 3) restitue le caractère gràce à son identifiant.
Figure 3 : Décompression
Le principe, on peut le voir, est simple. La problématique revient dès lors à trouver un système d’identification permettant, avec le moins de bits possibles, de retrouver et restituer le caractère identifié.
L’approche de Huffman a été de créer un arbre binaire (dit arbre de Huffman), où on prend pour identifiant le chemin de la lettre dans l’arbre : cf. figure 4.
Figure 4 : Arbre de Huffman
On objectera que l’on aurait pu utiliser un unique bit pour coder les deux caractères A et B (A=0 et B=1). En pratique, l’implémentation nécessite de prévoir l’insertion d’un marqueur ``nouvel élément’’ (à la fin du processus, dans notre exemple, ce ``nouvel élément’’ a pour identifiant 11 ; on le note par la lettre phi). L’identifiant de A (0) est de moindre taille que celui de B (10). Comme on est en présence d’un arbre binaire, on peut déduire que chaque nouvelle lettre aura un identifiant plus long de un bit que la lettre précédente.
Il serait donc intéressant de placer plus près de la racine les lettres les plus souvent rencontrées (au moyen d’une étude statistique sur les caractères rencontrés), car leur identifiant n’occuperait, à chaque fois, que quelques bit (un dans le cas précédent (figure 4)). Afin de valider ce principe, nous allons l’appliquer à une chaîne de caractères un peu plus complexe : ``AGACGGCCGCCAC’’. Nous reclasserons, dans un premier temps, les éléments de l’arbre en fonction de leur fréquence d’apparition, chaque fois qu’il sera nécessaire (cf. figure 6). Puis nous reprendrons la même opération (la même chaîne de caractères) sans reclasser selon leur fréquence d’apparition les feuilles de l’arbre, afin de quantifier le gain de place ainsi obtenu (cf. figure 7). On a, à chaque fois, le flux d’entrée, l’arbre de Huffman associé et le flux de sortie.
La place totale occupée par les fichiers compressés est de 48 bits avec contre 51 bits sans réorganisation. On observe donc un (petit) gain de place. Dans de longs fichiers, la tendance va en s’amplifiant, d’autant plus qu’il existe dans toutes les langues des lettre qui reviennent plus souvent que d’autres, tels le e en français (cf. figure 5).
Figure 5 : Fréquences relatives des lettres en français
Nous avons notre algorithme à un petit détail près : lors de la décompression, comment l’algorithme va-t-il faire la différence entre un octet (la lettre A) lorsqu’il la rencontre pour la première fois) et un identifiant (séquence de bits) ? Nous résoudrons ce problème en faisant précéder de notre marqueur phi toute présentation d’un caractère - ou, plus précisément, de son identifiant id(phi).
Figure 6 : Compression avec réorganisation de l’arbre
Figure 7 : Compression sans réorganisation de l’arbre
