Codage de Huffman

Considérons le texte ha ha ho ho qui comporte n = 11 caractères – en comptant les espaces. On souhaite coder ce texte pour en faire un fichier. On pourrait choisir le codage iso-8859-1. Dans ce codage,

• h est codé 01101000
• a est codé 01100001
• o est codé 01101111
• <espace> est codé 00100000

Le code obtenu serait donc 01101000 01100001 00100000 01101000 01100001 00100000 01101000 01101111 00100000 01101000 01101111 – les espaces servent à la lisibilité et ne seraient pas présent dans le fichier réel. Ce code comporte n x 8 = 88 bits.

Mais le codage iso-8859-1 permet de coder tout l'alphabet et plus encore, alors que notre texte n'utilise que quelques caractères différents. On pourrait décider d'un codage plus court. Il y a 4 caractères différents, $2^1 < 4 \leqslant 2^2$, il faut donc au minimum nb = 2 bits par caractères :

• <espace> serait codé 00
• h serait codé 01
• a serait codé 10
• o serait codé 11

Ainsi on obtiendrait le codage 01 10 00 01 10 00 01 11 00 01 11, qui comporte n x nb = 11 x 2 = 22 bits.

C'est beaucoup mieux mais c'est un peu illusoire : ce code, nous venons de l'inventer pour l'occasion. Il n'existe nulle part ailleurs. Personne ne le connaît. Donc je suis obligé d'indiquer dans le fichier une traduction de ce code, par exemple en indiquant la correspondance entre ce code et le code iso :

• 00 → 00100000
• 01 → 01101000
• 10 → 01100001
• 11 → 01101111

En supposant que je puisse donner cette traduction tout d'un bloc, sans espace ou quoique ce soit d'autre, il me faudra au minimum 4 x (2 + 8) = 40 bits.

L'ensemble de mon fichiers ferait alors 40 + 22 = 62 bits. C'est mieux que les 88 bits de départ avec iso.

Prenons un texte plus long dans lequel j'ai ôté les accents et les majuscules pour simplifier. Ce texte comporte des retours à la ligne qu'il faut compter également.

renard_et_corbeau.txt

maitre corbeau, sur un arbre perche,
tenait en son bec un fromage.
maitre renard, par l'odeur alleche,
lui tint a peu pres ce langage :
He ! bonjour, monsieur du corbeau.
que vous etes joli ! que vous me semblez beau !
sans mentir, si votre ramage
se rapporte a votre plumage,
vous etes le phenix des hotes de ces bois.
a ces mots, le corbeau ne se sent pas de joie ;
et pour montrer sa belle voix,
il ouvre un large bec, laisse tomber sa proie.
le renard s'en saisit, et dit : mon bon monsieur,
apprenez que tout flatteur
vit aux depens de celui qui l'ecoute.
cette lecon vaut bien un fromage, sans doute.
le corbeau honteux et confus
jura, mais un peu tard, qu'on ne l'y prendrait plus.

Vous devez refaire le travail précédent :

La méthode décrite précédemment consistait à créer un code ne contenant que les symboles utiles. Le code de Huffman reprend cette idée en allant un peu plus loin : Le code de Huffman tient de plus compte de la fréquence des lettres.

L'idée est d'utiliser un codage dont la taille varie. On utilise un code court pour les caractères fréquents et un code long pour un caractère rare. On comprend qu'en ayant souvent un code court et rarement un code long, le code total a de bonnes chances d'être plus court.

Mais la longueur variable du code des caractères entraîne des complications. C'est ce que nous allons voir.

Soit le texte hahahaha oh. Il comporte 4 caractères différents et 11 caractères en tout. Si on adopte la méthode précédente, il me faudra 40 bits pour la traduction vers iso et 22 pour le texte soit 62 bits en tout.

Huffman propose d'utiliser plutôt ce code :

• h serait codé 1 → 01101000 en iso
• a serait codé 00 → 01100001 en iso
• <espace> serait codé 010 → 00100000 en iso
• o serait codé 011 → 01101111 en iso

La partie traduction code → iso nécessite (1+8) pour h + (2+8) pour a + (3+8) pour espace + (3+8) pour o soit 41 bits. La partie texte nécessite 5 x 1 bits pour les h + 4 x 2 bits pour les espaces + 1 x 3 bits pour l'espace + 1 x 3 bits pour le o soit en tout 19 bits.

Avec le code de Huffman, il me faut donc 60 bits pour coder le texte entier. Le gain est faible car ce texte est très court.

Supposons que je veuille codé h par 0 et a par 00. Que devra-t-on comprendre si dans le fichier codé on voit la séquence 00 ?

• est-ce un h répété 2 fois ?
• est-ce un a ?

Le codage utilisé doit interdire une telle situation. Avec le code que j'ai proposé dans l'exemple précédent, une telle ambiguïté est impossible.

Par exemple, avec h = 1, a = 00, espace = 010 et o = 011, le code 1001001011 n'a qu'un sens possible. Vous pouvez vérifier !

Le code de Huffman nécessite donc une méthode pour permettre de construire un code à la fois efficace et sans ambiguïté.

Pour poursuivre, nous aurons besoin de connaître les statistiques du texte à coder. On peut envisager de compter manuellement pour un texte court mais mieux vaut prévoir une méthode de comptage automatique.

Supposons que dans un texte, on ait relevé les statistiques suivantes :

• Relever les éléments avec la fréquence la plus faible. Ici B et C.
• Construire un arbre avec ces deux éléments comme ci-dessous :

Nous obtenons ainsi un nouveau tableau :

• Les deux éléments les moins fréquents sont maintenant 1 et D
• Construire un arbre avec ces deux éléments

Nous obtenons ainsi un nouveau tableau :

• Les deux éléments les moins fréquents sont les blocs AD et BC
• Construire un arbre avec ces deux éléments

Nous obtenons ainsi un nouveau tableau :

Il ne reste qu'à les assembler :

L'arbre étant donné, on déduit le codage. Ici,

• E sera codé 0
• A sera codé 100
• D sera codé 101
• B sera codé 110
• C sera codé 111

C'est un code de Huffman.

Dans cet exemple, ABCD sont codés sur 3 bits tandis que E sur un seul. Si on fait le compte, avec 30 A, 22 B, 10 C, 25 D et 100 E, on aura besoin de 361 bits pour le texte. Pour indiquer la traduction → iso, il faudra encore 1 + 8 bits pour le E et 3 + 8 bits pour A, B, C, D soit 53 bits de traduction et donc en tout 414 bits. Il en aurait fallu (30 + 22 + 10 + 25 + 100) x 8 = 1496 avec un codage iso soit un taux de compression de $\frac{414}{1496} \simeq 28\,\%$.

Nous avons déjà une fonction pour relever les statistiques d'un texte.

Ajoutez les fonctions pour :

• construire l'arbre de Huffman à partir du dictionnaire de statistiques,
• construire un dictionnaire donnant pour chaque caractère du texte son code selon l'arbre de Huffman obtenu,
• évaluer le nombre de bits du fichier obtenu avec le code de huffman et une approximation du taux de compression par rapport au même texte codé en iso.