Je m'intéresse au codage de Huffman. Je voudrais l'implémenter sur python mais j'ai beaucoup de mal à créer l'arbre.
J'aimerais le créer à partir de listes.
Avez-vous des conseils ?
J'ai fait une fonction permettant de déterminer les fréquences d'apparition de chaque lettre, mais je bloque pour faire une fonction qui crée l'arbre de Huffman.
Vous avez des pistes?
Voilà ce que j'ai fait : j'ai utilisé la programmation objet.
class Arbre(): def __init__ (self,donnee,gauche=None,droit=None): self.donnee = donnee self.gauche = gauche self.droit = droit def __repr__ (self): return("Arbre de noeud {} de fils gauche {} et de fils droit {}".format(self.donnee,self.gauche,self.droit))
Puis j'ai créé la fonction qui crée l'arbre de Huffman :
def arbrehuff(liste): #la liste correspond au dictionnaire classé par ordre croissant de fréquences l=liste m=[] h=[]
for k in range(0,len(l)): if l[k][1]!=0: m.append (l[k][0]) h.append (l[k][1]) #m est la liste des caractères dans l'ordre de trifusion #h est la liste des fréquences associées #h contient les fréquences, on va faire changer h à chaque étape i=0 #transformer h en liste d'arbres h1=[] for i in range (0,len(h)): h1.append(Arbre(h[i])) h=h1 g=[] nbdetapes= nombreetapes(len(h)) while i<nbdetapes: if len(h)%2==0: for i in range (0,len(h)-1): k=(h[i].donnee)+(h[i+1].donnee) g.append(Arbre(k,h[i],h[i+1])) else: for i in range(0,len(h)-2): k=(h[i].donnee)+(h[i+1].donnee) g.append(Arbre(k,h[i],h[i+1])) g.append(Arbre(h[len(h)-1])) h=g g=[] i+=1 return h
Le début fait référence à d'autres fonctions que j'ai créé, ce n'est pas le problème ici.
Mon problème se trouve à partir du 'while' : quand j'exécute la fonction, cela me renvoie une liste avec seulement les feuilles de départ, l'arbre n'a pas "évolué" et je ne comprends pas pourquoi.
class Arbre():
def __init__ (self,donnee,gauche=None,droit=None):
self.donnee = donnee
self.gauche = gauche
self.droit = droit
def __repr__ (self):
return("Arbre de noeud {} de fils gauche {} et de fils droit {}".format(self.donnee,self.gauche,self.droit))
def arbrehuff(liste):
#la liste correspond au dictionnaire classé par ordre croissant de fréquences
l=liste
m=[]
h=[]
for k in range(0,len(l)):
if l[k][1]!=0:
m.append (l[k][0])
h.append (l[k][1])
#m est la liste des caractères dans l'ordre de trifusion
#h est la liste des fréquences associées
i=0
#transformer h en liste d'arbres
h1=[]
for i in range (0,len(h)):
h1.append(Arbre(h[i]))
h=h1
g=[]
nbdetapes= nombreetapes(len(h))
while i<nbdetapes:
if len(h)%2==0:
for i in range (0,len(h)-1):
k=(h[i].donnee)+(h[i+1].donnee)
g.append(Arbre(k,h[i],h[i+1]))
else:
for i in range(0,len(h)-2):
k=(h[i].donnee)+(h[i+1].donnee)
g.append(Arbre(k,h[i],h[i+1]))
g.append(Arbre(h[len(h)-1]))
h=g
g=[]
i+=1
return h
je suis étonné par ton utilisation simultanée de la variable i dans la boucle while (lignes 29 à 41) et dans les boucles for imbriquées dans la boucle while (lignes 31 à 33 ou 35 à 37).
si le problème persiste après avoir adapté cela, peux-tu partager un code complet qui peut être exécuté?
En effet, c'était une erreur. Je l'ai corrigé mais le problème persiste, je vous envoie le code en entier (en plusieurs fois) :
alphabet=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
longalpha=len(alphabet)
def calculfreq (L):
#renvoie une liste de listes contenant le caractère suivi de sa fréquence d'apparition
M=[]
for k in range (longalpha):
M.append([alphabet[k],0])
n=len(L)
for k in range(0,longalpha):
for i in range (0,n):
if L[i]== alphabet[k]:
M[k][1]+=1
return M
def insere(x,liste):
#x est une liste de deux élements: le caractère et sa fréquence d'apparition
if liste==[]:
return [x]
elif (x[1])<=(liste[0][1]):
return [x] + liste
else:
return [liste[0]] + insere(x,liste[1:len(liste)])
def fusion(liste1,liste2):
if liste1==[]:
return liste2
elif liste2==[]:
return liste1
else:
return fusion(liste1[1:len(liste1)],insere(liste1[0],liste2))
def tri_fusion(liste):
#renvoie la liste classée par ordre croissant de fréquence d'apparition des éléments
n=len(liste)
if n==0 or n==1:
return liste
else:
return fusion(tri_fusion(liste[0:n//2]),tri_fusion(liste[n//2:n]))
def nombreetapes(n):
#n est le nombre de caractères
p=n
i=0
while p!=1:
if p%2==0:
p=p/2
else:
p=(p+1)/2
i+=1
return i
#création de classe d'arbre
class Arbre():
def __init__ (self,donnee,gauche=None,droit=None):
self.donnee = donnee
self.gauche = gauche
self.droit = droit
def __repr__ (self):
return("Arbre de noeud {} de fils gauche {} et de fils droit {}".format(self.donnee,self.gauche,self.droit))
class Feuille(Arbre):
def __init__ (self,donnee):
self.gauche = None
self.droit = None
self.donnee = donnee
def arbrehuff(liste):
#la liste correspond au dictionnaire classé par ordre croissant de fréquences
l=liste
m=[]
h=[]
for k in range(0,len(l)):
if l[k][1]!=0:
m.append (l[k][0])
h.append (l[k][1])
#m est la liste des caractères dans l'ordre de trifusion
#h est la liste des fréquences associées
i=0
#transformer h en liste d'arbres
h1=[]
for i in range (0,len(h)):
h1.append(Arbre(h[i]))
h=h1
g=[]
nbdetapes= nombreetapes(len(h))
while i<nbdetapes:
if len(h)%2==0:
for j in range (0,len(h)-1):
k=(h[j].donnee)+(h[j+1].donnee)
g.append(Arbre(k,h[j],h[j+1]))
else:
for i in range(0,len(h)-2):
k=(h[j].donnee)+(h[j+1].donnee)
g.append(Arbre(k,h[j],h[j+1]))
g.append(Arbre(h[len(h)-1]))
h=g
g=[]
i+=1
return h
je suis très étonné d'observer que certains nœuds de ton arbre sont en fait des arbres. est-ce bien le but recherché?
par ailleurs, je pense que tu devrais décrire à nouveau ton soucis. au départ, c'était "l'arbre n'a pas "évolué"": est-ce toujours le même soucis? comment sais-tu que l'arbre n'a pas évolué?
peux-tu également partager un code complet qui peut être exécuté? cela nous permettra de tester exactement la même situation que la tienne: il est possible que tes erreurs soient liées à tes données.
je voulais dire: as-tu vérifié qu'en réalité, la boule while était exécutée le nombre de fois souhaité? quelle technique utilises-tu pour vérifier que ton programme se comporte comme tu le souhaites?
quand tu auras maîtrisé cela, le moment sera venu de mettre des feuilles dans ton arbre, plutôt que des arbres.
j'ai rajouté un print (nbdetapes) avant la boucle while
pour cet exemple, j'obtiens nbdetapes = 2. Comme à chaque étape i augmente de 1, la boucle est parcourue bien deux fois.
tu as au moins deux techniques à ta disposition pour comprendre:
- relire ton code
- ajouter des print
je te suggère d'utiliser d'autres noms pour tes variables: des noms qui correspondent à leur rôles. comme tu l'as fait pour tes fonctions.
