Cette séance a pour objet l’étude d’une méthode de compression de données inventée par David Albert Huffman en 1952. Cette méthode permet de réduire la longueur du codage d’un alphabet et repose sur la création d’un arbre binaire.
Différents types de codages
Info
On appelle alphabet l’ensemble des symboles (caractères) composant la donnée de départ à compresser.
Dans la suite, nous utiliserons un alphabet composé seulement des 8 lettres A, B, C, D, E, F, G et H.
On cherche à coder chaque lettre de cet alphabet par une séquence de chiffres binaires.
Combien de bits sont nécessaires pour coder chacune des 8 lettres de l’alphabet ?
Réponse
Il faut coder 8 caractères, on a donc besoin de 3 bits, puisque 23=8.
Quelle est la longueur en octets d’un message de 1 000 caractères construit sur cet alphabet ?
Réponse
1000×3=3000 bits sont nécessaires.
83000=375 octets sont nécessaires.
Proposer un code de taille fixe pour chaque caractère de l’alphabet de 8 lettres.
Réponse
A : 000 ; B : 001 ; C : 010 ; D : 011 ; E : 100 ; F : 101 ; G : 110 et H : 111.
On considère maintenant le codage suivant, la longueur du code de chaque caractère étant variable.
Lettre
A
B
C
D
E
F
G
H
Code
10
001
000
1100
01
1101
1110
1111
Info
Ce type de code est dit préfixe, ce qui signifie qu’aucun code n’est le préfixe d’un autre (le code de A est 10 et aucun autre code ne commence par 10, le code de B est 001 et aucun autre code ne commence par 001). Cette propriété permet de séparer les caractères de manière non ambiguë.
En utilisant la table précédente, donner le code du message : CACHE.
Réponse
CACHE : 00010000111101
Quel est le message correspondant au code 001101100111001.
Réponse
001101100111001 : BADGE
Dans un texte, chacun des 8 caractères a un nombre d’apparitions différent. Cela est résumé dans le tableau suivant, construit à partir d’un texte de 1 000 caractères.
Lettre
A
B
C
D
E
F
G
H
Nombre
240
140
160
51
280
49
45
35
En utilisant le code de taille fixe proposé à la question 3., quelle est la longueur en bits du message contenant les 1 000 caractères énumérés dans le tableau précédent ?
Réponse
Si on utilise 3 bits pour chaque caractère, il faut 1000×3=3000 bits pour coder le message.
En utilisant le code de la question 4., quelle est la longueur du même message en bits ?
Réponse
N=f(A)⋅l(A)+f(B)⋅l(B)+f(C)⋅l(C)+f(D)⋅l(D)+f(E)⋅l(E)+f(F)⋅l(F)+f(G)⋅l(G)+f(H)⋅l(H) où f(xi) est la fréquence du caractère xi et l(xi) la longueur (en bits) du codage du caractère xi.
A.N.N=240×2+140×3+160×3+51×4+280×2+49×4+45×4+35×4=2660
Info
Ce type de codage réserve le codage le plus court aux caractères les plus fréquents.
Codage de Huffman
L’objectif du codage de Huffman est de trouver le codage proposé à la question 4.
Info
Le codage de Huffman minimise la taille en nombre de bits du message codé en se basant sur le nombre d’apparition de chaque caractère (un caractère qui apparaît souvent aura un code plutôt court).
Pour déterminer le code optimal, on considère 8 arbres, chacun réduit à une racine, contenant le symbole et son nombre d’apparitions.
On fusionne ensuite les deux arbres contenant les plus petits nombres d’apparitions (valeur inscrite sur la racine), et on affecte à ce nouvel arbre la somme des nombres d’apparitions de ses deux sous-arbres. Lors de la fusion des deux arbres, le choix de mettre l’un ou l’autre à gauche n’a pas d’importance. Nous choisissons ici de mettre le plus fréquent à gauche (s’il y a un cas d’égalité, nous faisons un choix arbitraire).
On recommence jusqu’à ce qu’il n’y ait plus qu’un seul arbre.
Combien d’étapes (combien de fusions d’arbres) sont nécessaires pour que cet algorithme se termine ?
En suivant l’algorithme précédent, construire l’arbre de Huffman.
Info
Le code à affecter à chaque lettre est déterminé par sa position dans l’arbre. Précisément, le code d’un symbole de l’alphabet décrit le chemin de la racine à la feuille qui le contient : un 0 indique qu’on descend par le fils gauche et un 1 indique qu’on descend par le fils droit.
graph TD
A(" ") --> B(" ")
B --> X("X")
B --> Y("Y")
A --> Z("Z")
Dans le cas de l’arbre ci-dessus le code de X est 00 (deux fois à gauche), le code de Y est 01, et celui de Z est 1.
Sur chaque arête de l’arbre construit à la question 10., inscrire 0 ou 1 selon que l’arête joint un fils gauche ou un fils droit.
Quel est le code de F ?
Le code suivant permet, à partir d’un fichier nommé texte.txt, de construire l’arbre de Huffman puis un dictionnaire qui associe à chaque caractère du fichier d’entrée son code sous forme d’une séquence de bits (liste de 0 et de 1).
Implémentation en Python de l’algorithme
Écrire le code (et la spécification !) de la classe Noeud, nœud d’un arbre binaire.
Par rapport à l’implémentation réalisée lors des TP précédenrs, ajouter le champ lettre initialisé à la chaîne de caractères vide et la méthode suivante :
def__lt__(self,n:Noeud):"""
Comparaison de deux noeuds = comparaison des valeurs
"""returnself.valeur<n.valeur
Réponse
classNoeud:def__init__(self:Noeud,val:int,let:str="")->None:"""
Initialisation de l'objet.
"""self.valeur=valself.lettre=letself.gauche=Noneself.droit=Nonedef__lt__(self:Noeud,n:Noeud)->bool:"""
Comparaison de deux noeuds = comparaison des valeurs
"""returnself.valeur<n.valeur
Écrire les codes (et la spécification !) des fonctions est_vide, est_feuille, parcours_prefixe qui, respectivement teste si un nœud est vide, teste si un nœud est une feuille et finalement affiche l’arbre.
Réponse
defest_vide(n:Noeud)->bool:"""
Détermine si l'arbre est vide.
"""returnnisNonedefest_feuille(n:Noeud)->bool:"""
Détermine si le noeud est une feuille.
"""return(n.gaucheisNone)and(n.droitisNone)defparcours(n:Noeud)->str:"""
Parcours en profondeur préfixe de l'arbre.
"""ifnisNone:return""else:chaine=str(n.valeur)chaine+=parcours(n.gauche)chaine+=parcours(n.droit)returnchaine
15. Écrire le code de la fonction creation_table_frequences dont la spécification est
defcreation_table_frequences(message:str)->dict[str,int]:"""
Établit la table des fréquences des caractères dans message.
"""
defcreation_table_frequences(message:str)->dict[str,int]:"""
Établit la table des fréquences des caractères dans message.
"""dic={}forcarinmessage:ifcarindic.keys():dic[car]+=1else:dic[car]=1returndic
Lire le document sur les files de priorité.
Écrire le code de la fonction construction_arbre_huffman dont la spécification est
defconstruction_arbre_huffman(dic_frequences:dict[str,int])->Noeud:"""
Construction de l'arbre de Huffman.
"""
et l’algorithme (cf. Cormen, Algorithmes)
Avertissement
Cet algorithme est un exemple d’algorithme glouton dans lequel on prend la décision qui semble la meilleure à un instant donné.
Réponse
defconstruction_arbre_huffman(dic_frequences:dict[str,int])->Noeud:"""
Construction de l'arbre de Huffman.
"""file=[]# Création de tous les noeuds et insertion dans la fileforlettre,frequenceindic_frequences.items():noeud=Noeud(frequence,lettre)heappush(file,noeud)# Construction de l'arbreforiinrange(len(dic_frequences)-1):noeud_droit=heappop(file)noeud_gauche=heappop(file)# Nouvel arbrenouvelle_valeur=noeud_droit.valeur+noeud_gauche.valeurnoeud=Noeud(nouvelle_valeur)noeud.droit=noeud_droitnoeud.gauche=noeud_gauche# Intégration à la fileheappush(file,noeud)# Retour de l'arbrereturnheappop(file)
Écrire une fonction nommée codes_huffman_parcours dont la spécification est :
defcodes_huffman_parcours(a:Noeud,dic:dict[str,str],code:str)->None:"""
Parcours de l'arbre et construction des codes et du dictionnaire passé en argument.
Les lettres constituent les clés et les codes les valeurs.
Algorithme récursif.
"""
Réponse
defcodes_huffman_parcours(a:Noeud,dic:dict[str,str],code:str)->None:"""
Parcours de l'arbre et construction des codes et du dictionnaire passé en argument.
Les lettres constituent les clés et les codes les valeurs.
Algorithme récursif.
"""ifest_feuille(a):# Cas de base : on modifie le dictionnairedic[a.lettre]=codereturnNoneelse:codes_huffman_parcours(a.gauche,dic,code+"0")codes_huffman_parcours(a.droit,dic,code+"1")
Écrire une fonction nommée encodage dont la spécification est :
defencodage(message:str,codes:dict[str,str])->str:"""
Retourne la chaîne de bits produite par le codage de Huffman pour la chaîne message.
"""
Réponse
defencodage(message:str,codes:dict[str,str])->str:"""
Retourne la chaîne de bits produite par le codage de Huffman pour la chaîne message.
"""message_code=""forcarinmessage:message_code+=codes[car]returnmessage_code
Avertissement
Il est impératif de savoir écrire le code de cette fonction !
Écrire une fonction nommée decodage dont la spécification est :
defdecodage(message_compresse:str,codes:dict[str,str])->str:"""
Retourne le message non compressé à partir du codage de Huffman.
"""
Réponse
defdecodage(message_compresse:str,codes:dict[str,str])->str:"""
Retourne le message non compressé à partir du codage de Huffman.
Étape intermédiaire : passer d'un dictionnaire 'A': '001' à
'001' : 'A'
"""# Inversion clés - valeursdic_inverse={}forcle,valeurincodes.items():dic_inverse[valeur]=cle# Décodageresultat=""code=""forcarinmessage_compresse:code+=carifcodeindic_inverse.keys():resultat+=dic_inverse[code]code=""returnresultat
Avertissement
Il est impératif de savoir écrire le code de cette fonction !
Appels de toutes les fonctions dans la partie principale du programme
if__name__=="__main__":arb=Noeud(12,"A")arb.gauche=Noeud(23,"B")arb.droit=Noeud(48,"C")arb.gauche.gauche=Noeud(49,"K")arb.droit.gauche=Noeud(9,"H")arb.droit.droit=Noeud(78,"X")print(parcours(arb))print(arb<Noeud(67,"E"))assertcreation_table_frequences("ABRACADABRA")=={"A":5,"B":2,"R":2,"C":1,"D":1,}message="ABRACADABRA"# nom_fichier = "livre.txt"# with open(nom_fichier, 'r') as f:# message = f.read()table_frequences=creation_table_frequences(message)arbre=construction_arbre_huffman(table_frequences)print(parcours(arbre))dic_codes={}codes_huffman_parcours(arbre,dic_codes,"")print(dic_codes)message_code=encodage(message,dic_codes)print(message_code)message_decode=decodage(message_code,dic_codes)print(message_decode)