Version imprimable
Bonjour à tous,
Je recherche un algorithme optimal pour la recherche du mot M dans le texte T (qq Mo).
Le texte T est composé uniquement de lettres 'A'..'Z'.
Le mot S est composé de lettres 'A'..'Z',
mais peut aussi comporter un ou plusieurs '?' (n'importe quelle lettre)...
L'algo devra trouver le plus rapidement possible toutes les occurences du mot M dans le texte T.
Bonsoir,
parcourir le texte lettre par lettre
tester chaque lettre avec la première lettre du mot recherché
si c'est la même tester la suivante.... et ainsi de suite
sinon revenir pour tester avec la première lettre du mot recherché
placer les lettre du mot recherché dans un vecteur avec lequel tu pourras faire le test.
Ca c'est l'algorithme naïf et c'est lent. On peut faire beaucoup mieux, par exemple en faisant un automate, on peut passer de O(nm) à O(n).Citation:
Envoyé par acacia
--
Jedaï
Bonsoir Jedai,
Je savais qu'on allait me dire ça :triste:Citation:
Envoyé par Jedai
je trouve l'idée intéressante, mais je ne vois pas très bien comment l'implémenter? :?Citation:
Envoyé par Jedai
Pour la culture générale :
http://www-igm.univ-mlv.fr/~lecroq/string/index.html
Ce lien est très interessant mais je ne nage un peu devant tous ces algorithmes...
Lequel est le plus rapide pour moi, en tenant compte du fait que le mot M
peut comporter un ou des '?'.
Essaye le "Deterministic Finite Automaton algorithm".Citation:
Envoyé par sbadecoder
Avec un alphabet de seulement 26 lettres (+ un jocker) ca ne devrait pas etre trop gourmand en mémoire et ca va etre tres rapide.
Si tu as simplement un ? et pas de *, il devrait etre possible d'adapter Boyer-Moore (ou une variante qui ne degenere pas en nm si les motifs periodiques sont vraissemblables, sinon je ne suis pas sur que ca en vaille la peine).
En fait si le mot M recherché est 'TEXT'
il faut parfois que je recherche aussi
'T?E?X?T', donc une seule lettre entre et jamais de *
et 'T??E??X??T' etc...
et une bonne vieille expression régulière?
C'est une bonne vieille expression régulière, mais on suppose que s'il est venu sur ce forum c'est pour trouver un algorithme, pas une librairie (sinon il s'est trompé de forum).Citation:
Envoyé par heid
--
Jedaï
Comme le but n'est pas d'implémenter une solution générale, on peux l'exprimer de la manière suivante.Citation:
Envoyé par Jedai
Tu dois implémenter 5 états :
Etat 1 (initial) : rien trouvé
Etat 2 : premier T trouvé
Etat 3 : E trouvé
Etat 4 : X trouvé
Etat 5 : dernier T trouvé
Au départ, tu es dans l'état 1. Tu parcours ton texte, et à chaque lettre, tu fait :
si Etat = 1, si lettre = T, passer à l'état 2, sinon, rester à l'état 1
si Etat = 2, si lettre = E, passer à l'état 3, sinon, retourner à l'état 1
si Etat = 3, si lettre = X, passer à l'état 4, sinon, retourner à l'état 1
si Etat = 4, si lettre = T, passer à l'état 5 (c'est fini :D), sinon, retourner à l'état 2 (ici, on utilise le fait que le T est à la fois préfixe et suffixe du mot).
Tu peux compléter l'algo pour chercher les chaînes avec joker ? en associant à chaque état 2, 3 et 4 un compteur. On stagnera sur un état jusqu'à ce que le compteur soit égal au nombre de jokers recherchés, puis on appliquera le même test que ci-dessus. En cas de retour vers l'arrière, il faudra réinitialiser les compteurs.