Discussion :

[tesla]

Bonjour,

Je cherche un algo ou une méthode qui permettent de rechercher un texte dans un grand nombre de fichiers (format *.txt et *.xml) rapidement.

Je peux avoir entre 10 et 20 Go de fichiers dont 90% font entre 5 et 10 ko. De plus ces fichiers sont dans des sous repertoires. J'ai donc un arbre d'une taille gigantesque mais il n'est pas spécialement ordonné ! Seule la date - incluse dans le nom des - répertoires pourrait servir. Pour donner une idée, lorsque j'essaye de parcourir un des répertoires contenant les fichiers avec l'explorateur windows cela peut mettre plusieurs minutes (environ 10 000 petits fichiers dans un répertoire). pourtant j'ai un PC puissant.

Je pensais à une solution qui permettrait de construire un arbre "malin" et l'explorer ensuite mais cela est il jouable avec plusieurs Giga de données ?

[souviron34]

sous unixoide tu as la commande "grep" qui te permet ça...

et tu peux faire un script qui explore les répertoires et appelles grep...

Mais je ne sais sous quel système tu es.

[Graffito]

Bonjour,

Compte tenu des volumes, je crééerai en mémoire l'arbre des répertoires, puis examinerai chaque répertoire l'un après l'autre.

Ensuite, Algo de recherche dans chaque fichier:
- Charger le fichier texte entiérement dans un string,
- rechercher la première occurence de sous-chaine de recherche dans ce string (fonction C : strtok, fonction Pascal : Pos, ...).

[tesla]

Merci pour vos réponses.

Hélas je ne suis pas sous Unix...en plus il faut jongler avec des dossiers compressés, misere. C'est encore plus lent.

[mamelouk]

héhé si c'était si facile on aurait pas besoin de google pour fouiller le web.

tu devrais regarder du coté de lucene

mais bon là on ne parle plus d'algorithmie...

[souviron34]

(fonction C : strtok, fonction Pascal : Pos, ...).

surtout pas strtok en C pour ce genre de problème..... Cette fonction isole les mots un par un.... Et de plus elle alloue de la mémoire dynamiquement à chaque appel.... Bonjour la perte de temps....

Non si la solution est de faire un programme et que le langage choisi est C, alors la solution sera strstr (qui vérifie si une sous-chaîne est présente dans une chaine..)

Quant à construire l'arbre d'un seul coup et à le mettre en mémoire, c'est jouable, mais tu viens de te mettre d'un coup une contrainte de mémoire qui peut s'avérer non négligeable...

Perso moi je ferais un prog. de test simple qui explorerait l'arborescence, et ferais (en C) le strstr ligne à ligne, puisque tu n"es pas sur unixoide. Et je mesurerais déjà combien de temps ça prend, admettons sur 100 megs.
(et si sur unixoide je ferais avec grep).

Et là, ben si ça passe c'est bon, si ça casse, ben faut chercher autre chose

c'est mon avis et je le partage

[edit]
je rajouterais une idée : je suppose que ce processus va se passer assez souvent, mais que l'ensemble des fichiers ne va pas changer tout le temps...
Ce que je ferais c'est passer une fois dans l'ensemble, stocker quelque part le résultat, et avoir un processus parallèle qui surveille la création de nouveaux fichiers, et dans ce cas met à jour les résultats..
Sans doute encore beaucoup plus rapide...
[/edit]

[pseudocode]

idem mamelouk et souviron.

Pour ce genre de probleme, il vaut mieux utiliser un indexeur de fichiers.
De "Lucene" a "Google Desktop SDK", y a du choix...

[sovitec]

Si un outil comme grep est suffisant il existe des portages pour windows comme gnuwin32.

Mais le plus simple serait surement d'utiliser des langages de script évolués comme perl ou python.

[souviron34]

Mais le plus simple serait surement d'utiliser des langages de script évolués comme perl ou python.

Sans doute pas à cause du temps de réponse...

Ne pas oublier que les scripts , lorsqu'ils appellent des programmes, font des "fork", et Java par construction redonne la main au système pour chaque manipulation d'objet différent. Dans un contexte où le volume est très important et le nombre d'objets également, chaque appel à un processus différent (fork) ou au système en asynchrone (Java) perd du temps.

Si le temps est le point critique (et au volume considéré c'est l'essentiel) un binaire ira toujours beaucoup plus vite qu'un script ou un langage interprété.