Recherche textuelle⚓︎

1. Recherche naïve⚓︎

Illustration de l'algorithme

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

1.1 Premier algorithme⚓︎

Algorithme de recherche naïve

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

Exemple d'utilisation :

>>> recherche_naive("une magnifique maison bleue", "maison")
[15]
>>> recherche_naive("une magnifique maison bleue", "nsi")
[]
>>> recherche_naive("une magnifique maison bleue", "ma")
[4, 15]

1.2 Modification de l'algorithme⚓︎

Exercice 1

Re-écrire l'algorithme précédent en s'arrêtant dès qu'une occurrence de motif est trouvée dans texte.

La fonction renverra uniquement un booléen.

Correction

def recherche_naive_bool(texte, motif):
    '''
    renvoie un booléen indiquant la présence ou non de
    la chaîne motif dans la chaîne texte.
    '''
    trouve = False
    i = 0
    while i <= len(texte) - len(motif) and not trouve:
        k = 0
        while k < len(motif) and texte[i+k] == motif[k]:
            k += 1
        if k == len(motif):
            trouve = True
        i += 1

    return trouve

1.3 Application à la recherche d'un motif dans un roman⚓︎

Le Projet Gutenberg permet de télécharger légalement des ouvrages libres de droits dans différents formats.

Nous allons travailler avec le Tome 1 du roman Les Misérables de Victor Hugo, à télécharger ici au format txt.

1.3.1 Récupération du texte dans une seule chaîne de caractères⚓︎

with open('Les_Miserables.txt') as f:
    roman = f.read().replace('\n', ' ')

1.3.2 Vérification et mesure du temps de recherche⚓︎

Exercice 2

À l'aide du module time, mesurer le temps de recherche dans Les Misérables d'un mot court, d'une longue phrase (présente dans le texte), d'un mot qui n'existe pas. Que remarquez-vous ?

Correction

import time

with open('Les_Miserables.txt') as f:
    roman = f.read().replace('\n', ' ')


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

t0 = time.time()
motif = 'maison'
print(recherche_naive(roman, motif))
print(time.time()-t0)

t0 = time.time()
motif = 'La chandelle était sur la cheminée et ne donnait que peu de clarté.'
print(recherche_naive(roman, motif))
print(time.time()-t0)

t0 = time.time()
motif = 'parcoursup'
print(recherche_naive(roman, motif))
print(time.time()-t0)

On remarque que le temps de recherche est semblable, quel que soit le motif cherché.

2. Vers l'algorithme de Boyer-Moore : et si on partait à l'envers ?⚓︎

Illustration de l'algorithme en partant à l'envers

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

Exercice 3

Re-écrire l'algorithme de recherche naïve mais en démarrant de la fin du motif et non du début.

Certes, c'est pour l'instant très artificiel, mais :

3. Algorithme de Boyer-Moore-Horspool⚓︎

2.1 Principe⚓︎

L'idée est d'améliorer le code précédent (celui on parcourt le motif à l'envers) en sautant directement au prochain endroit potentiellement valide.

Pour cela on regarde le caractère X du texte sur lequel on s'est arrêté (car X n'était pas égal au caractère de rang équivalent dans le motif):

si X n'est pas dans le motif, il est inutile de se déplacer "de 1" : on retomberait tout de suite sur X, c'est du temps perdu. On se décale donc juste assez pour dépasser X.
si X est dans le motif, on va regarder la place de la dernière occurence de X dans le motif et de déplacer de ce nombre, afin de faire coïncider le X du motif et le X du texte.

Illustration de l'algorithme

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

2.2 Implémentation⚓︎

2.2.1 Fonction préparatoire⚓︎

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

Exercice 4

Écrire la fonction dico_lettres.

Exemple d'utilisation :

>>> dico_lettres("MAURIAC")
{'M': 0, 'A': 5, 'U': 2, 'R': 3, 'I': 4}

2.2.2 Boyer-Moore-Horspool⚓︎

codes à trous

Exemple d'utilisation :

>>> BMH("une magnifique maison bleue", "maison")
[15]
>>> BMH("une magnifique maison bleue", "nsi")
[]
>>> BMH("une magnifique maison bleue", "ma")
[4, 15]

Exercice 5

Reprendre les mesures effectuées sur Les Misérables, mais cette fois avec l'algorithme BMH. Que remarquez-vous ?