Recherche d'un motif dans un texte

Motivation

Il existe un raccourci clavier universel, Ctrl + F , qui permet la recherche d'un mot dans un texte, dans une page web ou tout autre document...

Derrière cette combinaison de touche se cachent des algorithmes efficaces que nous allons en partie découvrir dans ce cours...

Comment ça marche?

Comment rechercher un mot (nous dirons un motif...) dans un texte bien plus grand que le motif recherché?

Retour en classe de première NSI

L'opérateur in permet de tester la présence d'un élément dans un itérable. En particulier, on peut l'utiliser pour rechercher un motif dans une chaîne.

🐍 Script Python

phrase_de_test = "Une phrase qui dit n'importe quoi, juste pour tester la présence de quoi "
test = 'quoi' in phrase_de_test

La variable test est de type booléen: elle retourne True car le motif quoi est présent dans le texte phrase_de_test.

🐍 Script Python

>>>print(test)
True

Néanmoins, cet opérateur ne teste que la présence du motif quoi dans la chaîne de caractères phrase_de_test et en particulier, il ne précise pas combien de fois il a été trouvé et encore moins où il a été trouvé!

L'instruction help("") dans une console Python affiche des méthodes de la classe string: la méthode count et find semblent intéressantes...

Les méthodes find et count

• La méthode count compte le nombre d'occurrences du motif recherché dans le texte de référence.
• La méthode find retourne le plus petit index du texte auquel se trouve le motif et retourne -1 sinon..

🐍 Script Python

phrase_de_test = "une phrase qui dit n'importe quoi, juste pour tester la présence de quoi "
cpt = phrase_de_test.count('quoi')
rang = phrase_de_test.find('quoi')

La variable cpt vaut alors 2 et la variable rang vaut 29!

On considère un motif M et un texte T. L'objectif est la création d'un programme qui renvoie tous les index de T où se situent M en cas de détection de M dans T, en utilisant seulement les méthodes count,find rappelées ci-dessus.

Exercice

Écrire une fonction recherche_mot qui prend en paramètres M et T qui retourne la liste des index définis ci-dessus ou une liste vide si M n'est pas dans T.

Tester votre fonction sur des exemples très simples.

Info

Le site Gutenberg contient de nombreux ouvrages libres de droit.

Exercice

1. Télécharger sur le site Gutenberg, le roman Les trois mousquetaires d'Alexandre Dumas sous le format txt avec l'encodage UTF-8.
2. Ouvrez le fichier en lecture par la méthode fichier = open('troismousquetaires.txt','r', encoding = 'UTF-8').
3. Athos, Porthos et Aramis sont les trois mousquetaires et d'Artagnan le personnage principal: qui des trois mousquetaires a été le plus cité dans le roman?

Un algorithme de recherche simple

Pour éviter d'utiliser les méthodes count et find (qui font appel à des algorithmes mystérieux...), on va reprendre l'idée de comparer lettre par lettre, motif et texte, pour voir si il y a correspondance. Voici la proposition d'un algorithme qu'on appellera naïf:

Vous pouvez contrôler le déroulement de l'animation en la survolant avec la souris.

On décale de 1 à chaque fois le motif pour voir la correspondance dans le texte...

🐍 Script Python

def recherche_naive(texte, motif):
    """
    renvoie la liste des indices (éventuellement vide) des occurrences de
    de la chaîne motif dans la chaîne texte.
    """
    indices = []
    i = 0
    while i <= len(texte) - len(motif):
        k = 0
        while k < len(motif) and texte[i + k] == motif[k]:
            k += 1
        if k == len(motif):
            indices.append(i)
        i += 1

    return indices

Exercice

1. Tester cette fonction sur des exemples simples.
2. Tester cette fonction sur le roman et les trois mousquetaires
3. À l'aide du module time, mesurer le temps de recherche de chaque mousquetaire. Que remarquez-vous?

Complexité de l'opération

On détermine la complexité dans le pire des cas de cet algorithme, en déterminant le nombre de comparaisons de lettres. On appelle n (respectivement m), le nombre de caractères du texte (respectivement du motif).

Exercice

1. Quel est le pire des cas?
2. Déterminer en fonction de n et m la complexité de cet algorithme.

Amélioration de l'algorithme naïf

En général, on se contente de savoir si un motif est dans un texte ou non.

Exo

Modifier la fonction recherche_naive pour qu'elle retourne le booléen True dès qu'elle trouve le motif dans le texte et False sinon.

Pour comparer la présence du motif dans le texte, nous avons comparé la premier lettre du motif, puis éventuellement la seconde, etc... Nous allons changer de stratégie!

Exo

Re-écrire l'algorithme de recherche naïve mais en démarrant de la fin du motif et non du début. La comparaison se fera alors de droite à gauche!

L'algorithme de Boyer-Moore, version simplifée de Horspol:

L'idée est de décaler le motif vers la droite d'une valeur qui n'est pas toujours 1.

On va d'abord coder une fonction dico_lettres qui renvoie un dictionnaire associant à chaque lettre de mot (paramètre d'entrée) son dernier rang dans le mot. On exclut la dernière lettre, qui poserait un problème lors du décalage (on décalerait de 0...)

🐍 Script Python

def dico_lettres(mot):
    d = {}
    for i in range(len(mot) - 1):
        d[mot[i]] = i
    return d

def boyer_moore(texte, motif):
    dico = dico_lettres(motif)
    indices = []
    i = len(motif) - 1
    while i < len(texte):
        k = 0
        while k < len(motif) and motif[len(motif) - 1 - k] == texte[i - k]: 
            k += 1
        if k == len(motif): 
            indices.append(i - len(motif) + 1)
            i += 1 
        else:
            if texte[i - k] in dico: 
                i = max(i - k  + len(motif) - dico[texte[i - k]] - 1, i + 1) 
            else:
                i = i - k + len(motif) 

    return indices

Exo

Reprendre les tests effectués sur le roman avec la fonction précédente et comparez les résultats.