Implémentation codage huffman (python)

[invitecff8806c]

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 :

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
-----

[invite6c250b59]

Si on commence par le commencement:

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?

[invitecff8806c]

Je vous envoie le code en entier :

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

[invite6c250b59]

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:

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:

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:

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!

#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:

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

 
#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:

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

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:

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)

[A voir en vidéo sur Futura]

[invitecff8806c]

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.

[invitecff8806c]

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

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 :

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 ?

[invite6c250b59]

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.

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):

self.dico = self.dico_init(texte)

def dico_init(self, texte):

Une fois cela corrigé le code marche

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.

[invitecff8806c]

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

Voilà mon 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)...