Introduction

La méthode index qui s’applique aux chaînes de caractères Python permet de renvoyer l’indice d’une sous-chaîne (motif) dans un texte.

L’objectif de cet activité est d’analyser deux algorithmes possibles pour cette fonction :

  • la solution naïve
  • une solution optimisée : l’algorithme de Boyer-Moore qui met en oeuvre un mécanisme de précalcul.

L’idée centrale du précalcul est d’éviter les calculs répétitifs (à chaque itération, afin de réduire la complexité (en temps de calcul) aux détriment (souvent) d’une plus grande consommation mémoire.

La solution naïve

def nSearch(text: str, pattern: str) -> int:
    """ Recherche un motif / une sous-chaîne dans un texte
    @param text le texte
    @param pattern le motif recherché
    @return l'indice du premier caractère du motif dans le texte
            ou -1 si non trouvé
    >>> nSearch("Example", "Ex")
    0
    >>> nSearch("Example", "ple")
    4
    >>> nSearch("Example", "am")
    2
    >>> nSearch("Example", "not")
    -1
    >>> nSearch("Exam", "Example")
    -1
    """
    global cplx; cplx = 0 #calcul du coût
    end = len(text) - len(pattern) + 1
    match = False; i = 0
    while not match and i < end:
        match = True; j = 0
        while match and j != len(pattern):
            cplx += 1 #calcul du coût
            if text[i + j] != pattern[j]:
                match = False
            j += 1
        i += 1
    return i - 1 if match else -1
  • Tester puis expérimenter cette fonction ; après exécution, le coût est enregistré dans la variable cplx.
  • Faire la trace du programme avec par exemple le troisième test unitaire.
  • Déterminer quels sont les meilleurs et pire cas.
  • Déterminer la complexité de cet algorithme dans les meilleurs et pire cas en fonction de n (la longueur du texte) et de m la longueur du motif).

L’algorithme de Boyer-Moore simplifié (Horspool)

Principe de fonctionnement

Pour comprendre le principe de cet algorithme, se référer à la vidéo du cours d’Erwan Demerville

Précalcul

Soit “amar” le motif recherché.

Construire une table de décalage : pour chaque caractère du motif, relever l’indice inversé (de droite à gauche — cf poids des bits) de sa dernière occurence.

motif a m a r
indices 3 2 1 0

Table de décalage (offsets) : { “a”: 1, “m”: 2 } — l’offset du dernier caractère du motif est toujours 0.

Déroulement de l’algorithme

Soit le texte : “loren irsum doler amar…”

l’algorithme se déroule comme suit :

indices 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21
texte l o r u n i r s u m d o l a r a m a r
motif a m a r
motif a m a r
motif a m a r
motif a m a r
motif a m a r
motif a m a r
motif a m a r
motif a m a r
  • À la première itération, il y a non-correspondance à l’indice 3 ; comme il n’y a pas de “u” (texte[3]) dans le motif, la fenêtre de comparaison est décalée après le u.
  • À la deuxième itération, il y a correspondance à l’indice 7, mais pas à l’indice 6 ; comme il n’y a pas de “i” dans le motif, la fenêtre est décalée après cette lettre (et non pas après le “r”).
  • À la troisième itération, il y a non-correspondance à l’indice 10, mais “m” est dans le motif et la fenêtre est décalée de 2 (cf table de décalage) pour aligner la lettre du motif à celle du texte.
  • À la quatrième itération, il y a correspondance aux indices 16 et 15.
  • À la cinquième itération, il y a non-correspondance à l’indice 18
  • À la sixième itération, il y a non-correspondance à l’indice 19.
  • À la septième itération, il y a correspondance pour toutes les lettres du motif.

Au final, il y a eu 12 comparaisons aux indices 3, 7, 6, 10, 16, 15, 18, 19 puis 21, 20, 19 et 18 (toujours de droite à gauche).

Code de la fonction de recherche

from typing import Dict

def bmhSearch(text: str, pattern: str) -> int:
    """ Recherche un motif / une sous-chaîne dans un texte
    @param text le texte
    @param pattern le motif recherché
    @return l'indice du premier caractère du motif dans le texte
            ou -1 si non trouvé
    >>> bmhSearch("Example", "Ex")
    0
    >>> bmhSearch("Example", "ple")
    4
    >>> bmhSearch("Example", "am")
    2
    >>> bmhSearch("Example", "not")
    -1
    >>> bmhSearch("Exam", "Example")
    -1
    """
    def getOffsets(pattern: str) -> Dict: #sous-fonction de précalcul
        table = {}
        for i in range(len(pattern) - 1): #sauf la dernière lettre
            letter = pattern[i]
            table[letter] = len(pattern) - i - 1
        return table
    
    global cplx; cplx = len(pattern) - 1 #calcul du coût
    offsets = getOffsets(pattern) #pré-calcul
    
    match = False; i = 0
    while not match and i < len(text) - len(pattern) + 1:
        match = True; j = len(pattern) - 1
        while match and j >= 0: #parcours du motif de droite à gauche
            cplx += 1 #calcul du coût
            if text[i + j] != pattern[j]:
                match = False
                letter = text[i + j] #lettre qui ne correspond pas
                if letter in offsets.keys(): #alignement du motif
                    i += offsets[letter]
                else: #alignement impossible
                    i += j + 1
            j -= 1
    return i if match else -1

Expérimentation

Expérimenter la fonction, et comparer son coût à celui de l’implémentation naïve.

Questions de réflexion

  • Faire une trace de la fonction getOffsets avec le motif “morem”. Expliquer la formule qui détermine l’indice (de droite à gauche) : len(pattern) - i - 1.
  • Faire une trace de la fonction bmhSearch à partir du texte et du motif de l’exemple. Expliquer pourquoi l’instruction en cas d’alignement impossible est i += j + 1 et non pas i += len(pattern).
  • Indiquer le pire cas et sa complexité.