Aller au contenu

Recherche textuelle⚓︎

image image image

1. Recherche naïve⚓︎

Illustration de l'algorithme

image

1.1 Premier algorithme⚓︎

codes à trous

Algorithme de recherche naïve ❤

🐍 Script Python
 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 :

🐍 Script Python
>>> 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.

🐍 Script Python
 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⚓︎

🐍 Script Python
1
2
with open("Les_Miserables.txt" , encoding='utf-8') 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 ?

🐍 Script Python
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 :

🐍 Script Python
[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 ?⚓︎

Illustration de l'algorithme en partant à l'envers

image

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

image

🐍 Script Python
 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

image

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 :

🐍 Script Python
>>> dico_lettres("MAURIAC")
{'M': 0, 'A': 5, 'U': 2, 'R': 3, 'I': 4}
Correction
🐍 Script Python
1
2
3
4
5
def dico_lettres(mot):
    d = {}
    for i in range(len(mot)-1):
        d[mot[i]] = i
    return d

2.2.2 Boyer-Moore-Horspool⚓︎

codes à trous

Algorithme de Boyer-Moore-Horspool ❤

🐍 Script Python
 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 :

🐍 Script Python
>>> 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 ?

🐍 Script Python
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 :

🐍 Script Python
[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.