Répondre à la discussion
Affichage des résultats 1 à 8 sur 8

Implémentation codage huffman (python)




  1. #1
    coco011

    Implémentation codage huffman (python)

    Bonjour,

    Je travaille sur le codage de huffman et j'aimerais pouvoir l'implémenter en python, c'est à dire créer l'arbre binaire etc... J'ai créé quelques fonctions :

    Code:
    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
    
    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 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 problème est que la fonction arbrehuff ne me renvoie pas l'arbre voulu, et je ne vois pas où est l'erreur.

    Si quelqu'un peut m'aider, ce serait sympa

    Cordialement

    -----


  2. Publicité
  3. #2
    Jiav

    Re : Implémentation codage huffman (python)

    Si on commence par le commencement:
    Code:
    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
    Comment cette fonction pourrait-elle marcher alors que alphabet et longalpha ne sont pas passé à la fonction? Est-ce que ce sont des variables globales que tu as définis quelque part?
    L'été vient.

  4. #3
    coco011

    Re : Implémentation codage huffman (python)

    Je vous envoie le code en entier :

    Code:
    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]))
            
            
    #on va créer l'arbre binaire 
    
    
            
    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


  5. #4
    Jiav

    Re : Implémentation codage huffman (python)

    Code:
    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
    D’accodac. Quelques conseils dont je te laisserais décider la pertinence:
    -toujours utile de connaitre les libraries adaptées, ici Re et string pour du texte
    -pour un truc fixe qui doit être interrogé plus souvent que changé, un dictionnaire est plus efficace que des listes
    -perso je n’aime pas voir des variables qui trainent, cela me semble plus sain de tout mettre dans des fonctions et mieux dans une classe.
    -avant de commencer à coder ma suggestion sur la méthode de codage (que j'écris pour me fixer les idées et non pour prétendre que mon conseil serait au niveau des cadors qu'on voit butiner sur ce sous-forum) est de commencer par écrire les commandes simples qu'on aimerait pouvoir utiliser 'sur le fly’. Pour ton problème, on pourrait ainsi commencer par écrire quelque chose comme cela:

    Code:
    Huff = monHuffman(unlivrequelconque).                    # initialiser un dictionnaire
    Message_petit = Huff.coder(message_enclair)              # compresser un message 
    Message_enclair = Huff.decoder(Message_petit)            # décompresser un message
    Une fois qu'on a ces commandes fictives, il devient facile de structurer la création d’objet correspondante:

    Code:
    Import Re, string
    
    class monHuffman():
        def __init__(self, texte = list(string.ascii_lowercase)):
            self.dico = dico_init(texte)  
            self.longalpha = len(self.dico)
        
        def dico_init(texte):
            …
            # return (un dictionnaire de la fréquence d'apparition de chaque caractère)
        
        def coder(message_enclair):
            …
            # return message_petit
    
        def decoder(message_petit):
            …
            # return message_enclair
    Et il ne reste alors qu’à remplir les fonctions par du contenu réel, ce qui est rarement le plus complexe (constat bizarre mais fréquent). Voyons la suite:

    Code:
    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]))
    Rhoo des fonctions qui se définissent par un appel à elle-même. J’adore ce style!

    Code:
    #on va créer l'arbre binaire 
    
    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
    Pourquoi ne pas la mettre dans la classe précédente? Exemple:

    Code:
    class enyrepensant(monHuffman):  # hérite de la classe précédentes et toutes ses méthodes
        def __init__(self, name, texte = list(string.ascii_lowercase)): 
            super(monHuffman, self).__init__(texte=texte)		# et s’initialise pareil
            self.name = name                                    # ou presque
        
        def insere(x,liste):
            …
        def fusion(liste1,liste2):
            …
        def tri_fusion(liste):
            …
        def nombreetapes(n):
            …
    Comme ça tout est bien rangé. Le reste de ton code

    Code:
     
    #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
    Enfin de la vrai magie noire! Tant qu’on invoque pas des objets, on n’est pas des vrais nécromanciens. Par contre ton invocation semble avoir pour but premier de faire le calcul plutôt que de répondre à un besoin d’usage. Pour une raison que je ne comprends pas très bien, cette stratégie aboutie généralement à un code plus difficile à lire que nécessaire (à tout le moins dans mon cas). Ma stratégie serait plutôt de revenir à la classe définie par mes besoins et de la remplir. Exemple avec coder:

    Code:
    class monHuffman():
        …
        
        def coder(message_enclair):
            # pour chaque caractère de message_enclair
            # transform le caractère selon le dictionnaire
            # concatene le résultat
            return message_petit
    
        def decoder(message_petit):
            # pour chaque caractère de message_petit
            # transform le caractère selon le dictionnaire
            # concatene le résultat
            return message_petit
    Qui devient alors

    Code:
    class monHuffman():
        …
        
        def coder(message_enclair):
            res=[]
            for i in range(len(message_enclair))      # pour chaque caractère de message_enclair
                _ = self.dico{Key=message_enclair[i]} # transform le caractère selon le dictionnaire
                res = res.happened(_)                 # concatene le résultat
            return res
    
        def decoder(message_petit):
            # pour chaque caractère de message_petit
            # transform le caractère selon le dictionnaire
            # concatene le résultat
            return message_petit
    Et on continue avec le décodeur, plus on fini avec le dico dont la signification c'est naturellement éclairci en remontant du besoin jusqu'au coeur du problème.

    Il ne manque plus alors qu'un appel à la fonction (absent de ton code complet), qu'il est d'usage répandu d'écrire ainsi:
    Code:
    if __name__ == '__main__':
        Huff = monHuffman(unlivrequelconque).                    # initialiser un dictionnaire
        Message_petit = Huff.coder(message_enclair)              # compresser un message 
        Message_enclair = Huff.decoder(Message_petit)            # décompresser un message
    (pour des raisons d'importation, si on veut se resservir du module ainsi défini)
    Dernière modification par Jiav ; 03/11/2018 à 01h44.
    L'été vient.

  6. #5
    coco011

    Re : Implémentation codage huffman (python)

    Merci beaucoup pour ton aide, je vais essayer d'utiliser seulement les classes alors.
    Mais ce que je trouve complexe c'est la création de l'arbre de Huffman, qui n'apparait pas dans ce que tu me proposes mais qui aiderait beaucoup pour déterminer la fonction coder.

  7. A voir en vidéo sur Futura
  8. #6
    coco011

    Re : Implémentation codage huffman (python)

    Autre chose : j'ai repris ce que tu as commencé et j'ai complété le début :

    Code:
    class monHuffman():
        def __init__(self, texte = list(string.ascii_lowercase)):
            self.dico = dico_init(texte)  
            self.longalpha = len(self.dico)
        
        def dico_init(texte):
            dico = {}
            for element in texte:
                if element in dico:
                    dico[element] = dico[element] + 1
                else:
                    dico[element] = 1
            return dico #return (un dictionnaire de la fréquence d'apparition de chaque caractère)
    Mais je reçois un message d'erreur quand je tente d’exécuter :

    Code:
    Huff = monHuffman(["b","l","a","b","l","a","b","l","a","a"])
    Je pense que c'est lié au fait qu'on fait appel à dico_init pour __init__ , y'a t'il une autre manière d'y arriver ?

  9. #7
    Jiav

    Re : Implémentation codage huffman (python)

    Citation Envoyé par coco011 Voir le message
    Mais ce que je trouve complexe c'est la création de l'arbre de Huffman, qui n'apparait pas dans ce que tu me proposes mais qui aiderait beaucoup pour déterminer la fonction coder.
    Erreur conceptuelle induite par une confusion de ma part: dico ne devrait pas être un dictionnaire de la fréquence d'apparition mais un dictionnaire associant lettre en claire avec code de Huffman. Cela posé alors coder est déjà fait (moyennant vérifier l'absence d'erreur de syntaxe), et c'est bien dico que tu dois faire pour compléter le programme, sauf que dico doit lui même invoquer une arbre de Huffman et un dictionnaire de la fréquence d'apparition pour arriver au résultat souhaité: un dictionnaire associant lettre en claire avec code de Huffman.

    Citation Envoyé par coco011 Voir le message
    Mais je reçois un message d'erreur quand je tente d’exécuter
    La cause est deux petites erreurs de syntaxe (les self ajoutés ci-dessous):

    Code:
    self.dico = self.dico_init(texte)
    Code:
    def dico_init(self, texte):
    Une fois cela corrigé le code marche

    Code:
    Huff = monHuffman(["b","l","a","b","l","a","b","l","a","a"])
    
    Huff.dico
    Out[7]: {'b': 3, 'l': 3, 'a': 4}
    Mais note que le résultat est un dictionnaire associant lettre et fréquence, alors que pour que le codage/decodage marche il faut en fait un dictionnaire associant lettre en clair vs lettre codée.
    Dernière modification par Jiav ; 03/11/2018 à 16h58.
    L'été vient.

  10. Publicité
  11. #8
    coco011

    Re : Implémentation codage huffman (python)

    Bonsoir,
    J'ai avancé dans mon code. J'ai réussi à créer l'arbre de huffman correspondant au message à coder.

    Voilà mon code:
    Code:
    A=Arbre(7,2,5)
    Huff = monHuffman("textequelconque") 
    monHuffman.dico_init("a","textequelconque") 
    #(le "a" ne sert à rien, c'est pour mettre le bon nombre d'arguments)
    monHuffman.deuxmin("a",[Arbre(2,None,None),Arbre(5,None,None),Arbre(10,None,None),Arbre(12,None,None)])
    dico=monHuffman.dico_init("a","eedddddaaaaaaaaaaffffffffffff")
    h=monHuffman.dicointerm("a",dico)
    
    import string
    
    class Arbre():#fonction vérifiée
        def __init__ (self,donnee,gauche=None,droit=None):
            self.donnee = donnee
            self.gauche = gauche
            self.droit = droit  
        def __repr__ (self):
            return("Arbre(et:{},fg:{},fd:{})".format(self.donnee,self.gauche,self.droit))
    
    class monHuffman(): #fonction vérifiée
        def __init__(self, texte):
            self.dico = self.dico_init(texte)  #dico associé au texte
            self.longalpha = len(self.dico)    #longueur du dico associé au texte
            # self.dicocode = self.dicocode_huff
        
        def dico_init(self,texte): #fonction vérifiée
            dico = {}
            for element in texte:
                if element in dico:
                    dico[element] = dico[element] + 1
                else:
                    dico[element] = 1
            return dico #return (un dictionnaire de la fréquence d'apparition de chaque caractère)
        
        def deuxmin(self,liste): #fonction vérifiée
            listeoccu=[]
            for i in range (len(liste)):
                listeoccu.append(liste[i].donnee)#on stocke les etiquettes de tous les arbres dans listeoccu
            m1=listeoccu[0] #choix arbitraire
            for k in range (len(listeoccu)):
                if listeoccu[k]<m1:
                    m1=listeoccu[k]
            listeoccu.remove(m1)
            m2=listeoccu[0]
            for k in range (len(listeoccu)):
                if listeoccu[k]<m2:
                    m2=listeoccu[k]
            l=[]
            for i in range (len(liste)):
                if liste[i].donnee==m1:
                    l.append(liste[i])
                if liste[i].donnee==m2:
                    l.append(liste[i])
            return l
                
        #renvoie une liste des deux arbres avec les plus petites occurences
        #cas où plus de deux occurences sont les mêmes (fonction qui peut être améliorée)
        
        def dicointerm(self,dicofreq): #fonction vérifiée
            valeursbis=[]
            for valeurs in dicofreq.values():
                valeursbis.append(valeurs)
            i=0
            listearbres=[]
            #transformer les valeurs en arbres
            for k in range (len(valeursbis)):
                listearbres.append(Arbre(valeursbis[k]))          
            while (len(listearbres))>1:
                m1=(monHuffman.deuxmin("a",listearbres))[0]
                m2=(monHuffman.deuxmin("a",listearbres))[1]
                somme=(m1.donnee)+(m2.donnee)
                listearbres.append(Arbre(somme,m1,m2))
                listearbres.remove(m1)
                listearbres.remove(m2)
            return listearbres
        # dicointerm donne l'arbre de huffman associé au dico de fréquence
    Mais je ne sais pas comment, à partir de l'arbre de huffman, rendre le dictionnaire associé (comportant des 0 et des 1)...

Discussions similaires

  1. Problème codage sur python
    Par lilis11 dans le forum Programmation et langages, Algorithmique
    Réponses: 2
    Dernier message: 31/03/2018, 08h23
  2. Python codage difficile
    Par Inception dans le forum Programmation et langages, Algorithmique
    Réponses: 8
    Dernier message: 08/03/2015, 07h04
  3. TPE sur le pixels, codage binaire, codage hexadécimal..
    Par rachid84 dans le forum TPE / TIPE et autres travaux
    Réponses: 0
    Dernier message: 09/11/2012, 16h16
  4. la quantification et le codage huffman
    Par kadjuv dans le forum Logiciel - Software - Open Source
    Réponses: 0
    Dernier message: 12/11/2009, 10h33
  5. Compression des données ( Codage Huffman )
    Par NuxVsTheWorld dans le forum Logiciel - Software - Open Source
    Réponses: 14
    Dernier message: 22/04/2009, 14h12