Bonjour,
Je suis en train d'étudier une nouvelle façon de trier les String, appelée Burtsort.
J'ai vu qu'il y avait déjà des bibliothèque en C++ qui avaient été développées, aussi je voudrais savoir si quelqu'un l'a implémenté en Java.
Merci
Version imprimable
Bonjour,
Je suis en train d'étudier une nouvelle façon de trier les String, appelée Burtsort.
J'ai vu qu'il y avait déjà des bibliothèque en C++ qui avaient été développées, aussi je voudrais savoir si quelqu'un l'a implémenté en Java.
Merci
Bon, je vois que ça ne tente personne le burstSort, alors je vais voir si vous pouvez m'aider en vous donnant plus de précisions.
Donc un BurstTrie consiste en 3 composants :
Records : qui contient la String que l'on gère, des informations supplémentaires utiles à l'application qui utilise ce Sort (comme "word location" par ex.), et un pointer sur le son conteneur(container).
Containers : c'est donc plusieurs "Records" rangées dans une liste ou dans un arbre binaire. Pour un container de profondeur k, les String de chaque record ont au moins une longueur k et ces k caractères sont identiques pour tous les "Records" de ce "container" (par ex : auteur, automobile, autopsie). le container contient aussi une en-tete pour les statistiques.
Puis
Acces Trie : un arbre dont les feuilles sont des containers et les noeuds sont des tableaux p de pointeurs, de longueur équivalent à la taille de l'alphabet (ici 26 bien sur! ). chacun de ces pointeurs pointe donc vers un autre noeud ou vers un container. Et chaque case du tableau est la lettre de l'alphabet correspondant à son index.
Voilà je sais que ça fait beaucoup, mais si quelqu'un a le courage de m'aider, je l'en remercie d'avance.
Mais ?!?!? 8O
Tu as l'algorithme complet, alors ou est le problème pour le codage ?
Tu ne chercherais tout de même pas ici un poireau pour te coder ton algo ? :mrgreen:
non mais merci de ton sarcasme !
Le problème c'est que les mots que je traite sont en minuscule comme en majuscule et qu'il y a encore les accents à prendre en compte.
Donc je voulais déjà savoir pour les tableaux de chaque nœud si je dois agrandir sa taille ou si je dois le faire à 2 dimensions avec les différents variantes de chaque lettre.
Ensuite pour ce qui est des arbres, c'est pas mon fort, je sais que chaque feuille d'un arbre est un arbre sans fils (ou un noeud sans fils) mais je sais pas comment faire pour que les feuilles soient de type différents des noeuds
Je ne cherchais pas du tout à être sarcastique !Citation:
Envoyé par fanzyride
Relis bien les posts, et met-toi à ma place : tu demandes une API pour le tri, personne ne réponds. Et j'imagine que tu as cherchés aussi. Ensuite, tu sors l'algo détaillé sans aucune autre info, on ne connais pas l'état d'avancement de ton dev, ni tes difficultés algorithmiques. Mais maintenant, avec ta réponse, c'est plus clair ;)
Pour le problème des accents, majuscule ... tu recense l'ensemble de ton alphabet et tu dimensionnes tes tableaux en fonction.
Pour les feuille et noeud, tu n'utilise qu'une seule classe (Noeud) qui est dont les instances sont des feuilles si elles n'ont ni fils gauche ni fils droit.
Pour le reste, je te laisse faire 8O
Désolé je m'emporte un peu, je galère dessus depuis hier aprem.
C'est assez compliqué à expliquer c'est un tri par préfixe et la taille du préfixe dépend de la profondeur dans l'abre.
Si tu veux bien regarder le schéma de la page 7 (ou 9) du pdf suivant :
http://goanna.cs.rmit.edu.au/~jz/fulltext/acmtois02.pdf
Il y a aussi les algorithmes pour l'insertion l'éclatement (burst) et la recherche, mais sans la structure de mon arbre j'arrive pas trop à les coder.
Bonjour,
Bon je suis bien arrivé à coder cet algorithme, mais le problème c'est lors de la segmentation d'un texte de 100 Mo Il y a trop de String à stocker donc cela me génère une erreur de outOfMemory. Il faut donc que je puisse sauvegarder le contenu des containers dans un ou des fichiers de façon à pouvoir y accéder constamment pour ajouter modifier ou éclater (burst) son contenu dans des nouveau fichiers/containers (container étant l'équivalent d'un vecteur d'objet ou chaque objet contient la string la liste d'offsets d'occurrences ).
Pour l'instant j'ai fait en sorte que chaque fichier soit un container, et chaque ligne de ce fichier soit un String que l'on peut retransformer en objet (String + offsets d'occurrences). Mais le problème c'est qu'à chaque mot trouvé, je lis un fichier pour en faire un vecteur d'objet, j'ajoute mon mot s'il y est pas sinon j'ajoute les offsets, puis je réenregistre tout le vecteur dans le fichier.
Donc ce n'est pas performant(un texte de 100mo prend minimum 7heures):?.
Je voudrais savoir comment je peux faire pour améliorer cela ?
Merci
en changeant les propriete au lancement de ta machine virtuelle par :
java -Xmx 256m monProg
En mettant le nombre de MB dont tu as besoin.
Euh, Je fais tourner mon programme via éclipse, je dois mettre ça où.
dans eclipse il faut aue tu fasses :
click droit sur ton projet
--> properties
--> Run/Debug settings
puis que tu configures les differents champs pour que ton application s'execute suivant ta volonte.
Dans l'onglet arguments tu as un chanmp VMarguments c'est la qu'il faut mettre la commande.
Peut-être qu'en utilisant la classe "RandomAccessFile" tu peux faire une gestion plus fine de tes fichiers (avec la fonction seek(long) tu peux simuler des pointeurs) et ne pas être obligé de lire et d'écrire complètement un fichier à chaque nouveau mot.
Entre autres, si tes fichiers reflètent la structure du "burst tree".
Si ça peut être une piste :)
Merci baos
ça fait longtemps que je ne suis pas passé, je n'avais pas encore vu ta réponse.
Le problème c'est que je dois testé si le mot que je veux entrer est déjà dans le Fichier et dans ce cas le trouver pour ajouter les offsets de début et fin de ce mot à sa liste d'occurrences.
Je suis encore sur ce problème en ce moment car l'argument à mettre dans la VM java -Xmx 256m monProg ne suffisait pas pour le texte de 100Mo que je dois essayer de traiter