13 — Algorithmes sur les Chaînes : Cours complet

Niveau : Université — Durée : 5h de cours + 5h de TP Trouver un motif dans un texte, indexer des millions de documents, aligner des séquences ADN : le monde entier est fait de chaînes.

Partie I — Recherche naïve

1.1 Algorithme

On aligne le motif p de longueur m sur chaque position du texte t de longueur n, et on compare caractère à caractère.

def naive(t, p):
    n, m = len(t), len(p)
    matches = []
    for i in range(n - m + 1):
        if t[i:i+m] == p:
            matches.append(i)
    return matches

1.2 Complexité

Pire cas : O(n·m) — texte "aaaaaaaaab", motif "aaaab".
Moyen : proche de O(n) pour textes naturels (échec rapide au 1er caractère).

Diagramme en cours de génération...

Partie II — Rabin-Karp (rolling hash)

2.1 Principe

Comparer les empreintes (hash) des fenêtres du texte avec le hash du motif, au lieu des caractères.

Hash de la fenêtre : h = (c0·B^k + c1·B^(k-1) + ... + ck) mod M.
Rolling hash : passer d'une fenêtre à la suivante en O(1) :

h_new = (B·(h_old − t[i]·B^(m-1)) + t[i+m]) mod M

def rabin_karp(t, p):
    n, m = len(t), len(p)
    B, M = 256, 10**9 + 7
    hp = 0
    for c in p: hp = (hp * B + ord(c)) % M
    h = 0
    for c in t[:m]: h = (h * B + ord(c)) % M
    power = pow(B, m - 1, M)
    matches = []
    for i in range(n - m + 1):
        if h == hp and t[i:i+m] == p:      # vérification anti-collision
            matches.append(i)
        if i < n - m:
            h = ((h - ord(t[i]) * power) * B + ord(t[i+m])) % M
    return matches

2.2 Analyse

Temps attendu : O(n + m) (rare vérification de collision).
Pire cas : O(n·m) si collisions nombreuses (un hash faible, ou texte hostile).
Avantage clé : recherche de plusieurs motifs ou de fenêtres de longueurs variables (ex. plagiat, duplication de code).

Choisir M ~ 10⁹+7 et B > alphabet → risque de collision négligeable en pratique.

Partie III — KMP (Knuth–Morris–Pratt)

3.1 L'idée

Quand une comparaison échoue à la position j du motif, ne pas repartir de zéro : utiliser le préfixe déjà comparé.

3.2 La prefix function (pi)

pi[j] = longueur du plus long préfixe propre de p[:j] qui est aussi un suffixe de p[:j].

def prefix_function(p):
    m = len(p)
    pi = [0] * m
    for i in range(1, m):
        j = pi[i - 1]
        while j > 0 and p[i] != p[j]:
            j = pi[j - 1]
        if p[i] == p[j]:
            j += 1
        pi[i] = j
    return pi

Exemple : p = "aabaaab" → pi = [0, 1, 0, 1, 2, 2, 3].

3.3 La recherche

def kmp(t, p):
    pi = prefix_function(p)
    matches = []
    j = 0
    for i, ch in enumerate(t):
        while j > 0 and ch != p[j]:
            j = pi[j - 1]
        if ch == p[j]:
            j += 1
        if j == len(p):
            matches.append(i - j + 1)
            j = pi[j - 1]
    return matches

3.4 Analyse

O(n + m) garanti (chaque caractère du texte avance au plus 1 dans j, le recul total est borné par O(n)).
Ne ré-scanne jamais le texte.
Pattern réutilisable : les "cycles de bordure" servent aussi pour l'automate de Aho-Corasick.

Partie IV — Boyer-Moore

4.1 L'idée

Comparer de droite à gauche dans le motif : les échecs arrivent tôt, et on peut sauter loin.

4.2 Bad character heuristic

Dernière occurrence de chaque caractère du motif. À l'échec sur t[i+k] != p[k], on décale pour aligner t[i+k] avec sa dernière occurrence dans p (avant k).

def bad_char_table(p):
    last = {}
    for i, ch in enumerate(p):
        last[ch] = i
    return last

def boyer_moore(t, p):
    if not p: return []
    m = len(p)
    last = bad_char_table(p)
    matches = []
    i = 0
    while i <= len(t) - m:
        k = m - 1
        while k >= 0 and p[k] == t[i + k]:
            k -= 1
        if k < 0:
            matches.append(i)
            i += m
        else:
            shift = last.get(t[i + k], -1)
            i += max(1, k - shift)
    return matches

4.3 Good suffix heuristic

Quand une partie du motif a déjà été comparée (le "suffixe bon"), on décale pour aligner cette partie avec une occurrence précédente identique dans le motif.

4.4 Analyse

Pire cas : O(n·m).
En pratique : sous-linéaire ! ~O(n/m) sur textes naturels. C'est l'algorithme par défaut des moteurs grep, strstr, éditeurs.

Partie V — Z-algorithm

5.1 Définition

z[i] = longueur du plus long préfixe de t commençant en position i et qui est aussi un préfixe de t.

def z_algorithm(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

5.2 Recherche avec Z

Construire s = p + "$" + t (séparateur absent de p) : chaque z[i] ≥ m pour i > m indique une occurrence du motif à la position i − m − 1.

5.3 Analyse

O(n) — le segment [l, r) garantit un total linéaire de comparaisons.
Élégant, simple, utile pour beaucoup de problèmes de chaînes.

Partie VI — Trie (arbre préfixe)

6.1 Structure

Diagramme en cours de génération...

Chaque nœud = une lettre.
Marqueur de fin de mot sur les nœuds terminaux.
Insérer/chercher/préfixe : O(L) où L = longueur du mot (indépendant du nombre de mots !).

6.2 Implémentation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

6.3 Utilisations

Autocomplete / suggestions (clavier, IDE).
Correction orthographique : mots proches par édition.
Dictionnaires, IP routing (tries binaires).

Partie VII — Aho-Corasick (multi-patterns)

7.1 Le besoin

Rechercher k motifs simultanément dans un texte. Naïf : O(k·n·m). Aho-Corasick : O(n + somme des tailles des motifs).

7.2 La structure

Construire un Trie de tous les motifs.
Ajouter des liens d'échec (failure links) : en cas d'échec, où continuer (le plus long suffixe qui est préfixe d'un motif).
Parcourir le texte en suivant les liens : à chaque position, tous les motifs se terminant ici sont émis.

from collections import deque

def build_automaton(patterns):
    root = {"next": {}, "fail": None, "out": []}
    for pat in patterns:
        node = root
        for ch in pat:
            node = node["next"].setdefault(ch, {"next": {}, "fail": None, "out": []})
        node["out"].append(pat)
    # BFS pour les liens d'échec
    q = deque()
    for ch, child in root["next"].items():
        child["fail"] = root
        q.append(child)
    while q:
        node = q.popleft()
        for ch, child in node["next"].items():
            f = node["fail"]
            while f is not None and ch not in f["next"]:
                f = f["fail"]
            child["fail"] = f["next"][ch] if f else root
            child["out"] += child["fail"]["out"]
            q.append(child)
    return root

def aho_corasick(text, patterns):
    root = build_automaton(patterns)
    node = root
    results = []
    for i, ch in enumerate(text):
        while node is not None and ch not in node["next"]:
            node = node["fail"]
        if node is None:
            node = root
        else:
            node = node["next"][ch]
        for pat in node["out"]:
            results.append((i - len(pat) + 1, pat))
    return results

7.3 Applications

Antivirus / DLP (détection de signatures).
Filtrage de contenu, recherche multi-mots.
Bio-informatique : présence de millions de motifs.

Partie VIII — Suffix Array, Suffix Tree, LCP

8.1 Suffix array

Tableau trié des indices de début de tous les suffixes.

texte : "banana"
suffixes triés :  "a"(5) "ana"(3) "anana"(1) "banana"(0) "na"(4) "nana"(2)
suffix array : SA = [5, 3, 1, 0, 4, 2]

Construction : O(n) (SA-IS / DC3) ; naïf O(n² log n).
Recherche d'un motif : O(m log n) par binary search sur SA.

8.2 LCP array

lcp[i] = Longueur du plus long préfixe commun entre suffix[SA[i]] et suffix[SA[i-1]].

Sert à : dénombrer les sous-chaînes distinctes, plus longue répétition, etc.
Calcul : O(n) via l'algorithme de Kasai.

8.3 Suffix tree

Arbre compressé de tous les suffixes (arcs = sous-chaînes). Construit en O(n) (Ukkonen).

Propriété	Suffix array	Suffix tree
Mémoire	O(n) petit	O(n) mais constantes élevées
Construction	simple / O(n)	complexe
Recherche	O(m log n)	O(m)
Usage courant	production	recherche / bio-info

Partie IX — Levenshtein (edit distance)

La distance d'édition a déjà été traitée au chapitre 10 (DP). Rappel :

def levenshtein(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1): dp[i][0] = i
    for j in range(m + 1): dp[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[n][m]

Applications : fuzzy search, correcteurs, diff, alignement ADN (avec variantes).

Partie X — Manacher (palindromes)

Problème : trouver tous les palindromes, ou le plus long palindrome sous-chaîne, en O(n) (naïf : O(n²)).

10.1 Principe

Intercaler des séparateurs : #a#b#a# → les palindromes pairs et impairs sont unifiés.
d[i] = rayon du plus long palindrome centré en i (sur la chaîne transformée).
Miroir : si i est dans le palindrome [l, r] centré en c, alors d[i] ≥ min(d[mirror], r − i).

def manacher(s):
    t = "#" + "#".join(s) + "#"
    n = len(t)
    d = [0] * n
    l, r = 0, -1
    for i in range(n):
        k = 1 if i > r else min(d[l + r - i], r - i + 1)
        while i - k >= 0 and i + k < n and t[i - k] == t[i + k]:
            k += 1
        d[i] = k
        if i + k - 1 > r:
            l, r = i - k + 1, i + k - 1
    # longueur du plus long palindrome réel = max(d) - 1
    return max(d) - 1

10.2 Analyse

O(n) — le rayon droit r ne fait que croître.
Utilisations : bio-informatique (palindromes ADN), traitement de texte.

Partie XI — Applications réelles

Application	Algorithmes
Moteurs de recherche	Trie, suffix array, KMP, tokenisation, ranking
Correcteurs orthographiques	Levenshtein + Trie + BK-tree
Antivirus / DLP	Aho-Corasick (signatures)
Compression	LZ77 (matching de fenêtre), Huffman (chapitre 11)
Bio-informatique	Suffix tree, alignement (DP), index de Burrows-Wheeler
Autocomplétion	Trie + statistiques
Plagiat	Rolling hash (fenêtres)
Regex	Automates (KMP est un cas particulier)

Récapitulatif des complexités

Algorithme	Pré-traitement	Recherche	Mémoire
Naïf	—	O(n·m)	O(1)
Rabin-Karp	O(m)	O(n+m) attendu	O(1)
KMP	O(m)	O(n)	O(m)
Boyer-Moore	O(m)	O(n) pire, sous-linéaire pratique	O(m)
Z-algorithm	O(n)	—	O(n)
Trie	O(ΣL)	O(L)	O(ΣL·alphabet)
Aho-Corasick	O(ΣL)	O(n + occurrences)	O(ΣL)
Suffix array	O(n)	O(m log n)	O(n)
Manacher	O(n)	—	O(n)
Levenshtein	—	O(n·m)	O(min(n,m))

Check-list de maîtrise

Je sais implémenter KMP (prefix function + recherche).
Je sais expliquer le rolling hash et calculer une nouvelle fenêtre en O(1).
Je sais justifier pourquoi Boyer-Moore est rapide en pratique.
Je sais construire et utiliser un Trie.
Je sais construire l'automate Aho-Corasick (failure links).
Je sais ce qu'est un suffix array et comment l'utiliser.
Je sais implémenter Manacher en O(n).
Je sais choisir l'algorithme adapté à une application donnée.