Discussion :

[j0o0]

Bonjour à tous,

Je dois implémenter très efficacement (en terme de temps d'exécution) une recherche de plusieurs mots dans un texte (positions des éventuelles occurences de chaque mot dans le texte). D'après mes recherches, deux algos sont intéressants :
- Aho-Corasick ;
- Karp-Rabin.

Quel est le plus efficace des 2, sachant que le nombre de mots à rechercher ainsi que la taille du texte et des mots est très variable ?

Merci !

[pseudocode]

Ah ? Je pensais que l'algo de Boyer-Moore était le meilleur, surtout avec les possibilités de paralléliser l'exécution sur les ordinateurs modernes.

[j0o0]

L'algo de Boyer-Moore est très efficace pour la recherche d'un seul mot dans un texte, mais lorsqu'il faut rechercher plusieurs mots je ne suis pas sûr qu'il soit meilleur que l'algo de Aho-Corasick ou Karp-Rabin.

[pseudocode]

L'algo de Boyer-Moore est très efficace pour la recherche d'un seul mot dans un texte, mais lorsqu'il faut rechercher plusieurs mots je ne suis pas sûr qu'il soit meilleur que l'algo de Aho-Corasick ou Karp-Rabin.

C'est clair que la complexité dépend du nombre de mots à chercher par rapport à la longueur du texte. Mais bon, étant donné que tu parles de tailles très variables, je pense qu'en moyenne ca doit être tout de même meilleur que les algos suffix-tree.

Le calcul des tables d'offsets pour les mots est assez rapide à faire, et le parsing du texte pour un mot est en O(taille du texte). Il doit meme y avoir des implémentations optimisées pour faire plusieurs mots à la fois, mais ca doit vite devenir compliquer à gérer. L'algo de base est assez souple pour faire tout un tas d'optimisation simple (parallelisme, travail par fragment, ...)

[Graffito]

Je proposerai une solution basée sur une indexation de N mots recherchés en fonction de leurs 3 première lettre (l1,l2,l3) qui donnent une clé entière de 1 à 256^3.

Pour avoir la meilleure performance, on crée 2 tableaux d'entiers "Index" et "chainage" de taille 256x256x256+N.
Index[i] est égal à l'index du premier mot dont la clé est égale à i dans la liste des mots recherchés.
Chainage[i] pointe sur Index[j] avec j compris entre 256x256x256 et 256x256x256+N afin de chainer tous les mots recherchés ayant la même clé entière.

Ainsi, pour toute séquence de 3 lettres de début de mot, on est capable de savoir très rapidement s'il existe un mot recherché commençant par ces mêmes lettres et, si oui, obtenir tous les mots recherchés dans ce cas.

Il ne reste plus qu'à explorer le texte T en construisant à pour chaque position j dans le texte la clé entiere construite à partir de T[j],T[j+1],T[j+2] et en vérifiant si les éventuels mots recherchés associés à cette clé sont effectivement dans le texte.



Les avantages sont :

• pas de traitement si aucun mot recherché ne commence par les 3 lettre en position j du texte,
• vérifier seulement les mots recherchés qui commencent par les mêmes 3 lettres que le texte en poisition j.
• On peut parralléliser assez facilement en découpant le texte en tronçons et en traitant ces tronçons dans des threads différents (les tableaux index et chainage étant en lecture seule une fois créés au départ à partir des mots recherchés).

[j0o0]

Merci pour vos réponses (désolé pour le délai) !

Graffito, je ne comprends pas bien à quoi correspond la taille de 256...Pourquoi 256 ?

[Graffito]

[0..256] est l'intervalle des caractères ASCII étendus :
"0" => 0x30, "A" =>0x41, "b"=>0x61, "é"=>0x82

Ainsi pour le mot "Cabot", la clé sera 0x43616F


Si on cherche les 3 mots "chat", "cabot" et "cabinet", on aura 2 clés une pour "chat"(C1) et une pour "cabot" et "cabinet" (C2), ainsi que 2 listes de mots L1= { chat } et L2= { cabot, cabinet } avec
C1 -> L1 et C2->L2.