Aller au contenu

T3.3 Recherche textuelle⚓︎

1. Recherche naïve et efficacité⚓︎

Illustration de l'algorithme

Exercice 1: BNS 2024, sujet 21, exercice 1

Écrire une fonction recherche_motif qui prend en paramètre une chaîne de caractères motif non vide et une chaîne de caractères texte et qui renvoie la liste des positions de motif dans texte. Si motif n’apparaît pas, la fonction renvoie une liste vide.

Exemples:

>>> recherche_motif("ab", "")
[]
>>> recherche_motif("ab", "cdcdcdcd")
[]
>>> recherche_motif("ab", "abracadabra")
[0, 7]
>>> recherche_motif("ab", "abracadabraab")
[0, 7, 11]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def recherche_motif(motif:str, texte:str) -> list:
    """
    Renvoie une liste, éventuellement vide, des positions de motif dans texte.
    """
    positions = []
    i = 0
    while i <= len(texte)-len(motif):
        j = 0
        while j < len(motif) and texte[i+j] == motif[j] :
            j += 1
        if j == len(motif):
            positions.append(i)
        i += 1
    return positions

assert recherche_motif("ab", "") == []
assert recherche_motif("ab", "cdcdcdcd") == []
assert recherche_motif("ab", "abracadabra") == [0, 7]
assert recherche_motif("ab", "abracadabraab") == [0, 7, 11]

Exercice 2: 1 ecicrexe ,12 tejus ,4202 SNB

Modifier la fonction précédente pour quelle effectue la recherche «à l'envers», c'est-à-dire en partant de la fin de motif.

Illustration de l'algorithme

Cette fonction permet de rechercher n'importe quelle chaîne de caractères dans ... n'importe quelle chaîne de caractères. On utilise la plupart du temps (avec souvent le raccourci CTRL+F) cette recherche pour chercher un fragment de code (un nom de variable à remplacer par exemple) dans un programme ou bien pour chercher une occurence d'un mot dans une page web.

Pour mesurer l'efficacité de cet algorithme naïf, nous allons faire une recherche dans le texte intégral de L'Avare, de Molière, mis à disposition légalement par le Projet Gutenberg .

Exercice 3

Mesurer le temps d'exécution de la fonction recherche_motif sur 3 chaînes de caractères:

  • une courte, dont on est sûr.e qu'elle apparaît dans le texte;
  • une (plus) longue, dont on est sûr.e qu'elle apparaît dans le texte (par exemple 'Il faut, pour me donner conseil, que je voie ma cassette.');
  • une dernière dont on est sûr.e qu'elle n'apparaît pas dans le texte (par exemple 'Iron Man', 'Gouygou', "le gras c'est la vie.", etc.).

On peut utiliser pour cela le code suivant (à compléter):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
import time

with open('......') as f:
    piece = f.read().replace('\n', ' ') # pour obtenir une seule chaîne de caractères (certes très longue)

def chrono(motif, texte):
    t0 = time.time()
    recherche_naive(motif, texte)
    return time.time() - t0

for m in [...]:
    print(chrono(..., ...))

2. Algorithme de Boyer-Moore(-Horspool)⚓︎

2.1 Principe⚓︎

L'idée est d'améliorer le code précédent (celui où 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 est dans le motif (sauf à la dernière place du 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.

  • si X n'est pas dans le motif, il est inutile d'avancer "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, donc de la longueur du motif cherché.

Illustration de l'algorithme

2.2 Prétraitement⚓︎

Dans cet algorithme, on a donc besoin de savoir si un caractère appartient ou non au motif, et si oui, quel est le rang de sa dernière occurence dans le motif. On exclut le dernier caractère du motif cependant, car sinon cela poserait un problème lors du décalage (on décalerait de 0...).

Exercice 4

Écrire une fonction dico_lettres qui prend en paramètre une chaîne de caractères mot et qui renvoie un dictionnaire associant à chaque caractère de mot (sauf le dernier) son dernier indice dans mot.

Exemple:

>>> dico_lettres('MARGUERITE')
{'M': 0, 'A': 1, 'R': 6, 'G': 3, 'U': 4, 'E': 5, 'I': 7, 'T': 8}

1
2
3
4
5
def dico_lettres(mot):
    dico = {}
    for i in range(len(mot)-1):
        dico[mot[i]] = i
    return dico

2.3 Implémentation de l'algorithme de BMH⚓︎

Il s'agit maintenant de modifier la recherche naïve «à l'envers», en avançant non plus l'indice de recherche i systématiquement de 1, mais du bon nombre de caractères en fonction de l'apparition ou non du caractère dans le motif.

Un exemple à la main pour commencer...

Appliquer l'algorithme de BMH à la main (dans un tableau) pour la recherche du motif 'ATGCGA' dans le texte 'AACATATGXGATGCGAGGTCGTAGT'.

Exercice 5

  1. Compléter la fonction de recherche par l'algorithme de Boyer-Moore-Horspool.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    def recherche_BMH(motif:str, texte:str) -> list:
    """
    Renvoie une liste, éventuellement vide, des positions de motif dans texte.
    """
    dico = ...
    positions = []
    i = 0
    while i <= len(texte)-len(motif):
        j = len(motif) - 1
        while j >= 0 and texte[i+j] == motif[j] :
            j -= 1
        if j == -1:
            positions.append(i)
            i += ...
        else:
            if ... :
                i += ...
            else:
                i += ...
    return positions

  2. Reprendre les mesures de temps d'éxécution et comparer avec la recherche naïve.