Vers l'algorithme de Boyer - Moore

L'algorithme de Boyer - Moore propose un algorithme performant qui a nécessité des optimisations de l'algorithme naïf.

La première est celle proposée par Nigel Horspool : on compare depuis la fin du motif.

Question

Ré-écrire l'algorithme naïf (recherche de positions) en comparant non pas de gauche à droite, mais de droite à gauche...

1
def positions_naif(texte, motif):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: list - Tableau des positions où trouver motif dans texte
6
    """
7
    n = len(texte)
8
    p = len(motif)
9
    i = 0
10
    lst_indices = []
11
    while i <= n-p:
12
        k = 0
13
        while k < p and texte[i + k] == motif[k]:
14
            k += 1
15
        if k == p:
16
            lst_indices.append(i)
17
        i += 1
18
    return lst_indices

Indice

On ne part pas de i = 0 mais de i = len(motif) - 1

Indice

Les seules parties à modifier sont repérées par des ...

1
def positions_naif_droite_gauche(texte, motif):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: list - Tableau des positions où trouver motif dans texte
6
    """
7
    n = len(texte)
8
    p = len(motif)
9
    i = p-1
10
    lst_indices = []
11
    while ... : 		# On va un peu plus loin dans le texte...
12
        k = 0
13
        while k < p and ... :	# Prenez quelques exemples pour trouver une généralisation
14
            k += 1
15
        if k == p:
16
            lst_indices.append(...)
17
        i += 1
18
    return lst_indices

Solution

1
def positions_naif_droite_gauche(texte, motif):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: list - Tableau des positions où trouver motif dans texte
6
    """
7
    n = len(texte)
8
    p = len(motif)
9
    i = p-1
10
    lst_indices = []
11
    while i <= n-1:
12
        k = 0
13
        while k < p and texte[i-k] == motif[p-1-k]:
14
            k += 1
15
        if k == p:
16
            lst_indices.append(i-p+1)
17
        i += 1
18
    return lst_indices

Intéressons-nous au temps de recherche...

Question

Appliquer ce nouvel algorithme aux 3 recherches du roman « Les Misérables ». Que dire...

Indice

Quelques éléments de code :

1
import time
2
3
4
with open("Les_Miserables.txt") as f:
5
    roman = f.read().replace('\n', ' ')
6
7
t0 = time.time()
8
motif = "maison"
9
print(f"recherche naïve de '{motif}'")
10
print(positions_naif(roman, motif))
11
print("Le temps (en naïf) mis est de", time.time()-t0)
12
Solution
Il n'y a pas de différences, voire c'est un peu plus long... On peut donc en conclure que cette première approche fonctionne impérativement avec la 2ème proposition de Horspool : la règle du mauvais caractère.