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?
coco01
le problème est que je ne sais pas quoi utiliser comme structure d'arbre
coco01
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
yg_be
Contributeur
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é?
coco01
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)])
coco01
suite :
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]))
coco01
suite(fin) :
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
yg_be
Contributeur
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.
yg_be
Contributeur
que fais-tu pour déterminer combien de fois le while a été exécuté?
coco01
Je le détermine grâce à la fonction nombreetapes
(je me base sur combien de caractères il reste à assembler pour arriver à construire l'arbre)
yg_be
Contributeur
@coco01je 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.
yg_be
Contributeur
@coco01tu souhaites que la boucle soit parcourue deux fois: as-tu vérifié que cela se passait ainsi?
coco01
Je viens de mettre à la fin
return h,i
Pour l'exemple donné ci dessus ça me renvoie i=3, je ne comprends pas pourquoi car nbdetapes=2
