Codage de Huffman (décodage à partir de l'arbre)
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.
Example
Le texte : que voulez vous que je vous dise
sera codé par :
01111011101110000011011000011010001111000001101010111011110111011110010110111000001101010111100110110010110.
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 |
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).
On obtient le dictionnaire de codage suivant :
{' ': '111', 'e': '110', 'u': '101', 'd': '10011', 'j': '10010', 'z': '10001', 'l': '10000', 'q': '0111', 'i': '0110', 's': '010', 'o': '001', 'v': '000'}
Le texte : «que voulez vous que je vous dise» est alors encodé par : 01111011101110000011011000011010001111000001101010111011110111011110010110111000001101010111100110110010110
On pourra trouver plus d'explications dans l'exercice sur la construction d'un arbre de Huffman.
Décodage⚓︎
Le décodage peut se faire, soit à partir du dictionnaire de codage, mais de façon plus efficace à partir de l'arbre lui-même.
Le codage de Huffman produit un code préfixe, c'est à dire que chaque code n'est pas le début d'un autre.
L'idée est de lire symbole par symbole le texte encodé et de parcourir l'arbre simultanément.
- On parcourt tout le texte encodé.
- Si le symbole est
0, alors on descend vers le sous arbre gauche. - Si le symbole est
1, alors on descend vers le sous arbre droit. - Si on arrive à une feuille, alors le code est terminé et correspond au caractère de la feuille. On ajoute ce caractère au texte décodé. On repart de la racine, pour le prochain caractère
Question 1 : decode_Huffman(texte, arbre)
Créer la fonction decode_Huffman qui prend comme argument un texte codé(chaine de caractère constituée de 0 et de 1) et l'arbre de Huffman, et qui renvoie une chaîne de caractères contenant le texte décodé.
Le décodage du texte se fait en parcourant l'arbre. On s'interdit d'utiliser et/ou de reconstruire le dictionnaire de codage.
Éléments fournis
-
Les étiquettes des nœuds de l'arbre sont des dictionnaire de la forme
{"caractere":…, "poids":…}. -
Une classe
Arbredont un exemple d'utilisation est donné ci-dessous.La classe
ArbreLa classe d'arbre proposée dispose de l'interface suivante :
Constructeur :
Arbre(donnee): renvoie un arbre d'étiquette donneeArbre(donnee, sous_arbre_gauche, sous_arbre_droit): renvoie un arbre d'étiquette donnee avec des sous arbres
Méthodes fournies :
- donnee() : renvoie l'étiquette de la racine
- sous_arbre_gauche() : renvoie le sous arbre droit
- sous_arbre_droit() : renvoie le sous arbre gauche
- est_feuille()
Exemple d'utilisation
🐍 Console Python>>> t1 = Arbre("b") >>> t2 = Arbre(1, t1, t1) >>> t2.donnee() 1 >>> t2.sous_arbre_gauche().est_feuille() True >>> t2.sous_arbre_droit().est_feuille() True >>> t2.est_feuille() False -
Pour vos tests, les fonctions :
arbre_Huffman(texte): renvoie un arbre de Huffman construit à partir du texte passé en paramètre.encode_Huffman(texte): renvoie le texte encodé avec le codage de Huffman. (Cette fonction utilise la fonction précédente pour générer l'arbre qu'elle utilise pour l'encodage)
Voir les tests pour un exemple d'utilisation
Remarque
En pratique, le dictionnaire de codage est transmis dans le fichier avec le texte à décoder. Il faut d'abord reconstruire l'arbre, avant de décoder les données.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)