Recherche textuelle

La recherche d’un motif dans un texte est un problème fondamental en informatique : elle intervient dans les éditeurs de texte (Ctrl+F), les moteurs de recherche, l’analyse de séquences ADN ou encore les outils comme grep. Nous allons d’abord étudier une approche naïve, puis découvrir qu’en comparant le motif à l’envers, on peut aller beaucoup plus vite.

1. Position du problème

On dispose d’un texte de longueur \(n\) et d’un motif de longueur \(m\) (avec \(m \leqslant n\)). On cherche à déterminer si le motif apparaît dans le texte, et si oui, à quelles positions.

Par exemple, pour texte = 'abracadabra' et motif = 'bra', le motif apparaît aux positions 1 et 8 :

Pour résoudre ce problème, on va « glisser » le motif le long du texte. La question centrale est : de combien de positions avancer après chaque tentative ?

2. Algorithme naïf (de force brute)

2.1. Principe

L’idée la plus simple consiste à tester chaque position de départ possible : pour chaque indice \(i\) de 0 à \(n - m\), on compare les caractères du motif un par un avec ceux du texte à partir de la position \(i\). Dès qu’un caractère ne correspond pas, on passe à la position suivante.

Illustrons avec texte = 'abracadabra' et motif = 'dab' :

i=0: abracadabra    →  'a' ≠ 'd'  →  échec immédiat
     dab

i=1: abracadabra    →  'b' ≠ 'd'  →  échec immédiat
      dab

i=2: abracadabra    →  'r' ≠ 'd'  →  échec immédiat
       dab

  ...on continue position par position...

i=6: abracadabra    →  'd' = 'd', 'a' = 'a', 'b' = 'b'  →  trouvé !
           dab

On avance toujours d’une seule position, même quand le premier caractère ne correspond pas : c’est ce qui rend cet algorithme lent.

2.2. Implémentation en Python

def algo_naif(texte, motif):
    """Recherche toutes les occurrences de motif dans texte.

    Paramètres
    ----------
    texte : str – le texte dans lequel on effectue la recherche
    motif : str – le motif recherché

    Renvoie
    -------
    list[int] – la liste des indices de début de chaque occurrence
    """
    n = len(texte)
    m = len(motif)
    indices = []
    for i in range(n - m + 1):
        trouvé = True
        for j in range(m):
            if texte[i + j] != motif[j]:
                trouvé = False
                break
        if trouvé:
            indices.append(i)
    return indices


assert algo_naif("abracadabra", "bra") == [1, 8]
assert algo_naif("abracadabra", "dab") == [6]
assert algo_naif("aaaa", "aa") == [0, 1, 2]
assert algo_naif("abc", "abc") == [0]
assert algo_naif("abc", "xyz") == []

Remarques sur le code :

• La borne de la boucle est n - m + 1 (et non n - m) car la position \(n - m\) est la dernière position valide pour aligner le motif.
• La variable trouvé est initialisée avant la boucle intérieure, pas à l’intérieur : c’est important pour qu’elle soit correctement réinitialisée à chaque nouvelle position.
• On utilise break pour interrompre la comparaison dès le premier caractère qui ne correspond pas.

2.3. Complexité

La boucle extérieure parcourt \(n - m + 1\) positions. Pour chacune, la boucle intérieure effectue au plus \(m\) comparaisons. La complexité dans le pire des cas est donc :

$$\mathcal{O}\left( (n - m + 1) \times m \right) \approx \mathcal{O}(n \times m)$$

Comme en général \(n \gg m\), on parle de complexité quadratique \(\mathcal{O}(n^2)\).

Exemple de pire cas : chercher 'aab' dans 'aaaaaaaaa'. À chaque position, les deux premiers caractères correspondent ('a' = 'a', 'a' = 'a') avant d’échouer sur le troisième ('a' ≠ 'b'). On effectue presque \(3 \times (n - 2)\) comparaisons.

Nous allons voir qu’il est possible de faire beaucoup mieux en comparant le motif de droite à gauche.

3. L’algorithme de Boyer-Moore-Horspool

3.1. Deux idées clés

Nous allons étudier une version simplifiée de l’algorithme de Boyer-Moore, proposée par Nigel Horspool en 1980. Cet algorithme repose sur deux idées :

1. On compare le motif de droite à gauche, en commençant par sa dernière lettre.
2. Au lieu d’avancer d’une seule position après un échec, on utilise un décalage calculé à partir du caractère du texte qui a provoqué l’échec. Ce décalage peut être bien supérieur à 1.

3.2. Déroulement sur un exemple

Cherchons motif = 'dab' dans texte = 'abracadabra'.

Étape 1 – on aligne le motif en début de texte et on compare le dernier caractère du motif avec le caractère correspondant du texte :

abracadabra
dab
  ↑ on compare ici : 'r' ≠ 'b'

Échec. Le caractère du texte est 'r' : or 'r' n’apparaît nulle part dans le motif. On peut donc décaler le motif de toute sa longueur, soit 3 positions, sans risquer de rater une occurrence.

Étape 2 – on aligne le motif à la position 3 :

abracadabra
   dab
     ↑ on compare ici : 'a' ≠ 'b'

Échec. Le caractère du texte est 'a' : or 'a' apparaît dans le motif en avant-dernière position. On décale d’une seule position pour aligner les deux 'a'.

Étape 3 – on aligne le motif à la position 4 :

abracadabra
    dab
      ↑ on compare ici : 'd' ≠ 'b'

Échec. Le caractère du texte est 'd' : or 'd' apparaît dans le motif en première position (soit à distance 2 de la fin). On décale de 2 positions.

Étape 4 – on aligne le motif à la position 6 :

abracadabra
      dab
        ↑ on compare : 'b' = 'b', puis 'a' = 'a', puis 'd' = 'd'

Tous les caractères correspondent de droite à gauche : le motif est trouvé à la position 6.

Bilan : au lieu de tester les 9 positions possibles (algorithme naïf), on n’en a testé que 4. Le gain vient des « sauts » permis par le pré-traitement.

3.3. La table de décalages (pré-traitement)

Pour chaque caractère \(c\) du motif (sauf le dernier), on calcule la distance entre sa dernière occurrence dans le motif (hors dernière position) et la fin du motif. Si un caractère n’est pas dans le motif, le décalage vaut \(m\) (la longueur du motif).

Formellement, pour un motif de longueur \(m\), si le caractère \(c\) apparaît à la position \(i\) (la plus à droite, hors dernière position) :

$$\text{décalage}(c) = m - 1 - i$$

On stocke ces valeurs dans un dictionnaire.

Exemple avec motif = 'dab' (longueur 3) :

Le dictionnaire renvoyé est {'d': 2, 'a': 1}.

Exemple avec motif = 'maman' (longueur 5) :

Le caractère 'm' apparaît aux positions 0 et 2 : on garde la plus à droite (2), ce qui donne un décalage de \(5 - 1 - 2 = 2\). Le caractère 'a' apparaît aux positions 1 et 3 : on garde la position 3, décalage \(5 - 1 - 3 = 1\).

Le dictionnaire renvoyé est {'m': 2, 'a': 1}.

def pre_traitement(motif):
    """Construit la table de décalages pour Boyer-Moore-Horspool.

    Paramètres
    ----------
    motif : str – le motif recherché

    Renvoie
    -------
    dict – dictionnaire {caractère: décalage}
    """
    m = len(motif)
    décalages = {}
    for i in range(m - 1):       # on parcourt le motif sauf le dernier caractère
        décalages[motif[i]] = m - 1 - i
    return décalages


assert pre_traitement("dab") == {'d': 2, 'a': 1}
assert pre_traitement("maman") == {'m': 2, 'a': 1}
assert pre_traitement("abracadabra") == {'a': 3, 'b': 2, 'r': 1, 'c': 6, 'd': 4}

Pourquoi exclure le dernier caractère ? Parce que si le caractère du texte aligné avec la fin du motif est identique au dernier caractère du motif, on ne veut pas décaler de 0 (ce qui ferait boucler). On veut plutôt le décalage vers la prochaine occurrence de ce caractère plus à gauche dans le motif, ou \(m\) s’il n’apparaît pas ailleurs.

3.4. Implémentation complète

def recherche_boyer_moore(texte, motif):
    """Recherche toutes les occurrences de motif dans texte
    avec l'algorithme de Boyer-Moore-Horspool.

    Paramètres
    ----------
    texte : str – le texte dans lequel on effectue la recherche
    motif : str – le motif recherché

    Renvoie
    -------
    list[int] – la liste des indices de début de chaque occurrence
    """
    n = len(texte)
    m = len(motif)
    décalages = pre_traitement(motif)
    indices = []

    i = 0                        # position de début de la fenêtre dans le texte
    while i <= n - m:
        j = m - 1                # on compare de droite à gauche
        while j >= 0 and texte[i + j] == motif[j]:
            j -= 1
        if j < 0:                # tous les caractères correspondent
            indices.append(i)
            i += 1               # on avance d'une position pour chercher les suivantes
        else:
            # on décale selon le caractère du texte aligné avec la fin du motif
            c = texte[i + m - 1]
            if c in décalages:
                i += décalages[c]
            else:
                i += m
    return indices


assert recherche_boyer_moore("abracadabra", "dab") == [6]
assert recherche_boyer_moore("abracadabra", "bra") == [1, 8]
assert recherche_boyer_moore("abracadabra", "abra") == [0, 7]
assert recherche_boyer_moore("abracadabra", "obra") == []
assert recherche_boyer_moore("aaaa", "aa") == [0, 1, 2]
assert recherche_boyer_moore("abc", "abc") == [0]
assert recherche_boyer_moore("bonjour", "papa") == []

Points importants du code :

• La variable i représente la position de début de la fenêtre de comparaison.
• La comparaison se fait de droite à gauche grâce à la boucle while j >= 0.
• En cas de correspondance complète (j < 0), on avance d’une position pour trouver les éventuelles occurrences suivantes.
• En cas d’échec, le décalage est déterminé par le caractère du texte aligné avec la fin du motif (texte[i + m - 1]), conformément à la règle de Horspool.

3.5. Complexité

• Meilleur cas : si le dernier caractère du motif ne correspond jamais et que le caractère du texte n’est pas dans le motif, on saute de \(m\) positions à chaque fois. Le nombre de comparaisons est environ \(\dfrac{n}{m}\), soit une complexité sous-linéaire \(\mathcal{O}!\left(\dfrac{n}{m}\right)\). C’est remarquable : on peut trouver un motif sans examiner chaque caractère du texte.
• Pire cas : \(\mathcal{O}(n \times m)\), identique à l’algorithme naïf (par exemple, chercher 'baa' dans 'aaaaaa' : le décalage vaut toujours 1 et chaque fenêtre est comparée en entier).
• En pratique : sur du texte naturel (en français ou en anglais), les caractères sont suffisamment variés pour que les décalages soient grands. Boyer-Moore-Horspool est souvent trois à cinq fois plus rapide que l’algorithme naïf.

4. Comparaison expérimentale

On peut comparer les deux algorithmes avec le module timeit sur un texte long :

import timeit

texte = open("un_fichier.txt").read()  # un texte de plusieurs milliers de caractères
motif = "algorithme"

t_naif = timeit.timeit(lambda: algo_naif(texte, motif), number=1000)
t_boyer = timeit.timeit(lambda: recherche_boyer_moore(texte, motif), number=1000)

print(f"Naïf    : {t_naif:.4f} s")
print(f"Boyer-Moore : {t_boyer:.4f} s")

Plus le motif est long et l’alphabet varié, plus l’avantage de Boyer-Moore-Horspool est marqué.