Chapitre 17 : Recherche textuelle.

Introduction :

L'algorithme Boyer-Moore, introduit en 1977 par Robert S. Boyer et J Strother Moore, est conçu pour rendre la recherche de sous-chaînes dans un texte plus rapide.

Il utilise deux heuristiques principales : la mauvaise correspondance, qui permet de sauter plusieurs caractères lorsqu'un caractère ne correspond pas, et le bon suffixe, qui ajuste la recherche en fonction des parties déjà appariées.

Cet algorithme est particulièrement efficace sur les grands textes et a influencé de nombreuses méthodes de recherche optimisée.

1. Définition:

Le fait de faire "une recherche textuelle" signifie chercher une séquence ordonnée de caractères dans une chaîne de caractères plus grande.

2. Activité:

Programmer la fonction recherche_textu_basique(sequence,texte) qui prend en paramètres deux strings.

sequence désigne une chaîne de caractère cherchée.
texte désigne une longue chaîne de caractère.

Cette fonction affichera la position des éléments de séquence dans la liste si elle y est présente puis retournera un booléen selon son appartenance ou non.

Par exemple, recherche_textu_basique("coucou","Bonjour, coucou!") affichera [9,14] et retournera True.

3. Boyer Moore:

L'algorithme de Boyer Moore permet d'optimiser cette recherche.

Il fonctionne à l'aide d'un pré-traitement de la séquence à chercher.

Une vidéo Youtube expliquant cela:

4. Construction du dictionnaire:

Programmer la fonction constru_dico(sequence) qui prend en paramètre un string sequence.

Cette fonction retournera le dictionnaire des décalages à faire de l'algorithme Boyer-Moore.

Par exemple, constru_dico("coucou") retournera {'c': 2, 'o': 1, 'u': 3}.

5. Algorithme:

Compléter la fonction recherche_BOYER_MOORE(sequence,texte) qui prend en paramètres deux strings.

Cette fonction retournera un booléen selon l'appartenance ou non de sequence à texte.

Par exemple, recherche_BOYER_MOORE("coucou","Bonjour, coucou!") retournera True.

def recherche_BOYER_MOORE(sequence,texte):
    dico=...........
    if .................: #si la longueur de la sequence est plus longue que le texte, on renvoie Faux.
        return False
    curseur=...............     #on place le curseur au bon endroit
    while ..................:   #tant qu'on n'est pas au bout
        correspondance=True     #on part du principe qu'il y a une correspondance
        indice_sequence=...........
        indice_texte=.............
        while correspondance and .................:
            if sequence[..........]!=texte[..........]: #si le caractère ne correspond pas
                correspondance=False 
            else:
                ....................   # on modifie indice_sequence
                ....................   #on modifie indice_texte
        if correspondance:   #s'il y a toujours correspondance
            return .......
        if texte[curseur] in dico.keys(): #si dans le dictionnaire
            curseur+=................
        else: #si n'est pas dans le dictionnaire
            curseur+=................
    return False