J'aimerais avoir de l'aide et des pistes de solution pour un problème. J'ai créer un arbre de huffman pour un certaine donnée. Je suis capable facilement de sérialiser les données elle-même, mais j'ai des difficultés a voir comment sérialiser l'arbre.

Le problème c'est que les données de l'arbre sont typé. Il y a 2 type de données différente (des nombres sur 8 bits exactement et des entiers strictement positif d'une taille arbitraire déterminer a l’exécution. Il y as aussi une valeur séparateur, mais je compte la représentée comme l’entier 0 qui ne se retrouvera jamais parmi les autres.) et qui pourrais se superposée. La plupart des solutions que j'ai trouver parte du principe que l'arbre ne contient qu'un seul type de donnée. J'ai bien pensée les différencier en mettant un 0 ou un 1 avant, et d'encoder au début du fichier la taille variable des entiers, mais je suis incertain.

J'aimerais donc avoir des conseils sur comment être capable de séraliser l'arbre avec ces données et de le lire ensuite. L'encodage que devrais prendre les données.

Il y a certainement une facon intellignete de serialiser un arbre de huffman, mais en premiere approximation, pourquoi ne pas le serializer comme un arbre binaire generique ?
Tu donne un parcours en largeur de l'arbre et a pour chaque noeud tu ecris la valeur du noeud et si il a un fils gauche et si il a un fils droit. Et ensuite, il suffit de serialiser la valeur du noeud.

Le 24 juillet 2016 à 21:06:29 godrik a écrit :
Il y a certainement une facon intellignete de serialiser un arbre de huffman, mais en premiere approximation, pourquoi ne pas le serializer comme un arbre binaire generique ?
Tu donne un parcours en largeur de l'arbre et a pour chaque noeud tu ecris la valeur du noeud et si il a un fils gauche et si il a un fils droit. Et ensuite, il suffit de serialiser la valeur du noeud.

Le problème c'est que seule les feuilles contiennent des valeurs. Le reste des noeuds sont "vide". Sa me semble donc un gaspillage d'espace?

Aussi que veux-tu dire par un parcours en largeur?

Merci de prendre le temps de me répondre.

Ah tu as raison l'arbre est sparse. Du coup, il suffit d'identifier chaque valeure non nulle par sa position dans la traverse en largeur d'un arbre binaire complet.

https://en.wikipedia.org/wiki/Breadth-first_search

Le 24 juillet 2016 à 21:56:26 whiteapplex a écrit :
Tu peux donner un exemple de ce que tu veux faire, avec les données ?

J'ai un arbre de huffman qui contient 2 type de données. Un type de 8 bits et un type de taille variable. Je veux pouvoir le mettre sur le disque dur et ensuite pouvoir le relire pour obtenir le même arbre. Sachant que un arbre de huffman sers a donner un mots de code a des valeurs obtenirs les valeurs avec leur mots de code est tous aussi satisfaisant.

Le 24 juillet 2016 à 23:32:32 godrik a écrit :
Ah tu as raison l'arbre est sparse. Du coup, il suffit d'identifier chaque valeure non nulle par sa position dans la traverse en largeur d'un arbre binaire complet.

https://en.wikipedia.org/wiki/Breadth-first_search

Je vois bien comment mettre ça sur le disque, mais comment ensuite, je peux le déserialiser? Même si je connais leur position dans l'arbre je vois mal comment je pourrais refaire l'arbre. Car l'arbre n'est pas balancer. Désolé si j'ai manqué quelque chose.

Le 24 juillet 2016 à 23:32:32 godrik a écrit :
Ah tu as raison l'arbre est sparse. Du coup, il suffit d'identifier chaque valeure non nulle par sa position dans la traverse en largeur d'un arbre binaire complet.

https://en.wikipedia.org/wiki/Breadth-first_search

Je vois bien comment mettre ça sur le disque, mais comment ensuite, je peux le déserialiser? Même si je connais leur position dans l'arbre je vois mal comment je pourrais refaire l'arbre. Car l'arbre n'est pas balancer. Désolé si j'ai manqué quelque chose.

Si tu connais la position de tous les noeuds non vide, il devrait etre facil de reconstruire l'arbre qui va bien, non ? Si tu as une entree en position 14, alors il faut tous les neouds intermediaire qui t'amene au noeud 14.

Je vais expliquer ce que je ne comrpends pas. Disons cette arbre.

https://upload.wikimedia.org/wikipedia/commons/3/33/Breadth-first-tree.svg

Disons qu'on élimine le 3 et que l'arbre est binaire. Les noeuds non-nulle sont alors: 9-10-6-11-12-8. (accompagner de la valeur respective dans l'arbre.) Comment puis-je reconstruire l'arbre?

Aussi comment encoder en binaire de manière efficace ces informations? J'ai pensée encoder au début du fichier la longueur de l'arbre encoder en binaire pour pouvoir couper l'arbre des données a la lecture. Une idée pour ce nombre est de faire comme suis. Je mets le nombre en binaire. Ensuite, entre chaque bit je mets un 0. Et a la fin je mets un 1. Comme ça en décodant je sais que si le bit est un 0 le prochain bit fais partit du nombre. Et quand j'atteint le 1 de contrôle je sais que j'ai tous les bits du nombre. J'ai une difficulté en binaire a me figurer comment "séparer" les données pour être capable de les ravoir par la suite. J'ai l'habitude de pensée en terme de programme de beaucoup plus haut niveau.

C'est pourquoi godrik a suggere un arbre binaire *complet* ; sur ton exemple en supprimant le "3" ton arbre n'est toujours pas complet, et on peut pas deduire sa structure totale juste en connaissant sa profondeur.

Donc tu prends un binaire complet, on numerote, et ensuite c'est trivial d'identifier une position par son indenx.

Pour l'encodage, ca depend vraiment de la nature de tes donnees ; taille fixe, token de separation, etc.

Les noeuds non-nulle sont alors: 9-10-6-11-12-8. (accompagner de la valeur respective dans l'arbre.) Comment puis-je reconstruire l'arbre?

J'ai changer les nombres pour que ca correspondent a un arbre binaire numerote a partir de 1. Si les noeuds non nul sont 7, 8, 9, 10, 11, 12 alors ca ne peut etre que l'arbre presente en [1]. Il faut un chemin qui amene a 7 donc le chemin c'est droite-droite. il faut un chemin qui amene a 8, donc il faut que gauche-gauche-gauche soit un chemin.

[1] http://webpages.uncc.edu/~esaule/temp.jpg

Le 25 juillet 2016 à 20:53:09 LGV a écrit :
C'est pourquoi godrik a suggere un arbre binaire *complet* ; sur ton exemple en supprimant le "3" ton arbre n'est toujours pas complet, et on peut pas deduire sa structure totale juste en connaissant sa profondeur.

Donc tu prends un binaire complet, on numerote, et ensuite c'est trivial d'identifier une position par son indenx.

Pour l'encodage, ca depend vraiment de la nature de tes donnees ; taille fixe, token de separation, etc.

Si par arbre complet tu parle d'un arbre sous cette forme:

http://web.cecs.pdx.edu/~sheard/course/Cs163/Graphics/CompleteBinary.jpg

Je ne peux pas. En fais, l'arbre ne sers pas juste a stocker des données. La positions exacte d'une feuille dans l'arbre a une signification bien précise. Je ne peux donc pas modifier l'arbre pour qu'il soit complet, car alors je détruit de l'information, car la structure exact de l'arbre est de l'information.

Le 25 juillet 2016 à 21:01:09 godrik a écrit :

Les noeuds non-nulle sont alors: 9-10-6-11-12-8. (accompagner de la valeur respective dans l'arbre.) Comment puis-je reconstruire l'arbre?

J'ai changer les nombres pour que ca correspondent a un arbre binaire numerote a partir de 1. Si les noeuds non nul sont 7, 8, 9, 10, 11, 12 alors ca ne peut etre que l'arbre presente en [1]. Il faut un chemin qui amene a 7 donc le chemin c'est droite-droite. il faut un chemin qui amene a 8, donc il faut que gauche-gauche-gauche soit un chemin.

[1] http://webpages.uncc.edu/~esaule/temp.jpg

Comme j'ai dis le problème c'est que l'arbre n'aura jamais cette forme. Un arbre de huffman est extrêmement dé-balancer et donc absolument pas complet.

Voici un arbre de huffman par exemple,.

https://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Huffman_tree_2.svg/625px-Huffman_tree_2.svg.png

oui bien sur. Je ne dis pas qu'il faut construire l'arbre complet. Je dis que tu peux numeroter n'importe quel arbre binaire en utilisant un arbre binaire complet comme reference pour la numerotation. Le probleme que tu as est que tu ne peux pas utiliser le code de huffman pour encoder l'arbre lui meme parcequ'il te faut l'arbre pour savoir faire la decomposition. Donc la seule soluion que je vois est d'utiliser un coode moins efficace pour encoder l'arbre en lui meme. Pour pouvoir faire ca, il faut un systeme de numeroration unique et qui est commun a tous les arbres binaire. Voir un arbre de huffman comme un sous arbre d'un arbre binaire complet te permet d'avoir facilement une numerotation des feuilles de l'arbre.

(note que j'ai numerote a partir de 1 parceque ton exemple commencait sa numerotation a 1. Mais commencer a 0 a un avantage certain ici!)

Voila, tout a fait, on parle de le considerer complet pour la numerotation, mais pas de modifier l'arbre pour le rendre complet.

Ahhhhhhhhh! Merci! Je viens de comprendre! J'ai une bonne idée de quoi faire!

Merci beaucoup de votre aide!