Informatique au lycée Faustin Fleret

La recherche textuelle est un domaine de l'informatique qui consiste à trouver un motif (ou une chaîne de caractères) dans un texte. Cette tâche est courante en informatique, par exemple pour rechercher des mots-clés dans un document, des chaînes de caractères dans des fichiers ou encore pour effectuer des recherches sur le web.

Il existe plusieurs algorithmes pour la recherche textuelle, chacun ayant ses avantages et ses inconvénients en termes de temps d'exécution, de complexité et de précision. L'un des algorithmes les plus efficaces pour la recherche de motifs dans un texte est l'algorithme de Boyer-Moore.

L'algorithme de Boyer-Moore repose sur le principe de la recherche en décalage, c'est-à-dire qu'il utilise des règles de décalage pour éviter de vérifier inutilement des correspondances déjà exclues. L'algorithme commence par la fin du motif et cherche dans le texte la première occurrence du dernier caractère du motif. Si ce dernier caractère est présent dans le texte, on compare les caractères du motif en partant de la fin jusqu'à trouver une différence. Si une différence est trouvée, on utilise les règles de décalage pour sauter des positions dans le texte pour le prochain essai de correspondance.

Les règles de décalage utilisées dans l'algorithme de Boyer-Moore sont les suivantes :

• Si le caractère du texte qui ne correspond pas au motif ne figure pas dans le motif, on décale le motif jusqu'à ce que le dernier caractère du motif coïncide avec le caractère suivant dans le texte.
• Si le caractère du texte qui ne correspond pas au motif figure dans le motif, on décale le motif jusqu'à ce que le dernier caractère du motif coïncide avec ce caractère dans le texte.
• Si le caractère du texte qui ne correspond pas au motif figure dans le motif, mais il n'y a pas de correspondance possible entre les caractères précédents, on décale le motif d'un nombre de caractères égal à la longueur du motif.

Ces règles de décalage permettent de sauter des positions dans le texte pour éviter de vérifier inutilement des correspondances déjà exclues.

Exemple d'application de l'algorithme de Boyer-Moore

Voici un exemple simple d'application de l'algorithme de Boyer-Moore pour la recherche du motif "a b c" dans le texte "a b a c b d a b r a b c a".

Tout d'abord, on construit les tableaux de saut de prétraitement "d" pour le motif "abc":

Ensuite, on commence la recherche à partir de la position 0 du texte. On compare les caractères du motif et du texte de droite à gauche, en commençant par la fin du motif.

Texte :    a b a c b d a b r a b c a
Motif :    a b c

• À la position 2, on compare le caractère "c" du motif et le caractère "a" du texte. Comme ils ne correspondent pas, on utilise le tableau de saut "d" pour déterminer le nombre de positions à sauter.

  Texte :    a b a c b d a b r a b c a
  Motif :            a b c

  Le caractère "a" du texte est pas présent dans le motif, donc on saute 2 positions à droite, ce qui nous amène à la position 4.

• À la position 4, on compare le caractère "c" du motif et le caractère "b" du texte. Comme ils ne correspondent pas, on utilise à nouveau le tableau de saut "d".

  Texte :    a b a c b d a b r a b c a
  Motif :                a b c

  Le caractère "b" du texte est présent dans le motif, donc on saute 1 position à droite, ce qui nous amène à la position 5.

• À la position 5, on compare le caractère "c" du motif et le caractère "d" du texte. Comme ils ne correspondent pas, on utilise le tableau de saut "d".

  Texte :    a b a c b d a b r a b c a
  Motif :                   a b c

  Le caractère "d" du texte n'est pas présent dans le motif, donc on saute 3 position à droite, , ce qui nous amène à la position 8.

• À la position 8, on compare le caractère "c" du motif et le caractère "r" du texte. Comme ils ne correspondent pas, on utilise le tableau de saut "d".

  Texte :    a b a c b d a b r a b c a
  Motif :                                 a b c

  Le caractère "r" du texte n'est pas présent dans le motif, donc on saute 3 position à droite, , ce qui nous amène à la position 11.

• À la position 11, on compare le caractère "c" du motif et le caractère "c" du texte. Comme ils correspondent, on continue à comparer les caractères précédents.

  Texte :    a b a c b d a b r a b c a
  Motif :                                    a b c

• À la position 10, on compare le caractère "b" du motif et le caractère "b" du texte. Comme ils correspondent, on continue à comparer les caractères précédents.

• À la position 9, on compare le caractère "a" du motif et le caractère "a" du texte. Comme ils correspondent, on a trouvé une occurrence du motif à la position 5.

L'algorithme s'arrête ici, car on a trouvé une occurrence du motif dans le texte.