Le codage d'Huffman

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

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.

1. Combien de bits sont nécessaires pour coder chacune des 8 lettres de l’alphabet ?

2. Quelle est la longueur en octets d’un message de 1 000 caractères construit sur cet alphabet ?

3. Proposer un code de taille fixe pour chaque caractère de l’alphabet de 8 lettres.

On considère maintenant le codage suivant, la longueur du code de chaque caractère étant variable.

4. En utilisant la table précédente, donner le code du message : CACHE.

5. Quel est le message correspondant au code 001101100111001.

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.

7. 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 ?

8. En utilisant le code de la question 4., quelle est la longueur du même message en bits ?

Codage de Huffman

L’objectif du codage de Huffman est de trouver le codage proposé à la question 4.

graph TD
    A("A | 240")
    B("B | 140")
    C("C | 160")
    D("D | 51")
    E("E | 280")
    F("F | 49")
    G("G | 45")
    H("H | 35")

graph TD
    A("A | 240")
    B("B | 140")
    C("C | 160")
    D("D | 51")
    E("E | 280")
    F("F | 49")
    I("80") --> G
    I("80") --> H
    G("G | 45")
    H("H | 35")

9. Combien d’étapes (combien de fusions d’arbres) sont nécessaires pour que cet algorithme se termine ?

10. En suivant l’algorithme précédent, construire l’arbre de Huffman.

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.

11. 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.

12. 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

13. É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 :

1
2
3
4
5

def __lt__(self, n: Noeud):
        """
        Comparaison de deux noeuds = comparaison des valeurs
        """
        return self.valeur < n.valeur

14. É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.

15. Écrire le code de la fonction creation_table_frequences dont la spécification est

1
2
3
4

def creation_table_frequences(message: str) -> Dict[str, int]:
    """
    Établit la table des fréquences des caractères dans message.
    """

Tester la fonction avec l’instruction :

1

assert creation_table_frequences("ABRACADABRA") == {'A': 5, 'B': 2, 'R': 2, 'C': 1, 'D': 1}

16. Lire le document sur les files de priorité Écrire le code de la fonction construction_arbre_huffman dont la spécification est

1
2
3
4

def construction_arbre_huffman(dic_frequences: Dict[str, int]) -> Noeud:
    """
    Construction de l'arbre de Huffman.
    """

et l’algorithme (cf. Cormen, Algorithmes)

17. Écrire une fonction nommée codes_huffman_parcours dont la spécification est :

1
2
3
4
5
6

def codes_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 valeurs et les codes les clés.

    Algorithme récursif.
    """

18. Écrire une fonction nommée encodage dont la spécification est :

1
2
3
4

def encodage(message: str, codes: Dict[str, str]) -> str:
    """
    Retourne la chaîne de bits produite par le codage de Huffman pour la chaîne message.
    """

19. Écrire une fonction nommée decodage dont la spécification est :

1
2
3
4

def decodage(message_compresse: str, codes: Dict[str, str]) -> str:
    """
    Retourne le message non compressé à partir du codage de Huffman. 
    """