[Algo] Recherche de sous chaîne

Recherche de sous chaîne [Algo] - Algo - Programmation

Marsh Posté le 30-03-2006 à 18:04:17    

Bonjour à tous,
 
voilà je vais devoir réaliser un moteur de recherche pour mon stage, cette application devra chercher dans le contenu de fichiers excel une certaine chaine.
 
Mais là je me pose des questions sur l'algorithme de recherche que je vais utiliser, j'ai déja vu qu'il existait KMP ou Boyer-Moore, je ne les ai jamais utiliser, à votre avis y en a t'il un plus puissant que l'autre ? Ou plus facile à mettre en place ? Ou peut être un autre algo que je n'aurais pas vu ? Ou peut être pas d'algo du tout ?
 
Une autre question que je me pose, par rapport à l'ouverture des fichiers, en effet je me dis que si j'ouvre un flux pour chaque fichiers excels à chaque recherche ça va faire un peu lourd nan ?
Je pensais peut être à copier le contenu des fichiers excel dans un fichier texte, donc ne garder que le texte et ne faire une recherche que dans un gros fichier.
Vous trouvez ça aussi lourd ou intéressant ?
Sachant qu'il peut y avoir une 100aine de fichier excels !
 
Merci beaucoup pour votre aide :)

Reply

Marsh Posté le 30-03-2006 à 18:04:17   

Reply

Marsh Posté le 30-03-2006 à 21:41:37    

Boyer-Moore est considéré comme étant un chouia meilleur que KMP, mais cela dépend de la sous-chaine à trouver et de la chaine dans laquelle se fait la recherche.
 
Pour Boyer-Moore, voir http://www-igm.univ-mlv.fr/~lecroq/string/node14.html
Pour Knuth-Morris-Pratt, voir http://www-igm.univ-mlv.fr/~lecroq [...] ECTION0080
 
Les deux algorithmes se basent en gros sur le même prinicipe, mais il y en a un qui va de gauche droite et l'autre dans l'autre sens. Ils profitent des lettres qui apparaissent plusieurs fois dans la sous-chaine à chercher. Mais ils sont moins performant qu'une recherche brute ordinaire dans le cas où la sous-chaine ne contient aucune lettre en double.
 
Par ailleurs, le gain est tout de même relativement faible car l'algorithme ordinaire simple est très rapide. En essayant, j'avais réalisé que gagner 20 pourcent sur une recherche qui dure deux secondes au total, ne vaut pas le coup de s'ennuyer avec KMP ou BM. En fait, la différence était même totalement effacé dans mon cas par le fait que les entrées/sorties sur disque sont beaucoup plus lentes que la recherche en mémoire, et donc la CPU n'était que partiellement utilisée dans les deux cas, puisqu'il fallait attendre la lecture du disque.
 
Je ne comprends pas bien la deuxième question. Je peux juste dire, comme M. de La Palisse, qu'il est très probable qu'une recherche dans un fichier texte sera plus rapide que dans un fichier Excel.

Reply

Marsh Posté le 30-03-2006 à 22:11:43    

Merci pour tes liens et pour tes conseils, du coup je vais peut être simplement faire une comparaison de chaine :)
 
Pour mon autre question en fait l'idée ça serait de lire tous les fichiers excel d'un coup et d'en copier le contenu dans un simple fichier, donc de n'avoir que un seul fichier avec seulement du texte (le texte des fichiers excel) et de faire ma recherche que dans ce fichier et non dans chaque fichier excel.
 
Encore merci :)

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed