Recherche d'un motif

Exercice 3 du TP2

On dispose d'un texte, par exemple un roman, et on cherche dans cette chaîne, un motif, par exemple un mot ou une partie de mot, une expression.

Il s’agit de savoir si le motif apparaît dans la chaîne et si oui, éventuellement, où et combien de fois ?

On implémente ici un algorithme naïf qui consiste à chercher l'occurrence du premier caractère du motif dans le texte, puis lorsque on est dans ce cas, regarder ce qu'il en est du deuxième caractère du motif avec le caractère suivant du texte et ainsi de suite, en cas de succès, jusqu'à épuisement du motif.

Dans la version la plus simple, on retourne un booléen qui représente la présence ou pas du motif dans le texte. Deux variantes.

variante while

def recherche(texte, motif):
    n = len(texte)
    p = len(motif)
    if n < p:
        return False
    for i in range(n - p + 1):
        if texte[i] == motif[0]:
            j = 1
            while j < p and texte[i+j] == motif[j]:
                j += 1
            if j == p:
                return True
    return False

variante for

def recherche(texte, motif):
    n = len(texte)
    p = len(motif)
    if n < p:
        return False
    for i in range(n - p + 1):
        echec = False
        for j in range(p):
            if texte[i+j] != motif[j]:
                echec = True
                break
        if not echec:
            return True
    return False

On préfère en général la version for car une boucle for est plus sûre qu'une boucle while. En effet, une boucle while court toujours le risque, si on a fait une erreur, de se répéter indéfiniment. C'est pourquoi quand on on vérifie qu'un programme fonctionne correctement, on fait toujours très attention aux while.

Justifier le n - p + 1 en ligne 6 ?
Expliquer le rôle de la 2e boucle.
Justifier que la fonction renvoie True quand le motif est trouvé.
Quels sont les coûts de cet algorithme, dans le meilleur des cas et dans le pire des cas ?
Modifier la fonction recherche pour qu’en cas de présence du motif dans le texte, elle renvoie le nombre d’occurrences de motif dans texte et tous les indices d'apparition.

Conseil de rédaction de code : l'algorithme proposé imbrique de nombreuses structures for, if… Dans la version for, le break en ligne 9 est décalé de 4 indentations. Cela peut devenir difficile à lire. Un conseil élémentaire de programmation est de faire appel à des fonctions annexes aussi souvent que possible.

Dans notre cas, la première boucle, sur i, consiste à tester toutes les positions possibles ; la deuxième boucle, sur j, consiste à tester si le motif est bien présent à partir de la position i.

On pourrait déplacer le travail de la seconde boucle dans une fonction ad-hoc dont le rôle serait précisément de tester si on trouve motif dans texte à partir d'un certain indice de texte.

def motif_est_a_la_position(texte, motif, pos):
    p = len(motif)
    for j in range(p):
        if texte[pos+j] != motif[j]:
            return False
    return True

def recherche(texte, motif):
    n = len(texte)
    p = len(motif)
    if n < p:
        return False
    for i in range(n - p + 1):
        if motif_est_a_la_position(texte, motif, i):
            return True
    return False

Cette écriture est équivalente et est plus lisible. La possibilité d'interrompre les fonctions avec return permet d'éviter break. Enfin, le simple fait d'ajouter une fonction avec un nom explicite permet de se dispenser de commentaires.

Si vous êtes curieux sur ces méthodes de recherche textuelle, vous pouvez consulter ce TD de terminale NSI sur l'algorithme de Boyer-Moore.