Algo recherche String

Bonjour,

Nous avons un projet en internet chez nous fait sous access de recherche de caractères.

En fait nous avons un fichier .txt en entrée, et une base de données de Mot Clés. Nous recherchons si les mots clés présents dans notre base se trouve dans notre fichier texte. (Nous effacçons les caractères "espace" de notre fichier texte pour n'avoir qu'un String).

Notre processus devient de plus en plus long car notre base de mot clés (Sous Access aussi) devient de plus en plus grande.

J'ai pensé que peut-être Java pourrait être plus rapide que notre algo en VB. Mais je dois pouvoir montrer cela sans passer 3 jours en dévelopement.

Quelque'un peut-il me dire si il existe des algos de recherches, des fonctions Java de recherche entre Strin et Tableau ou HashMap qui sont relativement Rapide et Fiable.

D'avance merci pour toutes vos informations.

:ccool:

Je resume tu as:
- une base des mots cles (sous Access)

- un fichier txt que tu enleves les espaces --> une seule chaine de caracteres

C'est quoi la comparaison alors? Sur quels criteres? Et quelle action?

Avant de te tourner vers un langage particulier, tu dois absolument trouver comment diminuer la complexité de ton algo.
Tu peux avoir à disposition le RoadRunner d'IBM, si ton algo est pourri, tu auras des perfs catastrophiques.
Donc première action primordiale : crayon + papier et tu écris l'algo. Puis si possible tu estimes le nombre de combinaisons de recherche pour le cas moyen, le meilleur cas et le pire cas si possible. Puis tu cherches comment améliorer l'algo et si possible diminuer sa complexité.
L'implémentation viendra bien plus tard.
bon courage !

Le but est de trouver dans la chaine de caractères si mon mon clé de ma base s'y trouve.

Exemple :

Ma base contient : toto, lulu, fifi
Mon txt au départ : "ici toto et lu lu".

Si on ne supprimer pas les blancs, le résultat de mon algo me donnerait comme réponse "TOTO".

En supprimant les blancs, mon algo me donnera "TOTO" et "LULU" comme résultats...

Dans nos résultats, nous avons entre 6000 et 25000 résultats/jour. La base de mot clé que nous avons est composée de 1.200.000 de mots :)

Merci

La recherche de sous chaines dans une chaine existant, sur base du base de donnée de critère, c'est une problème qui a déjà été abordé de nombreuses fois dans la littérature algorithmique, et il existe pas mal d'algos optimisés spécifique. Pour référence, ce problème est identique à celui de la recherche de gènes dans un ADN, (rechercher une séquence de 10.000 caractère dans une chaine de plusieurs millions) et c'est donc une problème qui a déjà largement été optimisé. C'est pas un langage qu'il te faut, ce sont quelques recherches dans la littérature scientifique.


PS: 1.200.000 entrées dans une DB access, alors que tu compare toutes les entrées au contenu du texte: y a-t-il un intérêt à utiliser une base de donnée pour les mots clés?? Est-ce que son aspect relationnel est utilisé? Ensuite, mettre en production une base de donnée sur access, c'est une peu n'importe nawak. Utilise une base de donnée robuste, soit commerciale soit gratuite, mais un truc conçu pour de telles tailles (postgresql, mysql, oracle, sql server, ....)

Alors tu as effectivement tout intérêt à soigner l'algorithme.
Il y a énormément de possibilités, mais la toute première idée qui me vient est le rangement propre des mots clés sous forme d'arbre N-aire. Chaque cellule représente une lettre.
Tu as une liste de premières lettres sans répétition de tous tes mots clés. Puis chaque cellule-lettre contient une liste des lettres suivantes possibles. Et chaque cellule contient un booléen pour savoir si c'est une lettre de fin de mot ou pas.
Par exemple, pour les mot "tot", "tat", "ou" et "toto", l'arbre sera :
une liste contenant 't' et 'o'.
't' contient la liste 'o', 'a'
'o' contient 'u' avec le booléen de fin de mot à vrai
... etc...

A chaque lettre de la phrase, tu parcours l'arbre pour savoir si le mot existe. S'il n'existe pas, alors tu passe à la lettre suivante.
L'avantage est que tu ne vas pas parcourir tous tes mots clés pour chaque recherche. Pour chaque lettre de la phrase, si tu utilises 26 lettres et que les mots ont une longueur N et que la phrase a une longueur P, le nombre de tests sera :
nb_tests = P * N * 26
Ce calcul est le pire cas. Si tu ajoutes 1 millions de mots clés, le temps de calcul dans le pire cas ne sera pas changé !!!

EDIT : trop lent :aie:

Alors pourquoi Access?

Je viens d'arriver dans cette boite et c'est ce qui est utilisé... Je ne peux donc rien révolutionner sans "Preuves" de meilleurs résultats. Je pense comme vous sur cet aspect.

Et pourquoi utiliser une base de données? Nous utilisons bien entendu le relationnel et diverses applications se connectent à cette base.

Je vais regarder un peu du côté des algos.

Je vous remercie de vos commentaires.

la question était plutot, pourquoi une DB pour cette application précise ;) Enfin c'est toi qui vois :)