Implémentation codage huffman

Python

coco01 -
yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention - 3 nov. 2018 à 15:23

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

Afficher la suite

A voir également:

Le codage optimisé proposé ci-dessous a été obtenu en appliquant l'algorithme du codage de huffman sur un texte.
Le codage optimisé proposé ci-dessous a été obtenu en appliquant l'algorithme du codage de huffman sur un texte. lucia a codé un mot en utilisant ce codage optimisé. elle a obtenu : 01001000111011 codage standard codage optimisé lettre codage lettre codage m 01001101 m 00 a 01000001 a 10 s 01010011 s 011 e 01000101 e 111 d 01000100 d 0100 g 01000111 g 0101 l 01001100 l 1100 r 01010010 r 1101 - Meilleures réponses
11001011010101111 - Meilleures réponses
Codage ascii - Guide
Codage binaire - Guide
Controleur de codage/decodage pci ✓ - Forum Pilotes (drivers)
Pilote controleur de codage/décodage PCI manquant ✓ - Forum Pilotes (drivers)
Contrôleur de codage/décodage PCI pilote manquant ASUS X751S - Forum Pilotes (drivers)

7 réponses

Réponse 1 / 7

yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention Ambassadeur 1 584

bonjour, qu'as-tu essayé? sur quoi bloques-tu?

Réponse 4 / 7

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.

Merci d'avance pour votre aide.
Cordialement

yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention 1 584

peux-tu utiliser la coloration syntaxique pour poster ton code?

Réponse 5 / 7

coco01

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 Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention 1 584

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

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 Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention 1 584

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

yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention Ambassadeur 1 584

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 Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention 1 584 > 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.

coco01

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.

yg_be Messages postés 23541 Date d'inscription Statut Contributeur Dernière intervention 1 584 > coco01

tu 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

Discussions similaires

Chiffrement de Vigenère en Python

Algo python Conversion Base 2 à base 10 et base 10 à base 16

A quoi sert le return ?

Programme bataille navale python

Programme ".py" qui ne se lance pas

int(input())

Votre réponse

Discussions similaires