Algorithme du codage de Huffman

Algorithme du codage de Huffman - Python - Programmation

Marsh Posté le 21-03-2019 à 20:23:15    

Bonjour,
 
Je suis en train de créer une fonction qui construit l'arbre de Huffman sur Python:  
 

Code :
  1. def arbre_huffman(occurrences): #occurences correspond au dictionnaire de fréquences de chaque caractère
  2.     # Construction d'un tas avec les lettres sous forme de feuilles
  3.     tas = [(occ, lettre) for (lettre, occ) in occurrences.items()]
  4.     heapq.heapify(tas)
  5.     # Création de l'arbre
  6.     while len(tas) >= 2:
  7.         occ1, noeud1 = heapq.heappop(tas) # noeud de plus petit poids occ1
  8.         occ2, noeud2 = heapq.heappop(tas) # noeud de deuxième plus petit poids occ2
  9.         heapq.heappush(tas, (occ1 + occ2, {0: noeud1, 1: noeud2}))
  10.         # ajoute au tas le noeud de poids occ1+occ2 et avec les fils noeud1 et noeud2
  11.     return heapq.heappop(tas)[1]


 
Mais je reçois le message d'erreur : '<' not supported between instances of 'dict' and 'str'  
 
Je crois que c'est parce que le tas se trie en comparant les membres de droite (de type str et de type dict) des couples alors que je souhaiterais qu'il se trie en comparant le membre de gauche des couples considérés (entiers)
 
Par exemple pour le mot abracadabra, j'ai un dictionnaire de cette forme :
 

Code :
  1. {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}


Puis mon tas initial est :

Code :
  1. [(1, 'c'), (1, 'd'), (2, 'r'), (2, 'b'), (5, 'a')]


 
Avez vous des suggestions ?
 
Merci d'avance

Reply

Marsh Posté le 21-03-2019 à 20:23:15   

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed