Introduction

La compression RLE de la première partie de l'énigme n'est pas adaptée à tous les types de données. En particulier, si on veut utiliser cet algorithme pour compresser une suite de caractères, cela va généralement ne pas être efficace car la plupart des "phrases" ne contiennent pas des plages de valeurs identiques.

Par exemple, pour compresser le mot "compression" cela donnerait quelque chose comme "1c1o1p1r1e2s1i1o1n" car il y a un "c", puis un "o", etc. On voit donc que l'on obtient un mot "compressé" qui est plus long que celui de départ !

Heureusement, il existe d'autres algorithmes de compression et cette seconde partie d'énigme aborde le codage de Huffmann, inventé par David Albert Huffman et publié en 1952.

Codage de Huffman

L'algorithme du codage de Huffman est à la fois extrêmement efficace et très simple à comprendre.

L'idée est de compresser les données de manière à coder les symboles les plus fréquents par des codes courts, et les plus rares par des codes plus longs.

Mais trouver le code optimal pour chaque symbole est plus compliqué qu'il ne semble, et personne n'avait réussi à en proposer un algorithme jusqu'à David Huffmann en 1951, alors qu'il était toujours étudiant. Pour la petite histoire, sa proposition d'algorithme était tellement impressionnante qu'il a été autorisé à valider son année sans passer l'examen final !

Exemple

On va présenter cet algorithme sur un exemple textuel très simple. Dans cet exemple on utilise un langage comportant uniquement 4 caractères, mais très important pour nous car c'est le langage qui représente notre ADN, composé de séquences de quatre caractères : A, C, G et T.

Par exemple, la séquence de 4.6 millions de caractères qui représente la bactérie Escherichia coli commence par :

agcttttcattct

Sans compression

En utilisant le codage habituel des caractères "a", "c", "g" et "t" sur 8 bits utilisé habituellement (voir table ASCII, vue dans l'énigme n°2), on obtient le codage suivant :

a : 01100001
c : 01100011
g : 01100111
t : 01110100

Ainsi, sans compression, notre séquence de 13 caractères ci-desssus se coderait alors en utilisant les 104 bits ($13\times 8=104$) suivants :

01100001011001110110001101110100011101000111010001110100011000110110000101110100011101000110001101110100

Une compression possible

On peut faire mieux en utilisant que 2 bits pour coder chaque caractère (cela suffit car il n'y a que 4 caractères à coder) :

a : 00
c : 01
g : 10
t : 11

Ainsi, notre séquence de 13 caractères serait codée en utilisant uniquement 26 bits ($13\times 2=26$) :

00100111111111010011110111

Mais on peut faire mieux que cela, comme on va le voir tout de suite !

Compression optimale (codage de Huffman)

Dans notre séquence la lettre "t" est la plus fréquente ("t" apparaît 7 fois, "c" trois fois, "a" deux fois et "g" seulement une fois). Si on donne le code le plus court à la lettre "t", 54% du temps (7 caractères sur 13) on utiliserait moins de place. Par exemple, si on utilise le codage suivant :

a : 010
c : 00
g : 011
t : 1

alors nos 13 caractères seraient codés ainsi :

0100110011110001011001

ce qui ne nécessite que 22 bits.

Ce codage des lettres "a", "c", "g" et "t" correspond à ce qu'on appelle le codage de Huffman, qui est le codage optimal, celui donnant la meilleure compression possible (le code le plus court).

Taux de compression : En comparant la taille (en bits) du message non compressé (104 bits) et celle donnée par le codage de Huffman (22 bits), on obtient un taux de compression d'environ 79 % :

$$\text{taux de compression} = \dfrac{\text{taille - taille compressée}}{\text{taille}} = \dfrac{104-22}{104} \simeq 0.79.$$

Décodage

Ce nouveau code peut toujours être décodé même si les caractères sont codés avec des longueurs différentes ! En effet, chaque code n'est pas le début d'un autre, donc il suffit de lire de gauche à droite et de repérer les codes utilisés.

Par exemple, pour décoder

111001

on procède ainsi :

• on lit un 1, cela correspond à "t"
• puis, de même, il y a 2 autres "t"
• et ensuite on voit un 0 donc cela peut être soit "a" (010), soit "c" (00), soit "g" (011) car leurs codages commencent par un zéro
• mais comme il est suivi d'un 0 alors c'est nécessaire un "c"
• cela laisse un 1 pour finir qui représente "t"

Ainsi, on est sûr que 111001 correspond au codage de "ttct" !

a : 00
c : 01
g : 10
t : 1

Algorithme

L'algorithme permettant de trouver le codage de Huffman est astucieux mais simple à comprendre. Il est basé sur la construction d'un arbre, appelé arbre de Huffman.

On commence par calculer le nombre d'apparitions (ou occurrences) de chaque symbole dans le message à compresser :

a : 2 fois
c : 3 fois
g : 1 fois
t : 7 fois

On construit les noeuds correspondant aux différentes lettres en leur associant leur nombre d'apparitions :

On choisit ensuite les deux noeuds des caractères ayant le nombre d'apparition le plus petit (ici "a" et "g"). On les fusionne pour créer un noeud ayant pour valeur la somme des valeurs des deux noeuds ($2+1$, qui vaut 3) :

On oublie les occurrences des deux caractères que l'on vient de combiner mais on va utiliser leur total pour ensuite répéter la même opération. Les valeurs restantes sont 3 (pour le total de la fusion), 3 (pour "c") et 7 (pour "t"), et on fusionne les deux plus petites (ici 3 et 3) pour faire un nouveau noeud et deux nouvelles branches :

Il ne reste plus que deux valeurs à considérer (6 et 7), donc on les fusionne pour obtenir l'arbre final, appelé l'arbre de Huffman (de "agcttttcattct") :

En fusionnant à chaque étape les deux noeuds dont les valeurs sont les plus petites, on est sûr d'obtenir un unique arbre à la fin, c'est l'arbre de Huffman !

Ce dernier étant construit, il ne reste plus qu'à attribuer à chaque caractère son code de Huffman, ce qui est très simple ! Il suffit de partir de la racine (le noeud tout en haut, car l'arbre est représenté à l'envers des arbres que l'on trouve dans la nature), et de descendre vers chaque caractère : si on descend par une branche de gauche c'est un 0, si c'est par une branche de droite c'est un 1.

La lettre "a" est ainsi codée 010 car pour arriver à la lettre "a" dans l'arbre on suit les branches gauche puis droite et enfin gauche :

De même pour les autres lettres et on trouve bien :

Ainsi, le message "agcttttcattct" se compresse, grâce au codage de Huffman, en 0100110011110001011001, soit 22 bits au lieu de 104 sans compression, pour un taux de compression d'environ 79 % comme on l'a vu précédemment.

Autre exemple

Avec l'algorithme décrit, on peut compresser toutes sortes de données. Par exemple, le mot "compresser" donne l'arbre de Huffman suivant

et se code donc

0100111001011101110000111110

donc une compression sur 28 bits au lieu de 80 bits sans compression (10 caractères codés chacun sur 8 bits), soit un taux de compression de $\dfrac{80-28}{80}=0.65=65\%$.

On peut compresser des textes aussi long que l'on veut, d'ailleurs plus le texte est long, plus l'algorithme de Huffman sera efficace.

Pour aller plus loin ...

... sur l'algorithme de Huffman

Concrètement, les arbres de Huffman ne sont pas construits manuellement. Mais un arbre de Huffman est construit, par un programme, à chaque fois que vous prenez une photo en JPG (le format pris par nos smartphones), que vous compressez un fichier en ZIP, que vous enregistrez une vidéo...

La compression de Huffman n'est pas efficace si la longueur du message est trop courte car il faut aussi enregistrer l'arbre dans les données pour pouvoir décompresser le message. En revanche, elle est extrêmement efficace pour des messages longs puisque l'enregistrement de l'arbre devient négligeable (en taille) par rapport à la compression obtenue.

... sur les arbres

En informatique, un arbre est une structure de données qui permet de représenter de manière symbolique des informations structurées de manière hiérarchique.

Cette structure d'arbre est très utilisée en informatique. Par exemple :

• le système de fichiers sur votre ordinateur est représenté par un arbre (il y a des dossiers, dans lesquels se trouvent des fichiers et d'autres dossiers, qui contiennent aussi des fichiers et des dossiers, etc.) :

• pour votre navigateur, une page Web est également représentée par un arbre :

L'analogie avec les arbres réels peut s'avérer trompeuse. Les arbres - en informatique - sont le plus souvent représentés avec la racine en haut, puis les noeuds, et les feuilles en bas.

Dans un arbre, on retrouve donc ce qu'on appelle des noeuds dont chacun dépend d'un antécédent (sauf le noeud racine) et à des descendants (sauf les feuilles). L'intérêt est de stocker des informations dans ces noeuds (comme les symboles, les nombres d'occurrecnce pour l'arbre de Huffman).

Les descendants d'un noeud s'appellent les fils, et le noeud dont ils sont issus est leur père.

Une catégorie d'arbre est celle dont les noeuds possèdent au maximum deux fils, ce sont des arbres binaires. L'arbre de Huffman est à classer dans cette catégorie puisque de chaque noeud (sauf les feuilles, qui correspondent aux symboles à coder) part deux branches vers les fils gauche et droit. Ces arbres binaires sont très utilisés en pratique pour stocker, insérer et rechercher des informations de manière très efficace (= très rapide).

🔎 Énigme 🔎