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

1.2 Modification de l'algorithme

Exercice 1

ÉnoncéCorrection

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.

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:
    texte = f.read().replace('\n', ' ')

1.3.2 Vérification et mesure du temps de recherche

Exercice 2

ÉnoncéCorrection

1. Testez la validité de vos réponses en comparant avec les résultats donnés par la fonctionnalité Ctrl-F proposée par votre navigateur
2. Mesurez le temps d'exécution de votre algorithme à l'aide du module time.

à faire

2. Algorithme de Boyer-Moore-Horspool

Illustration de l'algorithme

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

2.1 Principe

2.2 Implémentation

---

Dernière mise à jour: 22 août 2022