← Retour au chapitre

Fiche à trous · Terminale · NSI

Recherche textuelle : algorithme de Boyer-Moore

Complétez de mémoire, puis vérifiez avec la page de corrigé.

Chercher un mot dans un livre, un gène dans une séquence d'ADN, un virus dans un fichier : il faut trouver un motif dans un texte, le plus vite possible. L'algorithme de Boyer-Moore évite de tester chaque position une à une.

L'algorithme naïf

Règle

L'idée de Boyer-Moore

Définition — Boyer-Moore-Horspool :

Définition — table de sauts :

Efficacité

Règle

Exemple

Calcule la table de sauts du motif « NSI ».

  1. 5.
  2. 6.
  3. 7.

Résultat :

Piège

Comparer de gauche à droite dans Boyer-Moore.

Toujours partir du dernier caractère du motif.

Appliquer Boyer-Moore-Horspool

  1. 9.
  2. 10.
  3. 11.
  4. 12.
  • Ai-je défini le vocabulaire ?
  • Mon code est-il testé sur un exemple ?
  • Ai-je traité les cas limites ?
  • Ai-je justifié la complexité ou le résultat ?

Corrigé · à détacher

Recherche textuelle : algorithme de Boyer-Moore

  1. 1. On place le motif à chaque position du texte et on compare caractère par caractère. Pour un texte de longueur n et un motif de longueur m, le nombre de comparaisons peut atteindre environ n × m.
  2. 2. Version simplifiée de Boyer-Moore : on compare le motif au texte de droite à gauche ; en cas d'échec, on décale le motif grâce à une table de sauts calculée à l'avance.
  3. 3. Pour chaque caractère du motif (sauf le dernier), distance entre sa dernière occurrence et la fin du motif ; un caractère absent du motif permet de sauter de toute la longueur m.
  4. 4. Plus le motif est long et l'alphabet varié, plus les sauts sont grands : on lit bien moins de caractères que l'algorithme naïf. C'est le principe utilisé par la fonction « Rechercher » des éditeurs de texte.
  5. 5. Longueur m = 3.
  6. 6. N est à 2 positions de la fin : saut 2 ; S à 1 position : saut 1.
  7. 7. Tout autre caractère : saut 3.
  8. 8. La table de sauts indique de combien décaler le motif selon le caractère du texte aligné avec la fin du motif.
  9. 9. Calculer la table de sauts du motif.
  10. 10. Aligner le motif au début du texte.
  11. 11. Comparer de droite à gauche.
  12. 12. Décaler selon la table en cas d'échec, jusqu'à la fin du texte.