DS MP - Codage de Huffman - Compression de données

Lorsqu'on enregistre des données — qu'il s'agisse d'un texte, d'une image ou de tout autre contenu — on stocke en réalité une suite de symboles (caractères, pixels, etc.). Traditionnellement, chaque symbole est représenté par un nombre fixe de bits : par exemple, en ASCII, un caractère occupe 8 bits (soit 1 octet).

Cependant, tous les symboles n'apparaissent pas avec la même fréquence :

Dans un texte français, la lettre 'e' est très courante, contrairement à la lettre 'z' qui est beaucoup plus rare.
Il devient alors intéressant d'attribuer aux symboles fréquents des codes binaires courts, et aux symboles rares des codes plus longs, ce qui permet de réduire la taille totale du fichier.

Objectif

Le codage de Huffman est un algorithme qui construit automatiquement un tel système de codage optimal, basé sur les fréquences d'apparition des symboles.

Principe général 1 question

Supposons que l'on souhaite compresser le texte suivant : "AAABBCC"

Les fréquences d'apparition des symboles sont :

A : 3
B : 2
C : 2

L'objectif est d'attribuer à chaque caractère un code binaire tout en respectant deux contraintes essentielles :

Aucun code ne doit être le préfixe d'un autre, afin de garantir un décodage sans ambiguïté.
La longueur moyenne des codes doit être la plus faible possible.

Une table de codage valide (et obtenue par l'algorithme de Huffman) peut être la suivante :

Symbole	Code	Longueur
A	0	1
B	10	2
C	11	2

Le texte compressé devient donc :

AAABBCC → 0 0 0 10 10 11 11 → 0001010111

La longueur totale est alors de 10 bits, au lieu de 7 × 8 = 56 dans un codage ASCII classique : un gain considérable !

Idée de Huffman

Le principe de l'algorithme repose sur une idée fondamentale : À chaque étape, on sélectionne les deux symboles (ou nœuds) de plus faible fréquence et on les fusionne en un nouveau nœud dont la fréquence est égale à la somme des deux.

Cette fusion progressive permet de construire un arbre dans lequel les symboles les plus fréquents se trouvent plus proches de la racine, et donc possèdent des codes binaires plus courts.

Construction de l'arbre de Huffman

1 - Intialisation

On crée un noeud feuille pour chaque symbole, contenant :

le symbole ('A'),
sa fréquence (par exemple 3).

2 - Combinaison

On choisit les deux noeuds ayant les plus petites fréquences, disons f1 et f2.
On crée un nouveau noeud parent de fréquence \textbf{f1 + f2}.
Les deux noeuds deviennent ses enfants (gauche, droite).
On insère ce noeud dans la liste des noeuds.

3 - Répétition

On recommence jusqu'à obtenir un seul noeud : la racine de l'arbre.

4 - Codage

En parcourant l'arbre :

chaque fois qu'on descend à gauche $\rightarrow$ ajouter un 0
chaque fois qu'on descend à droite $\rightarrow$ ajouter un 1.

Exemple

Prenons les fréquences suivantes :

Symbole	Fréquence
A	5
B	9
C	12
D	13
E	16
F	45

Étapes de construction

Etape 1

On commence par repérer les deux symboles de plus faible fréquence, ici A(5) et B(9). On les fusionne pour former un nouveau noeud interne AB dont la fréquence est la somme des deux : $$ 5+9 = 14$$ Les noeuds restants sont donc : C(12), D(13), E(16), F(45) et AB(14).

Etape 2

Parmi les fréquences restantes, les plus petites sont C(12) et D(13). On les fusionne pour créer le noeud CD de fréquence : $$ 12 + 13 = 25$$ Les noeuds restants deviennent : E(16), F(45), AB(14) et CD(25).

Etape 3

Les deux plus petites fréquences sont désormais AB(14) et E(16). On les fusionne pour former le noeud ABE de fréquence : $$14 + 16 = 30$$ Les noeuds restants sont : F(45), CD(25) et ABE(30).

Etape 4

On fusionne ensuite les deux plus petits noeuds restants : CD(25) et ABE(30). Cela donne un nouveau noeud CDABE de fréquence : $$25 + 30 = 55$$ Il reste alors : F(45) et ABECD(55).

Etape 5

Enfin, on fusionne les deux derniers noeuds : F(45) et CDABE(55). On obtient la racine de l'arbre de Huffman avec une fréquence totale : $$45 + 55 = 100$$

Résultat final

L'arbre complet de Huffman est maintenant construit. La racine représente la fréquence totale (100) et chaque feuille correspond à un symbole initial (A, B, C, D, E, F), relié par des chemins codant leur représentation binaire.

Écrire une fonction frequences(msg) qui, à partir d'une chaîne de caractères, calcule la fréquence de chaque symbole (retourne un dictionnaire {symbole: fréquence}).

Exemple

Calcul des fréquences

Entrée

texte = "LES ALGORITHMES GLOUTONS SONT EFFICACES"

Sortie

{'L': 3, 'E': 4, 'S': 5, ' ': 4, 'A': 2, 
'G': 2, 'O': 4, 'R': 1, 'I': 2, 'T': 3, 
'H': 1, 'M': 1, 'U': 1, 'N': 2, 'F': 2, 'C': 2}

Contraintes

La chaîne peut contenir des espaces et des caractères majuscules
Retourner un dictionnaire avec les caractères comme clés

Solution — Calcul des fréquences

def frequences(msg):
    freq = {}
    for caractere in msg:
        if caractere in freq:
            freq[caractere] += 1
        else:
            freq[caractere] = 1
    return freq

Test

>>> frequences("AAABBCC")
{'A': 3, 'B': 2, 'C': 2}

Complexité

Temps : O(n) — un seul parcours de la chaîne
Espace : O(k) — où k est le nombre de symboles distincts

Construction de l'arbre de Huffman 7 questions

Chaque nœud de l'arbre sera représenté sous la forme :
[(fréquence, symbole), sous_arbre_gauche, sous_arbre_droit]

Un nœud feuille est donc : [(fréquence, symbole), [], []]

Dans la suite, on utilise le tableau des fréquences suivant :

freqs = {
    'A': 5,
    'B': 9,
    'C': 12,
    'D': 13,
    'E': 16,
    'F': 45
}

Écrire une fonction creer_feuilles(freqs) qui prend en paramètre le dictionnaire des fréquences et retourne une liste de feuilles au format [(fréquence, symbole), [], []].

Exemple

Création des feuilles

Entrée

freqs = {'A':5, 'B':9, 'C':12, 'D':13, 'E':16, 'F':45}

Sortie

[
    [(5, 'A'), [], []], [(9, 'B'), [], []], 
    [(12, 'C'), [], []], [(13, 'D'), [], []], 
    [(16, 'E'), [], []], [(45, 'F'), [], []]
]

Solution — Création des feuilles

def creer_feuilles(freqs):
    feuilles = []
    for symbole, frequence in freqs.items():
        feuilles.append([(frequence, symbole), [], []])
    return feuilles

En utilisant une file de priorité (heapq en Python), écrire une fonction construire_arbre(L) qui prend en paramètre la liste des feuilles et construit l'arbre de Huffman selon la méthode gloutonne :

Trier la liste selon la fréquence croissante
Extraire les deux arbres de plus petite fréquence (arbre1 et arbre2)
Créer un nouveau nœud [(f1 + f2, sym1+symb2), arbre1, arbre2]
Réinsérer ce nœud dans la liste
Répéter jusqu'à obtenir un seul arbre (la racine)

Exemple

Construction de l'arbre

Structure attendue

[(100, 'FCDABE'),
    [(45, 'F'), [], []],
    [(55, 'CDABE'),
        [(25, 'CD'), 
            [(12, 'C'), [], []], 
            [(13, 'D'), [], []]],
        [(30, 'ABE'),
            [(14, 'AB'), 
                [(5, 'A'), [], []], 
                [(9, 'B'), [], []]],
            [(16, 'E'), [], []]
        ]
    ]
]

Solution — Construction de l'arbre

import heapq

def construire_arbre(feuilles):
    # Utilisation d'un heap pour toujours avoir les plus petites fréquences
    heapq.heapify(feuilles)
    
    while len(feuilles) > 1:
        # Extraire les deux arbres de plus petite fréquence
        arbre1 = heapq.heappop(feuilles)
        arbre2 = heapq.heappop(feuilles)
        
        freq1, sym1 = arbre1[0]
        freq2, sym2 = arbre2[0]
        
        # Créer un nouveau nœud fusionné
        nouveau = [(freq1 + freq2, sym1 + sym2), arbre1, arbre2]
        
        # Réinsérer dans le heap
        heapq.heappush(feuilles, nouveau)
    
    return feuilles[0]

Note

Pour que heapq fonctionne correctement, Python compare les listes. Il compare d'abord le premier élément (fréquence, symbole), ce qui correspond à notre besoin de trier par fréquence.

Écrire une fonction récursive generer_codes(arbre, prefixe="", codes=None) qui parcourt récursivement l'arbre de Huffman et construit le dictionnaire des codes binaires :

ajouter "0" pour aller à gauche
ajouter "1" pour aller à droite

Exemple

Génération des codes

Sortie

{
    'F': '0', 
    'C': '100', 
    'D': '101', 
    'A': '1100', 
    'B': '1101', 
    'E': '111'
}

Solution — Génération des codes

def generer_codes(arbre, prefixe="", codes=None):
    if codes is None:
        codes = {}
    
    # Récupérer les informations du nœud
    (freq, symbole), gauche, droite = arbre
    
    # Si c'est une feuille (pas d'enfants)
    if not gauche and not droite:
        # Cas particulier: s'il n'y a qu'un seul symbole
        if prefixe == "":
            codes[symbole] = "0"
        else:
            codes[symbole] = prefixe
    else:
        # Parcours récursif
        if gauche:
            generer_codes(gauche, prefixe + "0", codes)
        if droite:
            generer_codes(droite, prefixe + "1", codes)
    
    return codes

Écrire une fonction encoder(texte, codes) qui remplace chaque caractère du texte par son code binaire correspondant.

Exemple

Encodage

Entrée

texte = "CBCFFFFCEFCFDFFEDFFFCBFEFBFEDFCFEFFCDEBFDEFEDEFFFACDBFEFFFBFDBDCEACAFEEDEFFDDFFFAFFCFFFDFFABFFBEEFFC"

Sortie

'1001101100000010011101000101001111010001001101011101101011110101000111001001011111010101111011110111100011001001011101011100011010101110110110011111001001100011111110111100101101000110000100000101001100110100110111111100100'

Solution — Encodage

def encoder(texte, codes):
    resultat = ""
    for caractere in texte:
        resultat += codes[caractere]
    return resultat

Écrire une fonction decoder(chaine, arbre) qui parcourt l'arbre à partir de la racine et décode la chaîne binaire en texte clair :

si le bit = 0 → aller à gauche
si le bit = 1 → aller à droite
quand on atteint une feuille, ajouter le symbole au texte et repartir de la racine

Exemple

Décodage

Sortie

"CBCFFFFCEFCFDFFEDFFFCBFEFBFEDFCFEFFCDEBFDEFEDEFFFACDBFEFFFBFDBDCEACAFEEDEFFDDFFFAFFCFFFDFFABFFBEEFFC"

Solution — Décodage

def decoder(chaine, arbre):
    resultat = ""
    noeud_courant = arbre
    
    for bit in chaine:
        if bit == "0":
            noeud_courant = noeud_courant[1]  # aller à gauche
        else:  # bit == "1"
            noeud_courant = noeud_courant[2]  # aller à droite
        
        # Si c'est une feuille
        if not noeud_courant[1] and not noeud_courant[2]:
            freq, symbole = noeud_courant[0]
            resultat += symbole
            noeud_courant = arbre  # retour à la racine
    
    return resultat

Écrire une fonction taux_compression(texte, code_binaire) qui calcule le taux de compression en comparant :

la taille initiale (8 bits par caractère)
la taille compressée (longueur du code binaire)

$$\text{Taux} = \frac{\text{Taille compressée}}{\text{Taille originale}}$$

Exemple

Calcul du taux

Sortie

Taille originale : 800 bits
Taille compressée : 224 bits
Taux de compression : 0.2800  (gain 72.00%)

Solution — Taux de compression

def taux_compression(texte, code_binaire):
    taille_originale = len(texte) * 8
    taille_compressee = len(code_binaire)
    taux = taille_compressee / taille_originale
    gain = (1 - taux) * 100
    
    print(f"Taille originale : {taille_originale} bits")
    print(f"Taille compressée : {taille_compressee} bits")
    print(f"Taux de compression : {taux:.4f}  (gain {gain:.2f}%)")
    
    return taux

Écrire une fonction est_prefixe_libre(codes), où codes est un dictionnaire {symbole : code}. La fonction retourne True si aucun code n'est préfixe d'un autre, False sinon.

Exemple 1

Codes valides

Entrée

codes = {'A': '0', 'B': '10', 'C': '11'}

Sortie

True

Exemple 2

Codes non valides ('0' est préfixe de '01')

Entrée

codes = {'A': '0', 'B': '01', 'C': '11'}

Sortie

False

Solution — Vérification des préfixes

def est_prefixe_libre(codes):
    liste_codes = list(codes.values())
    
    for i in range(len(liste_codes)):
        for j in range(len(liste_codes)):
            if i != j:
                # Vérifier si liste_codes[i] est préfixe de liste_codes[j]
                if liste_codes[j].startswith(liste_codes[i]):
                    return False
    
    return True

Note

Cette propriété de préfixe libre (ou code préfixe) est essentielle pour garantir un décodage unique et sans ambiguïté. L'algorithme de Huffman garantit toujours cette propriété grâce à la structure d'arbre binaire.

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Discussion (0)

Soyez le premier à laisser un commentaire !

Laisser un commentaire

Votre commentaire sera visible après modération.

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

DS MP - Codage de Huffman - Compression de données

Codage de Huffman - Compression de données

Construction de l'arbre de Huffman

Étapes de construction

Discussion (0)

Laisser un commentaire