Recherche textuelle et algorithme de Boyer-Moore

Un cap pour ce chapitre

Ce que vous saurez faire

Suivre des alignements de motif.
Construire une table de dernière occurrence.
Justifier un décalage de la règle du mauvais caractère.

Les bases utiles pour commencer

Définir une occurrence et ses indices

Le texte contient n caractères et le motif m caractères. Un alignement à l’indice s compare motif[j] à texte[s+j]. Si toutes les comparaisons correspondent, le motif apparaît à la position s. Les indices commencent ici à zéro, et la casse est significative.

La recherche naïve essaie les positions possibles puis compare les caractères, souvent de gauche à droite. Elle constitue une bonne référence de correction. Une recherche plus élaborée doit trouver les mêmes occurrences, y compris celles qui se chevauchent. Dans ABABA, ABA apparaît aux indices zéro et deux.

L’atelier compte des caractères Unicode par points de code, comme l’indexation usuelle d’une chaîne Python, et non les octets d’un fichier. Ainsi deux symboles 🐍 occupent ici deux positions. Des formes composées d’accents peuvent toutefois utiliser plusieurs points de code ; aucune normalisation linguistique n’est effectuée.

Comparer depuis la droite du motif

La famille Boyer-Moore compare le motif depuis sa droite. Lorsqu’un caractère différent est rencontré, on exploite cette différence pour avancer davantage qu’une seule position lorsque cela est justifié. Les caractères déjà comparés à droite peuvent également fournir des informations dans la version complète.

Cette page étudie explicitement une variante pédagogique utilisant seulement la règle du mauvais caractère avec une table de dernière occurrence. L’algorithme complet combine notamment cette règle à celle du bon suffixe. Les variantes n’ont pas exactement les mêmes décalages ; il faut appliquer les règles de l’énoncé plutôt que mélanger deux versions.

Prétraiter la dernière position de chaque caractère

Pour le motif ABCA, les dernières positions sont A:3, B:1 et C:2. Un caractère absent reçoit conceptuellement la position -1. En cas d’échec à la position j du motif contre le caractère c du texte, notre décalage vaut max(1, j-derniere(c)).

Si c est absent, le décalage j+1 dépasse sa position : aucun caractère du motif ne pourrait lui correspondre dans les alignements sautés. Si sa dernière occurrence est à gauche de j, on l’aligne sur c. Si cette occurrence est à droite de j, la formule peut être nulle ou négative ; le maximum avec un garantit une progression prudente.

Garder une correction vérifiable

Pour trouver toutes les occurrences, l’atelier avance d’une position après une correspondance complète. Ce choix volontairement prudent conserve les chevauchements. Pour une recherche de première occurrence seulement, on pourrait s’arrêter immédiatement. Si le motif est plus long que le texte, aucun alignement complet n’est possible.

Le motif vide demande une convention particulière ; ici l’atelier exige un motif non vide et le signale. Le programme de NSI demande de comprendre l’intérêt du prétraitement et le fonctionnement de Boyer-Moore. L’analyse détaillée de son coût est difficile et n’est pas exigible. On peut mesurer des comparaisons sur des exemples sans transformer ces observations en garantie générale non démontrée.

Ce programme complet suit exactement la variante annoncée et renvoie tous les débuts d’occurrence. Il rejette le motif vide, conserve la casse et utilise les indices des chaînes Python. Comparez ses résultats à la recherche naïve sur de petits textes.

def occurrences(texte, motif):
    if len(motif) == 0:
        raise ValueError("Le motif doit être non vide")
    derniere = {}
    for j, caractere in enumerate(motif):
        derniere[caractere] = j
    resultat = []
    debut = 0
    while debut <= len(texte) - len(motif):
        j = len(motif) - 1
        while j >= 0 and motif[j] == texte[debut + j]:
            j -= 1
        if j < 0:
            resultat.append(debut)
            debut += 1
        else:
            caractere = texte[debut + j]
            debut += max(1, j - derniere.get(caractere, -1))
    return resultat

assert occurrences("ABABA", "ABA") == [0, 2]
assert occurrences("AB", "ABC") == []

Exemple suivi : calculer deux décalages contrastés

Le motif ABCA possède A:3, B:1, C:2. Dans le texte ZZZABCA, le premier alignement commence en zéro. Depuis la droite, A du motif correspond à A du texte à l’indice 3 ; la comparaison suivante oppose C à Z à l’indice 2 et échoue. On a j=2 et dernière(Z)=-1 : le pas vaut trois. Le nouvel alignement commence donc en 3 et les quatre caractères correspondent.

Le décalage n’était pas quatre, car l’échec ne se produisait pas sur le dernier caractère du motif. La règle dépend de la position j de l’échec. Dans un autre alignement, si j=1 et le caractère rencontré est A, la différence 1-3 est négative ; on avance seulement de un. Appliquer systématiquement la longueur du motif ou la position du dernier caractère mélangerait des règles différentes et pourrait sauter une occurrence.

Exemple suivi : préparer un oracle et les cas limites

Un oracle naïf peut examiner chaque début s entre zéro et n-m, puis vérifier tous les caractères du motif. Sur ABABA avec ABA, il trouve 0 et 2. Sur AAAA avec AA, il trouve 0,1,2 : les occurrences se chevauchent. Une variante accélérée doit donner la même liste finale, même si ses comparaisons et ses décalages diffèrent. Le prétraitement change la manière de chercher, pas la définition d’une occurrence.

Si m dépasse n, l’ensemble des débuts possibles est vide et aucune comparaison n’est nécessaire. Si le texte est vide et le motif non vide, la conclusion est identique. Le motif vide demande un contrat différent et est refusé dans l’atelier. Testez aussi une différence de casse et des répétitions dans le motif : une table qui conserve la première occurrence au lieu de la dernière n’applique plus la formule annoncée. Les textes courts permettent de vérifier les sauts à la main avant toute mesure de performance.

À vous de faire varier les choses

Pilotez les alignements du motif

Entrez un texte court et un motif non vide, puis avancez d’alignement en alignement. Les majuscules et minuscules sont distinctes. Le texte est limité à 60 caractères et le motif à 12 ; les éventuels caractères suivants ne participent pas à cette simulation.

Lire le résultat de l’expérience initiale

Alignement 0 : échec, décalage 3.

Table de dernière occurrence : A:3, B:1, C:2. Après une réussite, le pas de un conserve les chevauchements.

Indice texte	Caractère texte	Indice motif	Caractère motif	Comparaison
3	A	3	A	Égal
2	Z	2	C	Différent

Indice 2

Les indices du texte portent sur les caractères représentés.

Comprendre la correction

La table correcte est B:0, A:3, N:4, E:5. Le décalage demandé vaut max(1,4-3)=1. Avec AB et ABC, aucun alignement complet n’existe et le compte de comparaisons vaut zéro. Avec 🐍A🐍 et 🐍, les occurrences sont 0 et 2. La convention Unicode évite de confondre position de caractère et unité d’encodage.

Les erreurs qui méritent un détour

Mélanger les tables de deux variantes.: La règle du mauvais caractère et les variantes de décalage doivent être annoncées précisément.
Prendre une mesure sur un texte comme preuve de coût général.: Le comportement varie selon texte et motif ; la correction des sauts reste prioritaire.

La fiche à garder

L’essentiel à retenir

Le motif est comparé de droite à gauche.
Le prétraitement guide des décalages justifiés.
La variante étudiée utilise max(1,j-derniere(c)) après un échec.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

Le prochain pas

Coûts en temps et en mémoire

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.