Bonjour,

je souhaite coder un arbre de huffman à partir d'un texte, mais une fois que j'ai crée l'arbre sous forme de liste de tuples, de tuples, de tuples, etc., je ne trouve pas comment faire pour parcourir chaque branche...

Comment peut-on faire pour parcourir chaque branche d'un arbre, sachant que chaque branchement à 2 branches?

voici mon code pour l'instant:

#**********Codage entropique: codage de huffman**********
f=open("demaindeslaube.txt","r")
data=f.read()
list_data=list(data)
occurences={}
while len(list_data)>0:
  elt=list_data[0]
  occurences[elt]=list_data.count(elt)
  list_data=[e for e in list_data if e!=elt]
list_occ=[(v,k) for k,v in occurences.items()]
while len(list_occ)>1:
  list_occ.sort(key=lambda x:x[0])
  mini1=list_occ[0]
  mini2=list_occ[1]
  del list_occ[0]
  del list_occ[0]
  list_occ.append((mini1[0]+mini2[0],mini1,mini2))
exam=list_occ[0]
path=""
all_analysed=False
i=0
while not all_analysed or i>1000:
  i+=1
  branches=[]
  branchespaths=[]
  correspondances={}
  while len(exam)==3:
    path+="0"
    branches.append(exam[2])
    branchespaths.append(path[:-1]+"1")
    exam=exam[1]
    if exam in branches:
      del branchespaths[branches.index(exam)]
      del branches[branches.index(exam)]
  correspondances[path]=exam[1]
  if not "0" in path:
    all_analysed=True
  exam=branches[-1]
  path=branchespaths[-1]
print(correspondances)

#d=open("coded.txt","w")

le début correspond à la création de l'arbre et la fin à mes essais pour parcourir l'arbre...

Merci de votre aide!!!

Bon, déjà faire un arbre sous forme d'un liste de tuples c'est vraiment se compliquer la vie. Les dictionnaires sont clairements à privilégier ici. Une autre solution sinon consiste à se faire une petite classe Noeud, avec un attribut fils_droit, et un autre fils_gauche.

Ensuite, pour parcourir un arbre, y'a pas 20 000 solutions simple différentes : des fonctions récursives.

Autres point pour améliorer ton code :

* utiliser l'instruction with pour lire un fichier
* par pitié, par de while len(machin), dans ce cas on utiliser un for ta_variable in ton_iterable

Tes while ont également l'air un peu étrange

-
Edité par Nephthys 11 mai 2021 à 22:15:59

Il y a plusieurs sujets sur le forum avec les mots clés  huffman et python. Tu aurais pu t'en inspirer.
Il me semble que ça se ferait facilement en utilisant collections.Counter et inverser key/value au besoin.

Je ne peux pas utiliser le bouton code. Si vous faites un copier-coller de mon code, vous devriez pouvoir retrouver l'indentation.
Ce n'est pas l'algorithme au complet. Ça donne une idée de ce qu'on peut faire avec la récursivité.
-
# J'ai choisi de représenter l'arbre par un tableau. Ce sera un arbre binaire balancé, le plus souvent non complet
from collections import Counter
texte = "this is an example of a huffman tree."
dicto = Counter(texte)
feuilles = list(sorted(dicto.items(), key=lambda x: x[1]))
# Le truc est que le tableau représentant l'arbre doit être de la même longueur que celui représentant les feuilles
# On utilisera seulement les indices de l'arbre de 1 à len(feuilles)-1, Ici on a 17 feuilles, les indices vont de 1 à 16
# On n'utilisera pas la position 0 de l'arbre
# La racine est à 1, le père d'un noeud N est N//2, les fils d'un noeud N sont 2*N (2*N+0) et 2*N+1
# On reste conforme à la documentation.
arbre=[0]*len(feuilles)   # on oubliera la position 0
#
def arbreBinaire(arbre, feuilles, n):
    # pas optimisé face à len(feuilles)
    # Noter que les indices commencent à 0 dans les feuilles et commencent à 1 dans l'arbre
    if n >= len(feuilles):   # pas dans les noeuds
        if n >= 2*len(feuilles) - 1: return 0    # pas dans les feuilles
        else: return feuilles[n-len(feuilles)][1]   # extraire le poids
    arbre[n] = arbreBinaire(arbre, feuilles, 2*n) + arbreBinaire(arbre, feuilles, 2*n+1)
    return arbre[n]
#
arbreBinaire(arbre, feuilles, 1)   # je ne m'occupe pas de ce que retourne la  racine
print(feuilles)
print(arbre)
-
[('x', 1), ('p', 1), ('l', 1), ('o', 1), ('u', 1), ('r', 1), ('.', 1), ('t', 2), ('h', 2), ('i', 2), ('s', 2), ('n', 2), ('m', 2), ('f', 3), ('a', 4), ('e', 4), (' ', 7)]
[0, 30, 11, 19, 7, 4, 8, 11, 5, 2, 2, 2, 4, 4, 4, 7, 4]