Aller au contenu

Recherche textuelle⚓︎

image

image

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 ❤

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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⚓︎

1
2
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 ?

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)

retour console :

[7264, 9090, 9547, 9745, 10936, 17820, 23978, 38192, 41639, 41651, 41840, 42493, 48028, 48393, 51448, 53353, 70867, 72692, 72768, 75608, 77855, 108489, 115739, 130629, 132983, 138870, 143681, 144600, 153114, 155973, 158709, 160700, 163649, 169164, 169181, 171761, 171967, 182642, 186413, 190534, 219378, 220314, 224518, 225098, 227579, 296302, 345108, 345893, 346740, 349677, 359727, 362025, 389945, 395690, 434118, 438068, 457795, 457886, 464696, 469403, 501768, 514980, 520667, 520878, 520926, 520968, 522707, 529329, 598128, 601390, 645915]
0.21963715553283691
[651731]
0.21761441230773926
[]
0.22150230407714844

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 ?⚓︎

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 : image

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def presqueBMH(texte, 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
    return indices

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, donc de la longueur du motif cherché.
  • 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.
Illustration de l'algorithme

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

2.2 Implémentation⚓︎

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...)

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
21
22
23
24
def dico_lettres(mot):
    d = {}
    for i in range(len(mot)-1):
        d[mot[i]] = i
    return d

def BMH(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]: #(1)
            k += 1
        if k == len(motif): #(2)
            indices.append(i-len(motif)+1)
            i += 1 #(3)
        else:
            if texte[i-k] in dico: (#4)
                i = max(i - k  + len(motif) - dico[texte[i-k]] - 1, i+1) #(5)
            else:
                i = i - k + len(motif) #(6)

    return indices
  1. On remonte le motif à l'envers, tant qu'il y a correspondance et qu'on n'est pas arrivés au début du motif
  2. Si on est arrivés au début du motif, c'est qu'on a trouvé le mot.
  3. On a trouvé le motif, mais attention, il ne faut pas trop se décaler sinon on pourrait rater d'autres occurences du motif (pensez à la recherche du motif «mama» dans le mot «mamamamama»). On se décale donc de 1.
  4. On s'est arrêté avant la fin, sur une lettre présente dans le mot : il va falloir faire un décalage intelligent.
  5. On décale juste de ce qu'il faut pour mettre en correspondance les lettres, en évitant le retour en arrière (d'où le max pour se décaler au moins de 1)
  6. La lettre n'est pas dans le motif : on se positionne juste après elle.

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 4

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

t0 = time.time()
motif = "maison"
print(BMH(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(BMH(roman, motif))
print(time.time()-t0)

t0 = time.time()
motif = "parcoursup"
print(BMH(roman, motif))
print(time.time()-t0)

retour console :

[7264, 9090, 9547, 9745, 10936, 17820, 23978, 38192, 41639, 41651, 41840, 42493, 48028, 48393, 51448, 53353, 70867, 72692, 72768, 75608, 77855, 108489, 115739, 130629, 132983, 138870, 143681, 144600, 153114, 155973, 158709, 160700, 163649, 169164, 169181, 171761, 171967, 182642, 186413, 190534, 219378, 220314, 224518, 225098, 227579, 296302, 345108, 345893, 346740, 349677, 359727, 362025, 389945, 395690, 434118, 438068, 457795, 457886, 464696, 469403, 501768, 514980, 520667, 520878, 520926, 520968, 522707, 529329, 598128, 601390, 645915]
0.06359553337097168
[651731]
0.01853322982788086
[]
0.037064313888549805

On constate quelque chose de remarquable (et qui peut être à première vue contre-intuitif) :

Plus le motif recherché est long, plus la recherche est rapide.