Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1520 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  [Algo] Recherche de sous chaîne

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[Algo] Recherche de sous chaîne

n°1335736
Sebou77
French Tech powaa :-)
Posté le 30-03-2006 à 18:04:17  profilanswer
 

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 :)

mood
Publicité
Posté le 30-03-2006 à 18:04:17  profilanswer
 

n°1335893
olivthill
Posté le 30-03-2006 à 21:41:37  profilanswer
 

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.

n°1335910
Sebou77
French Tech powaa :-)
Posté le 30-03-2006 à 22:11:43  profilanswer
 

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 :)


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  [Algo] Recherche de sous chaîne

 

Sujets relatifs
Recherche algo ou programme pour détection de planrecherche traduction des différents codes css et xhtml
positionement dans moteur de rechercheRecherche Script pour afficher toutes les images d'un dossier !
[ RESOLU ] chercher dans une chaine de caractèrerecherche de script asp/php
recherche logiciel autre que notepad ++ pour xhtml et cssRecherche opérationnelle : quel algorithme ?
Construire une chaîne "en dur"[algo] recherche d'une chaine commune dans une liste de noms
Plus de sujets relatifs à : [Algo] Recherche de sous chaîne


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR