La Recherche Textuelle et l'Algorithme de Boyer-Moore

La recherche textuelle est un domaine clé en informatique qui consiste à trouver un motif (ou une chaîne de caractères) dans un texte. Cette tâche est courante dans de nombreuses applications informatiques, telles que la recherche de mots-clés dans un document, la recherche de chaînes de caractères dans des fichiers ou encore les requêtes de recherche sur le web.

Pour accomplir cette tâche de manière efficace, il existe plusieurs algorithmes de recherche textuelle, chacun ayant ses propres avantages et inconvénients en termes de temps d'exécution, de complexité et de précision. L'un des algorithmes les plus performants pour rechercher des motifs dans un texte est l'algorithme de Boyer-Moore.

Le Fonctionnement de 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. Voici comment il fonctionne :

• Il 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, l'algorithme utilise les règles de décalage pour sauter des positions dans le texte en vue du prochain essai de correspondance.

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

1. 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.
2. 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.
3. 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, ce qui rend l'algorithme de Boyer-Moore très efficace.

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.

  Copier le code

  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".

  Copier le code

  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".

  Copier le code

  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".

  Copier le code

  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.

  Copier le code

  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.