TNSI : Recherche dans un Texte.
Activité 1 : Algorithme Naïf de Recherche Simple⚓︎

Contenus	Capacités Attendues	Commentaires
Recherche textuelle.	Étudier l'algorithme de Boyer-Moore pour la recherche d'un motif dans un texte.	L'intérêt du prétraitement du motif est mis en avant. L'étude du coût, difficile, ne peut être exigée.

Animation :

Algorithme Naïf de Recherche d'un motif dans un Texte
(mis en ligne par L. Abdal, d'après un travail de N. Reveret)

Définitions & Notations⚓︎

Dans toute la suite on cherche donc la première occurrence d’un motif de longueur \(p\) dans un texte de longueur \(n\).
À un moment donné de la recherche, on observe une fenêtre de taille \(p\) du texte complet, sur laquelle on aligne le motif, et on regarde s'il y a bien correspondance.
S’il n’y a pas correspondance, on recommencera la recherche avec une fenêtre décalée vers la droite dans le texte.
Dans tous les algorithmes présentés ici, la fenêtre se déplacera toujours de gauche à droite.
Nous noterons :

\(i\) la position de la fenêtre dans le texte : c’est l’index du premier caractère du texte qui apparaît dans la fenêtre.
\(j\) l’index dans le motif du caractère du motif que nous comparons avec son analogue du texte

Il s'agit donc de comparer le caractère motif[j] avec texte[i + j].
La recherche peut se faire à condition que \(i + p \leq n\) puisque les caractères du texte qui apparaissent dans la fenêtre ont pour index : \(i, i + 1, ..., i + p − 1\) (donc \(i+p-1 \leq n-1\))

Un Algorithme naïf⚓︎

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.
On en déduit l’écriture de la fonction correspondance :

def correspondance(texte, motif, i):
    # algorithme naïf - l'inégalité i + p <= n est garantie
    p = len(motif)
    for j in range(p):
        if texte[i + j] != motif[j]:
            return (False, 1)
    # si on arrive ici c'est qu'il y a eu correspondance
    return (True, 0)

Implémenter l'Algorithme Naïf⚓︎

SANS UTILISER les méthodes natives find ou index de Python :

écrire une fonction cherche(texte, motif,i ) qui :

reçoit en entrée deux strings : texte et motif
renvoie en sortie :
- True si la chaîne de caractères motif se trouve dans texte
- False sinon

Corrige

def cherche(texte:str, motif:str)->bool:
    n = len(texte)
    p = len(motif)
    i = 0
    while i + p <= n:
        ok, decalage = correspondance(texte, motif, i)
        if ok: # on a trouvé une occurrence du motif en position i dans le texte !
            return True
        else:
            i = i + decalage
    return False

Même question, mais qui cette fois-ci renvoie en sortie :

l'indice i où de la première occurence (/position) chaîne de caractères motif se trouve dans texte (lorsque motif existe dans texte)
-1 sinon

Corrige

def cherche(texte:str, motif:str)->int:
    n = len(texte)
    p = len(motif)
    i = 0
    while i + p <= n:
        ok, decalage = correspondance(texte, motif, i)
        if ok: # on a trouvé une occurrence du motif en position i dans le texte !
            return i
        else:
            i = i + decalage
    return -1

Coût/Complexité de l'algorithme naïf⚓︎

Comme le programme suggère de s’y limiter, on n’étudie que la complexité dans le pire des cas.
Mais à quoi correspond ce pire des cas, au fait ?
Le pire des cas est quand on est obligé de faire passer la fenêtre par tous les indices i de l’intervalle \(⟦0, n − p⟧\) et si en plus, pour chaque position i de la fenêtre, on doit comparer tous les caractères du motif au texte, c’est-à-dire si j varie dans tout l’intervalle \(⟦0, p⟧\).
On peut vérifier que c’est en particulier le cas pour un texte ne contenant que des a et un motif ne contenant que des a sauf sa dernière lettre : on cherche aa...ab dans aa...aa.
Mais alors il y a \(n − p + 1\) appels à correspondance(), chacun de ces appels nécessitant \(p\) comparaisons de caractères : la complexité dans le cas le pire est donc, si on la mesure par le nombre de comparaisons, égale à \(p(n − p)\) :

\(C(n) = p(n-p)\)

Références⚓︎

Cette page est directement issue de : Eduscol