Aller au contenu principal

Codage de Huffman

#Codage de Huffman

Le codage de Huffman est un algorithme de compression de données sans perte qui utilise un dictionnaire à longueur variable basé sur la fréquence d'apparition des caractères. Il a été développé par David Huffman en 1952 et reste l'un des algorithmes de compression les plus importants en informatique.

#Principe

L'idée fondamentale du codage de Huffman est d'attribuer des codes plus courts aux caractères les plus fréquents et des codes plus longs aux caractères les moins fréquents. Cela contraste avec les systèmes de codage à longueur fixe comme l'ASCII où chaque caractère utilise le même nombre de bits.

#Animation interactive

Voici une animation qui illustre le fonctionnement de l'algorithme de Huffman :

Chargement...

#Algorithme

  1. Calcul des fréquences : Compter l'occurrence de chaque caractère dans le texte
  2. Construction de l'arbre :
    • Créer un nœud feuille pour chaque caractère avec sa fréquence
    • Répéter jusqu'à ce qu'il ne reste qu'un seul nœud :
      • Sélectionner les deux nœuds avec les fréquences les plus basses
      • Créer un nouveau nœud avec ces deux nœuds comme enfants
      • La fréquence du nouveau nœud est la somme des fréquences des enfants
      • Ajouter le nouveau nœud à la liste
  3. Génération des codes : Parcourir l'arbre pour attribuer des codes binaires (0 pour gauche, 1 pour droite)

#Implémentation en Python

pythonpython
1import heapq2from collections import defaultdict, Counter3 4class NoeudHuffman:5    def __init__(self, char=None, freq=0, gauche=None, droite=None):6        self.char = char7        self.freq = freq8        self.gauche = gauche9        self.droite = droite10    11    def __lt__(self, other):12        return self.freq < other.freq13 14def construire_arbre_huffman(texte):

#Propriétés

#Optimalité

Le codage de Huffman est optimal pour un modèle de source sans mémoire (chaque caractère est indépendant des autres). Cela signifie qu'il produit le code à longueur variable avec la plus petite longueur moyenne possible.

#Préfixe

Le codage de Huffman est un code préfixe, ce qui signifie qu'aucun code n'est le préfixe d'un autre code. Cette propriété permet une décompression non ambiguë.

#Complexité

  • Construction de l'arbre : O(n log n) où n est le nombre de caractères distincts
  • Génération des codes : O(n)
  • Compression : O(m) où m est la longueur du texte
  • Décompression : O(m)

#Exercice : Implémentation avec sérialisation

Implémentez une version du codage de Huffman qui peut sérialiser l'arbre dans le flux compressé pour une décompression autonome.

#Instructions

  1. Créez une fonction pour sérialiser l'arbre de Huffman
  2. Modifiez l'algorithme pour inclure l'arbre dans le flux compressé
  3. Implémentez la décompression qui utilise l'arbre du flux

#Exemple de code

pythonpython
1def serialiser_arbre(noeud):2    """Sérialiser l'arbre de Huffman en une chaîne binaire"""3    if noeud.char is not None:4        # Nœud feuille : '1' + code ASCII sur 8 bits5        return '1' + format(ord(noeud.char), '08b')6    else:7        # Nœud interne : '0' + sous-arbre gauche + sous-arbre droit8        return '0' + serialiser_arbre(noeud.gauche) + serialiser_arbre(noeud.droite)9 10def deserialiser_arbre(bits, index=0):11    """Désérialiser l'arbre de Huffman à partir d'une chaîne binaire"""12    if bits[index] == '1':13        # Nœud feuille14        char_code = bits[index+1:index+9]

#Applications

  1. Compression de fichiers : Formats comme ZIP, PNG, JPEG utilisent Huffman dans leur processus
  2. Transmission de données : Réduction de la bande passante nécessaire
  3. Stockage : Réduction de l'espace de stockage requis
  4. Multimédia : Compression audio (MP3) et vidéo (MPEG)

Le codage de Huffman est un excellent exemple d'application des structures de données arborescentes et de l'optimisation combinatoire en informatique.