Sujet Précédent Sujet Suivant

Implémentation codage huffman

Fermé
-
Messages postés
18325
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
28 janvier 2022
 -
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
A voir également:

7 réponses

Réponse 1 / 7
Messages postés
18325
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
28 janvier 2022
 1 002
bonjour, qu'as-tu essayé? sur quoi bloques-tu?
Réponse 2 / 7

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?
Réponse 3 / 7

le problème est que je ne sais pas quoi utiliser comme structure d'arbre
Réponse 4 / 7

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
Messages postés
18325
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
28 janvier 2022
 1 002
peux-tu utiliser la coloration syntaxique pour poster ton code?
Réponse 5 / 7 

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
Messages postés
18325
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
28 janvier 2022
 1 002
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é?
Réponse 6 / 7

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
Messages postés
18325
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
28 janvier 2022
 1 002
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.
Réponse 7 / 7
Messages postés
18325
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
28 janvier 2022
 1 002
que fais-tu pour déterminer combien de fois le while a été exécuté?

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)
Messages postés
18325
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
28 janvier 2022
 1 002 > coco01
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 essayé ma fonction avec cet exemple : 

L=["a","a","a","n","t","i"]
M=calculfreq(L)      
print(arbrehuff(tri_fusion(M)))


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.
Messages postés
18325
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
28 janvier 2022
 1 002 > coco01
tu souhaites que la boucle soit parcourue deux fois: as-tu vérifié que cela se passait ainsi?

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
Afficher les 6 commentaires
Posez votre question

sur les mêmes thèmes