Aller au contenu

Recherche Textuelle☘

Dans de nombreuses situations, il est nécessaire de rechercher si un mot (ou une expression) est présent(e) au sein d’un texte voire identifier où trouver ce mot (cette expression).

Exemples

  • Option « Chercher/Remplacer » dans un éditeur de texte, souvent accessible à l’aide du raccourci [Ctrl]+[F].
  • Moteur de recherche.
  • Analyse de séquences génétiques ou biologiques.

Problématique☘

Les situations précédentes reviennent à utiliser un algorithme de recherche textuelle. Ce type de recherche peut se résumer ainsi :

  1. Un texte est représenté par une chaîne de n caractères.

  2. Un motif est une chaîne de p caractères.
    En pratique on a 1 ≤ p ≤ n, et même p beaucoup plus petit que n.

  3. Ce motif est-il présent dans le texte ? Si oui, à quelle(s) position(s) ?

Exemples

Déterminer le nombre d'occurrences (et leur positions respectives) du motif CAAGT dans le texte ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT.

Une réponse

ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT

Le motif est présent quatre fois dans le texte, aux indices 2, 8, 20 et 30.

Fenêtre glissante☘

Les algorithmes de recherche textuelle reposent sur le principe de la « fenêtre glissante » : on positionne le motif à différentes positions du texte puis on teste si chaque caractère du motif est identique au caractère correspondant du texte :

  • On positionne la fenêtre à l'indice 0 du texte :

  • Puis à l'indice 1 du texte :

  • etc...

Pour établir la correspondance entre les différents caractères, il faut prendre en compte à la fois les indices des caractères dans le texte et les indices des caractères dans le motif. On note :

  • i la position de la fenêtre dans le texte : c’est l’indice du premier caractère du texte qui apparaît dans la fenêtre.

  • j l’indice d’un caractère dans le motif.

Exemples

Sur l'image précédente, la fenêtre est positionnée à l’indice i = 13. A cette étape, les caractères à comparer sont :

  • texte[13] avec motif[0]

  • texte[14] avec motif[1]

  • texte[15] avec motif[2]

  • texte[16] avec motif[3]
  • texte[17] avec motif[4]

Généralisation☘

Lorsque la fenêtre est positionnée à l’indice i du texte, il faut comparer les caractères motif[j] et texte[i+j], avec j compris entre 0 et p-1 (on rappelle que p est la longueur du motif).

Contrainte importante

La recherche s’effectue donc à condition d’avoir i ≤ n-p.