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:

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

Pour rechercher un motif M de longueur p dans un texte T de longueur n, on a donc besoin:

• d'un indice i qui va de 0 à n - p qui indique le début de la fenêtre de recherche
• d'un indice k qui va de 0 à p - 1 pour vérifier la correspondance entre les indices dans le texte et le motif.

Si il existe un rang i pour lequel M[k] == T[i + k] pour tout k, alors on en déduit la présence de M au rang i dans le texte T.

🐍 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 <= .....................:
        k = 0
        while k < len(motif) and texte[i + k] == motif[k]:
            k += 1
        if k == ...........:
            indices.append(i)
        i += 1

    return indices

Exercice

1. Compléter les parties manquantes.
2. Tester cette fonction sur des exemples simples.
3. Tester cette fonction sur le roman et les trois mousquetaires
4. À 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 p), 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 p la complexité de cet algorithme.

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!

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

Cet algorithme permet d'améliorer significativement la complexité de recherche.L'idée est de décaler le motif vers la droite d'une valeur qui n'est pas toujours 1.

Naturellement, la comparaison des lettres entre M et T s'effectue de gauche à droite. Nous allons maintenant comparer de droite à gauche et surtout décaler la fenêtre de recherche en fonction de la paire de caractères qui a révélé la non correpondance.

Décrivons étape par étape le processus sur un exemple: rechercher le motif MAISON dans une phrase.

La correspondance n'est pas bonne entre le A et le N. Décalons de 4 rangs pour que la correspondance le soit puisque la lettre A est bien présente dans le motif.

Les dernières lettres (F et N) ne correspondent toujours pas et il faut donc redécaler le motif. Mais le F n'étant pas présent dans le motif, on peut décaler de 6 pour tester une nouvelle correspondance:

Toujours pas de correspondance avec la dernière lettre mais le décalage est de 5 car le M se trouve aussi dans le motif.

Il y a maintenant une correspondance entre les lettres. L'algorithme se termine... En résumé:

Un décalage qui n'est plus 1

On décale donc le motif d'une valeur qui dépend du contenu de ce motif.

Appellons let le caractère du texte qui ne correspond pas. Alors:

• si let n'est pas dans le motif, on décale de la longueur du motif.
• si let est dans le motif , on décale en fonction de la position de let dans le motif.

On va donc 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 # la valeur initiale de i 
    while i < len(texte): # i s'arrête donc à len(texte) - 1
        k = 0
        while k < len(motif) and motif[len(motif) - 1 - k] == texte[i - k]: 
            k += 1
        if k == len(motif): # coorespondance
            indices.append(i - len(motif) + 1)
            i += 1 
        else: # on décale
            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.