Implémentation codage huffman
coco01
-
yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention -
yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention -
Bonjour,
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 ?
Cordialement
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 ?
Cordialement
7 réponses
-
yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention Ambassadeur 1 588
bonjour, qu'as-tu essayé? sur quoi bloques-tu? -
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.
Merci d'avance pour votre aide.
Cordialement-
peux-tu utiliser la coloration syntaxique pour poster ton code?
-
-
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question -
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 -
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)])-
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])) -
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 -
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 Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention Ambassadeur 1 588
que fais-tu pour déterminer combien de fois le while a été exécuté?-
-
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. -
-
-
-
