L'objectif de cet exercice est de compresser une chaîne de caractère en utilisant un codage de Huffman. On appelle codage d'une chaîne de caractère une bijection depuis l'ensemble des chaînes de caractère vers un autre ensemble.
Un code de Huffman est un code binaire à longueur variable sans préfixe, c'est à dire que (1) il associe à un caractère une chaîne binaire (qui ne contient que des 0 et des 1) de longueur variable d'un caractère à l'autre et (2) aucune de ces chaines obtenues n'est préfixe d'une autre, ce qui assure que l'on peut "décoder", c'est-à-dire trouver une bijection réciproque. Ceci permet de réduire la place prise par les données, en se basant sur la fréquence d'apparition des éléments dans le texte.
L'exemple suivant illustre le principe du code de Huffman. On cherche à réduire l'espace pris par la chaîne de caractères "test". On rappelle qu'en code ascii étendu, un caractère informatique occupe 8 bits. "test" est composée de trois caractères différents. Le code de Huffman suggère d'étudier les fréquences d'apparition des caractères ; 't' apparaît 2 fois, 'e' 1 fois, et 's' 1 fois. On va donc coder la lettre 't' en utilisant moins de bits que les lettres 'e' et 's'. Si on alloue le code binaire "1" à la lettre 't', et les codes "00" et "01" respectivement à 'e' et 's', on peut coder la chaîne de caractères "test" avec le code "100011", soit 6 bits au lieu des 32 nécessaires avec le codage ascii. On remarque que comme le code est sans prefixe, l'opération inverse qui consiste à retrouver le texte "test" à partir de la chaîne de bits "100011" est bien définie. En effet, la chaîne commence avec un 1, ce qui ne peut être qu'un t, puis un 0, donc soit un e soit un s, le fait qu'il soit suivi d'un 0 nous donne que c'est un e, ensuite vient un 0, donc soit un e soit un s, suivi d'un 1 donc c'est un s et enfin un 1 donc un t.
Le fonctionnement du code de Huffman est simple. Pour trouver quel code utiliser pour chaque caractère, on va construire un arbre binaire dont les branches maximales représentent le code associé à chaque élément. Cet arbre contiendra donc autant de feuilles qu'il y a de caractères à encoder. Pour trouver le code associé, on parcourt l'arbre depuis la racine jusqu'à la feuille. Quand on passe par le fils gauche, on ajoute un '0' au code, quand on passe par le fils droit, on ajoute un '1' (notez que le sens n'a pas d'importance sur la longueur de la chaîne générée). Pour réduire la taille occupée par la version codée, il faut donc s'arranger pour que les caractères ayant la plus haute fréquence soient moins profonds dans l'arbre et donc représentés par des codes plus courts.
Le processus précis pour la construction de l'arbre est décrit à l'adresse suivante : http://www.cs.cf.ac.uk/Dave/Multimedia/node210.html.
Si on reprend l'exemple précédent, le code est représenté par l'arbre binaire suivant :
racine
/ \
/ \ t
e s
Dans cet exercice, l'objectif est de générer le code de Huffman pour une chaîne de caractère donnée, et d'en obtenir la taille. On ne demande pas de gérer les accents ou caractères spéciaux, les chaînes ne seront composées que d'espaces, de caractères de ponctuation et de caractères de l'alphabet latin, majuscules et minuscules.
| Entrée | Sortie |
|---|---|