Discussion :

[yarf]

Bonjour,

je dois manipuler des structures d'arbres avec pour chaque noeud un nombre de fils pouvant aller jusqu'à plusieurs milliers (pour le moment environ 17000), et d'une profondeur pouvant varier de 3 à 6 (la structure stoque des n-grammes). Donc je ne peux pas tout charger en mémoire. Les arbres se construisent en parcourant un corpus. J'ai envisagé deux solutions mais comme elles sont laborieuses à implémenter, je vous demande votre avis d'experts avant.

La première est la suivante : quand on rencontre un n-gramme, on charge un certain nombre de n-grammes stoqués dans un fichier, ceux qui sont "autour" du n-gramme courant. Puis tant qu'on ne sort pas du cadre et que la mémoire utilisée ne dépasse pas un certain seuil, on insère les n-grammes suivants (ou on modifie le nombre d'occurrences s'ils ont déjà été insérés). Si on sort du cadre on recommence comme avec le premier n-gramme, après avoir modifié le fichier bien-sûr, et on stoque chaque fois les indices auquels le premier élément dans la liste des n-grammes change. Par exemple pour la liste :

1 2 3
1 3 9
1 6 7
2 8 5
2 1 1

on stoquerait (0, 3). Ainsi on peut retrouver les n-grammes plus rapidement avec une dichotomie.

La seconde : on crée un fichier par noeud du premier niveau (ou plutôt le niveau correspondant aux premiers éléments des n-grammes) et on en garde un certain nombre en mémoire. Au début ils sont tous en mémoire et petit à petit on n'en garde que certains quand la mémoire occupée dépasse un certain seuil. Et quand un n-gramme recherché n'est pas dans ceux en mémoire, on charge le fichier correspondant et on "décharge" un autre sous-arbre. Le problème c'est que cela implique la manipulation de 17000 fichiers.

Que pensez-vous de ces deux solutions ? En auriez-vous de meilleures à proposer ?

J'ai oublié de dire qu'à terme je voudrais que la liste des n-grammes soit stoquée dans un fichier.

[gifffftane]

Il faut que tu raisonnes plus en termes de services utilisateur, et moins en termes de performances.

Par exemple, admettons que tu proposes à l'utilisateur Pour tel n-gramme voici tous les n-grammes de profondeur 2. Alors tu vas (je suppose), lui donner ce service, et réfléchir pour le lui donner le mieux possible, mais sans te poser la question de savoir s'il est utile dans son cas précis.

Tu vas ainsi lui proposer une bibliothèque d'accès, bibliothèque que tu perfectionneras au fur et à mesure de l'expérience.

Dans un premier temps, peut être peux-tu t'inspirer tout simplement du modèle des arbres JTree, (qui ne feront certes pas gagner un doctorat en informatique), les TreeModel, en supprimant tout ce qui concerne la GUI ?

Pour le stockage, fais ce qui est le plus pratique pour toi ; tu pourras perfectionner après. Pour des arbres, un fichier XML ou Json devrait faire l'affaire ?...

[yarf]

Il faut que tu raisonnes plus en termes de services utilisateur, et moins en termes de performances.

Mon problème est lié à la phase d'apprentissage d'un modèle statistique, donc je n'ai pas besoin de me soucier des services utilisateurs. D'autant que l'étape d'utilisation du modèle me semble bien plus simple à traiter, mais bon je te demande de me faire confiance j'ai un peu la flemme de détailler... Dire que le problème est lié à une phase d'apprentissage est suffisant non ?

Dans un premier temps, peut être peux-tu t'inspirer tout simplement du modèle des arbres JTree, (qui ne feront certes pas gagner un doctorat en informatique), les TreeModel, en supprimant tout ce qui concerne la GUI ?

La classe d'arbre que j'ai implémentée est directement inspirée de DefaultMutableTreeNode, en plus spécifique pour que chaque objet occupe moins de mémoire. Mais le problème est la quantité de données : je dois insérer des noeuds dans un arbre que je ne peux pas charger totalement en mémoire.

Pour le stockage, fais ce qui est le plus pratique pour toi ; tu pourras perfectionner après. Pour des arbres, un fichier XML ou Json devrait faire l'affaire ?...

Pour le stoquage, j'utilise un fichier binaire, qui fait envirion 60 Mo pour seulement 4 millions de trigrammes (obtenus en les chargeant tous en mémoire). Les fichiers finaux sont sensés faire plusieurs Gigas.

Merci pour ta réponse, si quelque-chose ne semble pas clair n'hésite pas à me demander, c'est toujours difficile d'être concis et clair dans un forum.

[gifffftane]

Décidément tout le monde fait des stats en ce moment ! Y'a un prestataire de service sur le sujet qui vient d'ouvrir ses portes ?

Je découvre que c'est un domaine qui n'a pas besoin de se soucier des services utilisateurs ?... Bon, j'admets, on va pas philosopher, je ne connais pas tout...

J'avoue ne pas trop savoir comment ça se passe sur des fichiers qui font plusieurs gigas... il existe bien des techniques et combines à base de curseurs pour se débrouiller avec des valeurs séquentielles qu'on ne peut charger entièrement en mémoire, mais pour les arbres c'est un peu plus finaud, et, en plus, pour des trucs de x gigas...

Bon courage, désolé