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é : Recherche textuelle basique

Programmer la fonction recherche_textu_basique(sequence, texte, affiche_indices=False) qui prend en paramètres deux chaînes de caractères :

sequence : la sous-chaîne que l’on cherche ;
texte : la longue chaîne dans laquelle on cherche.
affiche_indices est un booléen.

La fonction doit retourner True si sequence est présente dans texte et False sinon.

Exemple : recherche_textu_basique("coucou", "Bonjour, coucou!") doit retourner True.

Si la séquence n’est pas trouvée la fonction retourne False.

Si le paramètre affiche_indices est égal à True, la fonction affichera une liste de deux nombres de type int correspondant à l'indice du début et à l'indice de fin où a été trouvé la séquence dans le texte en cas de succès.

def recherche_textu_basique(sequence, texte, affiche_indices=False): """ Affiche [debut, fin] si 'sequence' est trouvée dans 'texte', sinon []. Retourne True si trouvée, False sinon. """ if len(sequence) > len(texte): # si la séquence est plus longue que le texte return ... # à compléter sequence = "NsI" texte = "nsInsiNsiNNNsiNSInsnsnisinSINSinSInSInSniSinISNiNSniSNiNSIniSNINSINSnsinISniS" print(recherche_textu_basique(sequence, texte, True))

Tests :

Affichage :

Console:

>>>

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 explique 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 (heuristique du « mauvais caractère » version Horspool) pour l’algorithme de Boyer–Moore : pour chaque caractère apparaissant dans sequence sauf la dernière position, on associe la distance entre cette position (la plus à droite possible) et la dernière case (indice len(sequence)-1).

Exemple : constru_dico("coucou") doit renvoyer {'c': 2, 'o': 1, 'u': 3}.

def constru_dico(sequence): """ Retourne le dictionnaire des décalages pour Boyer-Moore (Horspool). Règle : pour chaque caractère de sequence **avant** la dernière position, on prend sa occurrence la plus à droite et on stocke (len(sequence)-1 - index). """ dico = ... m = len(sequence) # On parcourt jusqu'à l'avant-dernière position (la dernière est exclue) for i in range(...): ... = ... return ... sequence = "coucou" print(f"La sequence {sequence} est associée au dictionnaire : {constru_dico(sequence)} .")

Tests :

Affichage :

Console:

>>>

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.

# COPIER-COLLER ICI LA FONCTION constru_dico(sequence) DE L EXERCICE PRECEDENT AVANT D ECRIRE LA RECHERCHE. def recherche_BOYER_MOORE(sequence, texte): dico = ... if ...: # si sequence est plus long que le texte return False # on démarre le curseur sur l'index du dernier caractère de la séquence curseur = len(sequence) - 1 # tant que le curseur ne dépasse pas la fin du texte while ...: correspondance = True indice_sequence = ... # dernier index de sequence indice_texte = ... # position courante dans le texte # on remonte de droite à gauche tant que ça matche while correspondance and ...: if sequence[...] != texte[...]: correspondance = False else: ... ... if correspondance: return ... # sinon on décale selon le mauvais caractère if texte[curseur] in dico.keys(): curseur += ... else: curseur += ... return False sequence = "NsI" texte = "nsInsiNsiNNNsiNSInsnsnisinSINSinSInSInSniSinISNiNSniSNiNSIniSNINSINSnsinISniS" print(recherche_BOYER_MOORE(sequence, texte))

Tests :

Affichage :

Console:

>>>

6. Exercice :

Ce fichier contient l'ensemble du roman "Le Horla" de "Guy de Maupassant".

Le code suivant permet d'ouvrir ce genre de fichier et de mettre le contenu du roman dans la variable contenu.

import os

os.chdir("u:\\") # à modifier

with open("le_horla_guy_de_maupassant.txt", "r", encoding="utf-8") as f:
    contenu = f.read()

Dans un IDE python, tester les fonctions vues précédemment sur ce roman.