Comprendre la recherche textuelle

Problématique

Essayons de découvrir, via un exemple de séquençage génétique, un algorithme simple 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) ?

Question

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

Solution

AT CAAGT T CAAGT CAGTCCC CAAGT TGATG CAAGT

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

Premier algorithme...

On souhaite formaliser la méthode à travers l'écriture d'un pseudo-code.

Question

Écrire sur papier, l'algorithme pressenti pour réaliser cette recherche textuelle.

Solution

La solution sera donnée très bientôt. C'est une première recherche en classe.

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 :

Fenêtre en position 0Informations[1]

Puis à l'indice 1 du texte :

Fenêtre en position 1Informations[2]

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.

Fenêtre glissante...Informations[3]

Question

Sur l'image précédente, dire :

  • à quel indice i est positionné la fenêtre

  • quelles sont les comparaisons à réaliser...

Indice

Il suffit de lire où se situe la fenêtre

Solution

i vaut 13 et voici les comparaisons à effectuer :

  • 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).

Attention, la recherche s’effectue donc à condition d’avoir i ≤ n-p, sinon, on dépassera la longueur du texte.

Voici une illustration de l'algorithme en vidéo :

Vidéo illustrant l'algorithme naïf
Informations[4]