Discussion :

[Enguerrand1]

Bonjour à tous,

je suis en train de réaliser un petit programme pour un projet informatique en prépa, nous travaillons sur la compression d'image et je programme la partie sur la compression de Huffmann. Cette compression réside sur la réalisation d'un arbre avec les différents caractères, chaque chemin correspondant à un caractère (branche de gauche égale à 0 et branche de droite égale à 1), ce qui permet de ressortir un codage pour chaque caractère, qui possède moins de bits qu'un octet classique.

La manière la plus simple de modéliser cet arbre est je pense de créer une série de listes imbriquées, où l'indice d'un élément serait son code.

Ma question est la suivante : existe-t-il une fonction dans le même esprit que "index" qui permettrait de récupérer l'indice complexe d'un élément dans une série de liste imbriquées ?
par exemple :

A=[[[' ', ['H', [['V', ['X', ['U', 'W']]], ['J', 'K']]]], ['C', 'Z']],[['A', 'B'],[['O', [['P', ['G', 'M']], [[['L', 'S'], ['E', 'F']], 'N']]], 'I']]]

serait un arbre. La lettre 'O' a pour indice 1 1 0 0, lorsque je tape A[1][1][0][0] je récupère le 'O'. Je recherche une fonction permettant d'obtenir l'indice du 'O' directement.

Merci par avance pour vos réponses ! :-)

[wiztricks]

Salut,

Ma question est la suivante : existe-t-il une fonction dans le même esprit que "index" qui permettrait de récupérer l'indice complexe d'un élément dans une série de liste imbriquées ?

Une telle fonction n'existe pas mais associer à chaque caractère son indice, c'est parcourir l'arbre pour fabriquer un dictionnaire réalisant cette association.

La manière la plus simple de modéliser cet arbre est je pense de créer une série de listes imbriquées, où l'indice d'un élément serait son code.

Ca devrait fonctionner mais avec Python un arbre binaire est déjà réalisé avec le module standard heapq (et vous avez des exemples d'utilisation de codage de huffman avec cette bibliothèque qui montrent que çà aide bien).

- W

[lg_53]

Une manière de faire parmi d'autres :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def getpathofbinarytree(l, idx=()):
    if type(l) is list :
        n = len(l)
        if n==0 : return {}
        d = getpathofbinarytree(l[0], idx+(0,))
        if n>1 : d.update( getpathofbinarytree(l[1], idx+(1,) ) )
        return d
    else :
        return {idx:l}
 
pathtree = getpathofbinarytree(A)
paths = list(pathtree.keys())
treeval = list(pathtree.values())
 
#### Pour vous rendre compte un peu de ce qu'il y a la dedans
for k,v in pathtree.items(): print(k,v)
 
#### Pour rechercher une lettre
print( paths[ treeval.index('O') ] )

[Sve@r]

Bonjour

if type(l) is list

Tu ne voudrais pas que ta fonction puisse aussi gérer un tuple ?
Même sans ça, le danger de cette méthode, c'est que si "l" est un truc qui hérite de list, ça ne marche plus
Exemple

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
class xxx(list): pass
 
A=[[[' ', ['H', [['V', ['X', ['U', 'W']]], ['J', 'K']]]], ['C', 'Z']],[['A', 'B'],[['O', [['P', ['G', 'M']], [[['L', 'S'], ['E', 'F']], 'N']]], 'I']]]
pathtree1 = getpathofbinarytree(A)           # HADOPI
A=xxx(A)
pathtree2 = getpathofbinarytree(A)           # HAPUDOPI

Solution: isinstance() => if isinstance(l, list). La fonction reconnaitra une liste dans "l" même s'il n'en est que son arrière petit-fils. Et (avantage) ça permet de tester plusieurs possibilités => if isinstance(l, (tuple, list)).

Sinon j'ai bien aimé ta fonction

[Enguerrand1]

Bonjour,

merci pour vos réponses ! J'aime bien la fonction utilisant un dictionnaire, je vais creuser de mon côté pour vraiment comprendre comment marche un dictionnaire, je suis plutôt débutant en python et je ne maitrise pas encore cette notion, et ensuite comprendre le fond de la fonction.

[lg_53]

Solution: isinstance() => if isinstance(l, list). La fonction reconnaitra une liste dans "l" même s'il n'en est que son arrière petit-fils. Et (avantage) ça permet de tester plusieurs possibilités => if isinstance(l, (tuple, list)).

Ouaip, j'avais déjà passé pas mal de temps à faire la fonction, et puis j'avais une réunion qui m'attendait, alors j'ai posté ce que j'avais et qui fonctionnait sans changer ça. Et comme notre ami nous as dit une liste, je suis resté sur la liste. Parce que au sens large, on pourrait vouloir considérer tout type d'itérable, et donc tester un truc du style isinstance(l, collections.Iterable), mais pas sûr de la syntaxe exact, à vérifier.

J'aime bien la fonction utilisant un dictionnaire, je vais creuser de mon côté pour vraiment comprendre comment marche un dictionnaire, je suis plutôt débutant en python et je ne maitrise pas encore cette notion, et ensuite comprendre le fond de la fonction.

Ce n'est guère compliqué. Quand on a une liste, on accède aux éléments via leur index. Quand on a des dico, on accède aux éléments via leur clé (un tag, un label). Et là la subtilité dans la solution que je propose (qui complique probablement la compréhension du code) c'est qu'en tag je n'ai pas mis juste une chaine de caractère comme on le fait bien souvent, j'ai mis un tuple. Ce qui donne donc plus de sens à la clé, car elle va donc contenir le chemin dans ton arbre pour accéder à l'élément.