Le codage d'Huffman

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Noeud:
    def __init__(self: Noeud, val: int, let: str = "") -> None:
        """
        Initialisation de l'objet.
        """
        self.valeur = val
        self.lettre = let
        self.gauche = None
        self.droit = None

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def est_vide(n: Noeud) -> bool:
    """
    Détermine si l'arbre est vide.
    """
    return n is None


def est_feuille(n: Noeud) -> bool:
    """
    Détermine si le noeud est une feuille.
    """
    return (n.gauche is None) and (n.droit is None)


def parcours(n: Noeud) -> str:
    """
    Parcours en profondeur préfixe de l'arbre.
    """
    if n is None:
        return ""
    else:
        chaine = str(n.valeur)
        chaine += parcours(n.gauche)
        chaine += parcours(n.droit)
        return chaine

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def creation_table_frequences(message: str) -> dict[str, int]:
    """
    Établit la table des fréquences des caractères dans message.
    """
    dic = {}
    for car in message:
        if car in dic.keys():
            dic[car] += 1
        else:
            dic[car] = 1
    return dic

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def construction_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 file
    for lettre, frequence in dic_frequences.items():
        noeud = Noeud(frequence, lettre)
        heappush(file, noeud)

    # Construction de l'arbre
    for i in range(len(dic_frequences) - 1):
        noeud_droit = heappop(file)
        noeud_gauche = heappop(file)
        # Nouvel arbre
        nouvelle_valeur = noeud_droit.valeur + noeud_gauche.valeur
        noeud = Noeud(nouvelle_valeur)
        noeud.droit = noeud_droit
        noeud.gauche = noeud_gauche
        # Intégration à la file
        heappush(file, noeud)

    # Retour de l'arbre
    return heappop(file)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

    Algorithme récursif.
    """
    if est_feuille(a):
        # Cas de base : on modifie le dictionnaire
        dic[a.lettre] = code
        return None
    else:
        codes_huffman_parcours(a.gauche, dic, code + "0")
        codes_huffman_parcours(a.droit, dic, code + "1")

1
2
3
4
5
6
7
8

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.
    """
    message_code = ""
    for car in message:
        message_code += codes[car]
    return message_code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def decodage(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 - valeurs
    dic_inverse = {}
    for cle, valeur in codes.items():
        dic_inverse[valeur] = cle

    # Décodage
    resultat = ""
    code = ""
    for car in message_compresse:
        code += car
        if code in dic_inverse.keys():
            resultat += dic_inverse[code]
            code = ""
    return resultat