backend / algorithmes-structures-donnees
Recherche de motifs : Rabin-Karp et hachage roulant
Explication
Ce que vous allez apprendre
- Expliquer le principe de Rabin-Karp : comparer des hachages numériques plutôt que des caractères un par un
- Calculer un hachage roulant pour passer d'une fenêtre à la suivante en O(1) au lieu de tout recalculer
- Expliquer pourquoi une collision de hachage n'est jamais une preuve d'égalité, et pourquoi vérifier caractère par caractère reste indispensable
- Comparer Rabin-Karp à KMP selon le contexte (un seul motif vs plusieurs motifs recherchés simultanément)
- Relier le hachage roulant à des cas d'usage réels comme la détection de plagiat ou la déduplication de documents
Dans quel contexte ?
Un service de détection de plagiat doit vérifier si un document de 10 000 mots contient des passages copiés parmi une bibliothèque de millions de documents sources. Comparer caractère par caractère chaque passage à chaque document source serait bien trop lent. En calculant un hachage roulant sur des fenêtres glissantes de texte, le service compare des empreintes numériques en O(1) et ne vérifie le texte complet que dans les rares cas où deux hachages coïncident, ce qui rend la détection praticable à très grande échelle.
D'abord, une idée radicalement différente de KMP
La leçon précédente évitait de reculer dans le texte en précalculant une table sur le motif. Rabin-Karp attaque le même problème autrement : au lieu de comparer les caractères un par un, on compare des "empreintes" numériques (des hachages) des fenêtres de texte.
Prérequis
Cette leçon s'appuie sur les tables de hachage (leçon 8) : Rabin-Karp applique le même principe de "condenser une donnée en un nombre", mais pour comparer rapidement des fenêtres de texte plutôt que pour indexer des clés.
Pourquoi cette idée est intéressante
Comparer deux nombres est instantané, bien plus rapide en pratique que comparer des chaînes entières caractère par caractère.
| Algorithme | Ce qui est comparé | Cas d'usage privilégié |
|---|---|---|
| KMP | Caractères, avec table d'échec | Recherche d'un seul motif dans un texte |
| Rabin-Karp | Hachages (empreintes numériques) | Recherche de plusieurs motifs, détection de similarité |
Il reste un problème à résoudre
Recalculer le hachage complet d'une nouvelle fenêtre de texte à chaque déplacement coûterait aussi cher qu'une comparaison directe : on n'aurait alors rien gagné du tout.
La solution : le hachage roulant
Connaissant le hachage de la fenêtre actuelle, on peut calculer celui de la fenêtre suivante en temps constant, simplement en retirant la contribution du caractère qui sort et en ajoutant celle du caractère qui entre.
Un piège fondamental à connaître
Deux textes différents peuvent, par malchance, produire le même hachage : une "collision". Une égalité de hachage n'est donc jamais une preuve d'égalité réelle.
Piège fréquent
Une égalité de hachage entre deux fenêtres n'est JAMAIS une preuve d'égalité réelle : deux textes différents peuvent produire le même hachage par collision. Il faut toujours vérifier caractère par caractère après une correspondance de hachage avant de la considérer comme confirmée.
La conséquence de ce piège
Une égalité de hachage indique seulement un candidat probable, qu'il faut ensuite vérifier caractère par caractère pour être certain. Ignorer cette vérification produirait des faux positifs silencieux.
Un avantage décisif sur KMP
Là où KMP doit reconstruire une table différente pour chaque motif recherché, Rabin-Karp peut hacher plusieurs motifs à l'avance et les comparer tous en une seule passe sur le texte.
Vers la suite
Ce cours quitte maintenant le texte pour explorer un autre domaine où les mêmes intuitions algorithmiques s'appliquent : la géométrie, avec le calcul de l'enveloppe convexe d'un ensemble de points.
Commandes & code
Recherche de motifs : Rabin-Karp
Rabin-Karp compare des hachages plutôt que des caractères, avec un avantage clé : chercher plusieurs motifs en une passe.
def rabin_karp(texte: str, motif: str, base: int = 256, modulo: int = 1_000_000_007) -> list[int]:
n, m = len(texte), len(motif)
if m == 0 or m > n:
return []
# Hachage roulant : recalcule le hash de la fenêtre suivante en O(1) au lieu de O(m)
puissance = pow(base, m - 1, modulo) # base^(m-1) mod modulo, réutilisé à chaque glissement
hash_motif = 0
hash_fenetre = 0
for i in range(m):
hash_motif = (hash_motif * base + ord(motif[i])) % modulo
hash_fenetre = (hash_fenetre * base + ord(texte[i])) % modulo
occurrences = []
for i in range(n - m + 1):
if hash_fenetre == hash_motif:
# Le hash peut coïncider par hasard (collision) -- toujours vérifier caractère par caractère
if texte[i:i + m] == motif:
occurrences.append(i)
if i < n - m:
# Retire le premier caractère de la fenêtre, ajoute le suivant -- O(1) amorti
hash_fenetre = (
(hash_fenetre - ord(texte[i]) * puissance) * base + ord(texte[i + m])
) % modulo
return occurrences
texte = "ababcabababcabcabab"
motif = "abcab"
assert rabin_karp(texte, motif) == [2, 10]
assert rabin_karp("aaaaaaa", "aaa") == [0, 1, 2, 3, 4]
# Recherche MULTI-motifs simultanée : avantage clé de Rabin-Karp par rapport à KMP
def rabin_karp_multi(texte: str, motifs: list[str], base: int = 256, modulo: int = 1_000_000_007) -> dict:
resultats = {m: [] for m in motifs}
par_longueur: dict[int, dict[int, list[str]]] = {}
for m in motifs:
hash_m = 0
for c in m:
hash_m = (hash_m * base + ord(c)) % modulo
par_longueur.setdefault(len(m), {}).setdefault(hash_m, []).append(m)
for longueur, table_hash in par_longueur.items():
if longueur == 0 or longueur > len(texte):
continue
puissance = pow(base, longueur - 1, modulo)
hash_fenetre = 0
for i in range(longueur):
hash_fenetre = (hash_fenetre * base + ord(texte[i])) % modulo
for i in range(len(texte) - longueur + 1):
if hash_fenetre in table_hash:
fenetre = texte[i:i + longueur]
for candidat in table_hash[hash_fenetre]:
if candidat == fenetre:
resultats[candidat].append(i)
if i < len(texte) - longueur:
hash_fenetre = (
(hash_fenetre - ord(texte[i]) * puissance) * base + ord(texte[i + longueur])
) % modulo
return resultats
assert rabin_karp_multi("abcabcabc", ["abc", "bca", "xyz"]) == {
"abc": [0, 3, 6], "bca": [1, 4], "xyz": []
}Résumé
- Le hachage roulant calcule le hash de la fenêtre suivante en O(1) à partir du hash précédent, sans recalculer depuis zéro.
- Une égalité de hash n'est qu'un CANDIDAT : toujours vérifier caractère par caractère pour écarter les collisions.
- Complexité moyenne O(n + m) comme KMP, mais Rabin-Karp généralise naturellement à la recherche de plusieurs motifs en une seule passe sur le texte.
Exercices pratiques
Mission : fiabiliser le détecteur de plagiat qui valide trop vite
Objectif : Diagnostiquer une vérification de collision de hachage manquante et raisonner sur le choix entre KMP et Rabin-Karp.
Contexte
Un service de détection de plagiat compare des passages de documents via un hachage roulant, mais un développeur pressé a supprimé la vérification if texte[i:i+m] == motif après une égalité de hachage, "pour gagner en performance". Depuis, le service signale occasionnellement des passages comme identiques alors qu'ils diffèrent réellement de quelques caractères.