Codage de Huffman (encodage du texte)
Présentation rapide
Le codage de Huffman est un codage qui permet de compresser des données. Dans le cas d'un texte, codé en UTF-8, chaque caractère prendra la place de un à 4 octets. Dans le cas du codage de Huffman , plus un caractère est fréquent dans le texte, plus court sera son codage en binaire.
Exemple
Le texte : que voulez vous que je vous dise sera codé par :
01111011101110000011011000011010001111000001101010111011110111011110010110111000001101010111100110110010110.
Soit \(107\) bits au lieu de \(256\) avec le codage UTF-8. Le caractère espace ' ' sera codé par 111, tandis que le caractère 'l' sera codé par 1 0000.
Les étapes sur un exemple
Prenons pour exemple le texte que voulez vous que je vous dise.
Le nombre d'occurrences de chaque lettre est :
| q | u | e | v | o | l | z | s | j | d | i | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 5 | 5 | 6 | 3 | 3 | 1 | 1 | 3 | 1 | 1 | 1 |
L'arbre de Huffman est un arbre construit progressivement à partir des feuilles.
On commence par créer des nœuds pour tous les caractères. La donnée associée à chaque nœud est un caractère et son poids qui est son nombre d'occurrences.
graph TD
N7(l:1):::feuille
N8(z:1):::feuille
N90(j:1):::feuille
N10(d:1):::feuille
N1(i:1):::feuille
N11(q:2):::feuille
N5(v:3):::feuille
N6(o:3):::feuille
N9(s:3):::feuille
N2(u:5):::feuille
N3(e:5):::feuille
N4(_:6):::feuille
classDef feuille fill:#F88graph TD
N22(( :32)) --> N20(( :12))
N22 --> N21(( :20))
N20 --> N16(( :6))
N20 --> N17(( :6))
N16 --> N5(v:3):::feuille
N16 --> N6(o:3):::feuille
N17 --> N9(s:3):::feuille
N17 --> N14(( :3))
N14 --> N1(i:1):::feuille
N14 --> N11(q:2):::feuille
N21 --> N18(( :9))
N18 --> N15(( :4))
N18 --> N2(u:5):::feuille
N15 --> N12(( :2))
N15 --> N13(( :2))
N12 --> N7(l:1):::feuille
N12 --> N8(z:1):::feuille
N13 --> N90(j:1):::feuille
N13 --> N10(d:1):::feuille
N21 --> N19( :11)
N19 --> N3(e:5):::feuille
N19 --> N4(_:6):::feuille
classDef feuille fill:#F88
On pourra trouver plus d'explications dans l'exercice sur la construction d'un arbre de Huffman.
Encodage⚓︎
Une fois l'arbre construit, il faut procéder à l'encodage du texte. On va créer un dictionnaire, dont les clés seront les caractères et les valeurs associées, le codage binaire du caractère en utilisant l'arbre construit.
La convention utilisée ici sera la suivante :
Dans l'arbre chaque embranchement à gauche correspond à 0 et chaque embranchement à droite correspond à 1.
Exemple d'arbre et de codes
On obtient l'arbre suivant :
graph TD
N22(( :32)) --> |0| N20(( :12))
N22 --> |1| N21(( :20))
N20 --> |0| N16(( :6))
N20 --> |1| N17(( :6))
N16 --> |0| N5(v:3):::feuille
N16 --> |1| N6(o:3):::feuille
N17 --> |0| N9(s:3):::feuille
N17 --> |1| N14(( :3))
N14 --> |0| N1(i:1):::feuille
N14 --> |1| N11(q:2):::feuille
N21 --> |0| N18(( :9))
N21 --> |1| N19( :11)
N18 --> |0| N15(( :4))
N18 --> |1| N2(u:5):::feuille
N15 --> |0| N12(( :2))
N15 --> |1| N13(( :2))
N12 --> |0| N7(l:1):::feuille
N12 --> |1| N8(z:1):::feuille
N13 --> |0| N90(j:1):::feuille
N13 --> |1| N10(d:1):::feuille
N19 --> |0| N3(e:5):::feuille
N19 --> |1| N4(_:6):::feuille
classDef feuille fill:#F88Plus un symbole est fréquent, plus il est proche de la racine.
graph TD
N22(( :32)) --> |0| N20(( :12))
N22 --> |1| N21(( :20))
N20 --> |0| N16(( :6))
N20 --> |1| N17(( :6))
N16 --> |0| N5(v:3):::feuille
N16 --> |1| N6(o:3):::feuille
N17 --> |0| N9(s:3):::feuille
N17 --> |1| N14(( :3))
N14 --> |0| N1(i:1):::feuille
N14 --> |1| N11(q:2):::feuille
N21 --> |0| N18(( :9))
N21 --> |1| N19( :11)
N18 --> |0| N15(( :4))
N18 --> |1| N2(u:5):::feuille
N15 --> |0| N12(( :2))
N15 --> |1| N13(( :2))
N12 --> |0| N7(l:1):::feuille
N12 --> |1| N8(z:1):::feuille
N13 --> |0| N90(j:1):::feuille
N13 --> |1| N10(d:1):::feuille
N19 --> |0| N3(e:5):::feuille
N19 --> |1| N4(_:6):::feuille
N5 o-...-o N32[000]:::binaire
N1 o-..-o N33[0110]:::binaire
N4 o-...-o N30[111]:::binaire
N7 o-.-o N31[1 0000]:::binaire
classDef feuille fill:#F88
classDef binaire fill:#FF0Par exemple, l (peu fréquent) sera codé 1 0000 (5 bits) alors que l'espace (très fréquente) sera codée 111 (3 bits).
Note
Toutes les fonctions crées dans des questions, sont utilisables dans les questions suivantes.
Question 1 : lettre_binaire(arbre)
Principe : on parcourt récursivement l'arbre en profondeur. À chaque fois qu'on arrive sur un nœud,
- si c'est une feuille, on met à jour le dictionnaire de codage
- sinon on appelle récursivement le parcours en mettant à jour l'argument code en fonction du sous arbre gauche ou droit.
Compléter la fonction lettre_binaire qui prend comme paramètre un arbre de Huffman et qui renvoie un dictionnaire avec comme clé, les caractères et comme valeurs associées, le codage binaire du caractère.
Les étiquettes des nœuds de l'arbre sont des dictionnaire de la forme {"caractere":…, "poids":…}.
Question 2 : encode_texte_codage(texte, codage)
Il faut maintenant encoder le texte initial avec ce code obtenu.
Créer la fonction encode_texte_codage qui prend comme paramètre un texte et qui renvoie une chaîne de caractères contenant le codage binaire du texte.
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
Question 3 : encode_Huffman(texte)
Pour encoder un texte, en utilisant le codage de Huffman, il faut :
- créer l'arbre de Huffman à partir du texte. La fonction
arbre_Huffman(chaine)est intégré à l'IDE, - en déduire le dictionnaire de codage
- encoder le texte.
Compléter la fonction encode_Huffman(texte), qui prend en paramètre une chaine de caractères, et renvoie une chaine de caractère, représentant un codage de Huffman du paramètre.
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
Remarques
- Pour l'exercice le codage est « textualisé », alors que, dans la réalité, l'opération se passe au niveau des octets et est donc plus difficilement visible.
- En pratique, le dictionnaire de codage est transmis dans le fichier avec le texte à décoder.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)