Cours

Chapitre 17 : Recherche textuelle

1. Introduction

Objectif de la recherche textuelle

On considère deux chaînes de caractères, l’une appelée texte et l’autre motif. On cherche dans texte s’il existe une occurrence du motif motif.

Autrement dit, avec les notations de Python, on cherche s’il existe un indice i tel que texte[i:i+len(motif)] == motif.

Plusieurs algorithmes ont été inventés pour résoudre ce problème, un des plus connus est l’algorithme de Knuth, Morris, Pratt, qui ne figure pas au programme. Un autre algorithme, très efficace, est l’algorithme de Boyer et Moore, qui a été inventé en 1977. Boyer et Moore travaillaient alors à l’université d’Austin au Texas en tant qu’informaticiens.

Dans la suite, texte correspond au texte intégral du roman Le Rouge et le Noir de Stendhal, au format txt encodé en UTF-8.

fichier = open("LeRougeEtLeNoir.txt" , "r", encoding="utf-8")
texte = fichier.read()
fichier.close()

Compléter la cellule ci-dessous pour obtenir la taille du texte en carcatères.

print(len(texte))

Avant d’aller plus loin, remarquons qu’il existe une fonction Python qui répond à notre problème : il s’agit de la méthode find de l’objet str. Par exemple, le code ci-dessous renvoie l’indice de la première occurrence du motif Julien trembla dans le texte.

print(texte.find("Julien trembla"))

L’indice retourné est celui de la première lettre du motif dans le texte :

print(texte[162926:162960])

Julien tremblait que sa demande ne

Si le motif recherché n’apparaît pas dans le texte, alors la fonction find renvoie -1.

print(texte.find("Goldorak"))

-1

Une variante de la fonction find prend deux arguments : le second argument est la position de départ dans la recherche.

Compléter le code suivant, utilisant cette variante, pour déterminer le nombre d’occurrences de motif dans texte.

def nbOccurrences(texte, motif):
    compteur = 0
    position = texte.find(motif)
    while position != -1:
        compteur += 1
        position = texte.find(motif, position + 1)
    return compteur

Exécuter le code ci-dessous pour vérifier votre fonction.

assert nbOccurrences(texte, "Julien") == 1908
assert nbOccurrences(texte, "Goldorak") == 0
assert nbOccurrences(texte, "mort") == 178
print("Tests réussis")

Tests réussis

2. Recherche naïve

L’algorithme naïf consiste simplement à comparer un à un, de gauche à droite, les caractères du texte apparaissant dans la fenêtre avec ceux du motif. En cas de non-correspondance on avance simplement la fenêtre d’une unité vers la droite. Par exemple, dans la situation suivante,

on compare le ‘a’ du motif avec le ‘r’ du texte, obtenant immédiatement une différence : on peut avancer la fenêtre en incrémentant i, qui passe de 14 à 15.

Dans la nouvelle fenêtre, le premier caractère coïncide bien :

et on incrémente j pour tester les caractères suivants, ‘d’ et ‘c’ :

On est à nouveau en situation d’échec, et on effectue donc i = i + 1 et j = 0.

Compléter maintenant la fonction cherche_naif ci-dessous :

def cherche_naif(texte, motif):
    n = len(texte)
    p = len(motif)
    resultat = -1
    i = 0
    while i <= n-p and resultat == -1:
        j = 0
        while j < p and texte[i+j] == motif[j]:
            j += 1
        if j == p:
            resultat = i
        i += 1
    return resultat

# Test de la fonction cherche_naif
assert cherche_naif("Julien Sorel", "Julien") == 0
assert cherche_naif("Julien Sorel", "Sorel") == 7
assert cherche_naif("Julien Sorel", "Julienne") == -1
assert cherche_naif(texte, "Julien trembla") == 162926
print("Tests réussis")

Tests réussis

3. Algorithme de Boyer et Moore

On étudie en réalité une version simplifiée de cet algorithme, due à Nigel Horspool, né en Grande-Bretagne, mais citoyen canadien. Il est professeur émérite d’informatique de l’université de Victoria.

La première idée consiste à comparer le motif avec la portion du texte qui apparaît dans la fenêtre de droite à gauche, et non pas de gauche à droite. Ainsi, on fait décroître j à partir de p − 1 (p représente toujours la longueur du motif) jusqu’à trouver que le caractère qui lui fait face dans le texte, c’est-à-dire x = texte[i + j], est différent du caractère y = motif[j] du motif.

La deuxième idée consiste à opérer un décalage de la fenêtre qui varie en fonction de la paire de caractères qui ont révélé la non-correspondance, c’est-à-dire en fonction de (x; y).

Si le caractère x n’apparaît pas dans le motif, alors on peut décaler la fenêtre de p caractères vers la droite.
Si le caractère x apparaît dans le motif (mais pas en dernière position), alors on peut décaler la fenêtre afin de faire coïncider le x du motif et le x du texte.

Exemple “à la main”

Nous considérons ici la recherche du motif ‘dab’ dans le texte ‘abracadabra’.

Avec nos notations, p = 3, n = 11 et la première occurrence du motif dans le texte apparaît en position i = 6.

On commence avec la fenêtre tout à gauche, c’est-à-dire avec i = 0.

abracadabra
dab

Comme on commence à comparer de droite à gauche, c’est pour j = 2 qu’il y a non-correspondance : motif[2]='b' est différent de 'r'=texte[0 + 2].

On note x ='r' le caractère du texte qui ne correspond pas à y ='b' le caractère du motif qui lui fait face.

De combien peut-on décaler la fenêtre ? Comme x n’apparaît nulle part dans le motif, on peut carrément décaler le motif de p = 3 unités vers la droite !

abracadabra
   dab

Ainsi on se retrouve avec i = 3 et le premier échec intervient avec j = 2, où le caractère x =texte[3 + 2]='a' du texte est distinct du caractère face à lui dans le motif, c’est-à-dire y =motif[2]='b'.

Mais à la différence du cas précédent, le caractère x apparaît bien dans le motif. On déplace donc la fenêtre d’une unité vers la droite.

Voici la prochaine étape :

abracadabra
    dab

i = 4; x ='d' ; y ='b' : on décale de 2 pour faire correspondre les deux ‘d’.

Finalement avec i = 6, on trouve la première occurrence du motif et l’algorithme se termine.

abracadabra
      dab

Exercice

Dérouler à la main l’exécution de l’algorithme de Boyer et Moore pour la recherche du motif "cavalier" dans le texte "“Le cheval court, le cavalier se vante”.

Programmation de l’algorithme

On commence par calculer un dictionnaire dont les clés sont les caractères du motif et les valeurs l’indice de la position la plus à droite du caractère.

C’est ce que réalise la fonction calculeADroite.

Dans le cas du mot maman, par exemple, ce dictionnaire sera : {'m': 2, 'a': 3, 'n': 4}.

Compléter le code de la fonction calculeADroite.

def calculeADroite(motif):
    p = len(motif)
    dico = {}
    for j in range(p):
        dico[motif[j]] = j
    return dico

# test de la fonction calculeADroite
assert calculeADroite("Julien") == {'J': 0, 'u': 1, 'l': 2, 'i': 3, 'e': 4, 'n': 5}
assert calculeADroite("maman") == {'m': 2, 'a': 3, 'n': 4}
print("Tests réussis")

Tests réussis

On peut maintenant compléter la fonction recherche_BMH pour appliquer les idées ci-dessus : on parcourt le motif de droite à gauche et on calcule le décalage en utilisant le dictionnaire créé par la fonction précédente.

def recherche_BMH(texte, motif):
    n = len(texte)
    p = len(motif)
    dico = calculeADroite(motif)
    i = 0
    while i <= n - p:
        j = p - 1
        while j >= 0 and texte[i+j] == motif[j]:
            j -= 1
        if j == -1:
            return i
        else:
            if texte[i+j] in dico:
                i += max(1, j - dico[texte[i+j]])
            else:
                i += j + 1
    return -1

# test de la fonction recherche_BMH
assert recherche_BMH("Julien Sorel", "Julien") == 0
assert recherche_BMH("Julien Sorel", "Sorel") == 7
assert recherche_BMH("Julien Sorel", "Julienne") == -1
assert recherche_BMH(texte, "Julien trembla") == 162926
print("Tests réussis")

Tests réussis

4. Comparaison expérimentale des deux algorithmes

À l’aide du module timeit de Python, on peut comparer les performances des deux algorithmes.

# Comparaison des deux algorithmes avec timeit

import timeit
# Algorithme naïf
temps_naif = timeit.timeit("cherche_naif(texte, 'Julien trembla')", globals=globals(), number=100)
print("Temps de l'algorithme naïf :", temps_naif)

# Algorithme de Boyer-Moore-Horspool
temps_BMH = timeit.timeit("recherche_BMH(texte, 'Julien trembla')", globals=globals(), number=100)
print("Temps de l'algorithme BMH :", temps_BMH)

Temps de l'algorithme naïf : 3.2481508999990183
Temps de l'algorithme BMH : 0.6167228000049363