huffman.py

from heapq import heappush, heapify, heappop

#Question1


def table_frequences(texte):
    table={}
    for i in texte:
        if i in table:
            table[i]=table[i]+1
        else:
            table[i]=1
    return table

#question2
class OccuLettre(tuple):
    def __lt__(self, other):
        return self[0] < other[0]
    def __eq__(self, other):
        return self[0] == other[0]

def arbre_huff(occurrences):
    #construction d'un tas
    tas=[OccuLettre((occ, lettre)) for (lettre, occ) in occurrences.items()]
    heapify(tas) #trier le tas

    while len(tas)>=2:
        occ1, noeud1 = heappop(tas) #noeud de + petit poids occ1
        occ2, noeud2 = heappop(tas) #noeud de 2ème + petit poids
        heappush(tas, OccuLettre((occ1+occ2,{0: noeud1, 1: noeud2})))  #ajoute au tas le noeud de poids occ1+occ2
    return heappop(tas)[1]

def affiche_encodage(texte):
    table = table_frequences(texte)
    arbre = arbre_huff(table)
    res = []
    def print_arbre(a, path=""):
        for k,v in a.items():
            pathv = path + str(k)
            if isinstance(v, dict):
                print_arbre(v, pathv)
            else:
                res.append((pathv, v))
    print_arbre(arbre)
    res.sort()
    return res
        
texte = input("Texte? ")
print(affiche_encodage(texte))