🕸️ Aho–Corasick
Automate de recherche multi-motifs
État : 0 · Position 0 / 0
Paramètres
Commandes
Statistiques
État actuel
0
Position
0 / 0
Correspondances
0
Nœuds du trie
0
Journal des correspondances
Aucune correspondance pour le moment.
Infos et théorie

Aho–Corasick trouve chaque occurrence de plusieurs motifs dans un texte en un seul passage linéaire, en combinant un trie de tous les motifs avec des liens d'échec, qui généralisent l'idée sur laquelle repose l'algorithme mono-motif KMP.

1. Construction du trie

Chaque motif est inséré dans un trie partagé, dont la racine est le nœud 0. Chaque nœud correspond à la chaîne formée par le chemin depuis la racine ; un nœud est marqué comme nœud de sortie si ce chemin correspond à l'un des motifs.

2. Liens d'échec (BFS)

Pour chaque nœud v, atteint depuis le nœud parent u via le caractère c, le lien d'échec f(v) pointe vers le nœud correspondant au plus long suffixe propre de la chaîne du nœud v qui soit aussi un préfixe d'un motif (c'est-à-dire également un nœud du trie). Les liens d'échec sont calculés par un parcours BFS du trie, niveau par niveau : les enfants de la racine reçoivent f = racine ; pour un descendant plus profond atteint depuis u via c, on parcourt la chaîne de liens d'échec de u jusqu'à trouver un nœud possédant une transition goto sur c (ou jusqu'à revenir à la racine).

3. Sortie / liens de suffixes du dictionnaire

Un même nœud peut être simultanément le suffixe de plusieurs motifs correspondants ; l'ensemble effectif des correspondances de chaque nœud est donc constitué de ses propres outputs plus toutes les sorties accessibles en suivant les liens d'échec jusqu'à la racine — la chaîne de suffixes du dictionnaire. Le calcul préalable de cet ensemble fusionné (ou son parcours en temps réel) permet au scanner de signaler chaque motif se terminant à une position donnée, sans omettre aucune correspondance qui se chevauche.

4. Analyse

Le texte est fourni caractère par caractère. Depuis l'état courant, on emprunte la transition du trie si elle existe ; sinon, on applique successivement les liens d'échec jusqu'à trouver une transition ou à atteindre la racine. Après chaque transition, l'ensemble fusionné des sorties du nouvel état est signalé comme les correspondances se terminant à cette position.

Complexité

La construction du trie et des liens d'échec coûte O(m), où m est la longueur cumulée de tous les motifs ; l'analyse du texte coûte O(n), où n est la longueur du texte. La sortie de toutes les correspondances coûte O(z), où z est le nombre de correspondances, soit au total O(n + m + z).

À propos d'Aho–Corasick

Auteur : Équipe MySimulator · Relecture éditoriale : Rédaction MySimulator

Mis à jour le : 11 juillet 2026

L'algorithme Aho–Corasick, inventé en 1975 par Alfred V. Aho et Margaret J. Corasick aux laboratoires Bell, résout le problème de la recherche multi-motifs : étant donné un dictionnaire de motifs et un texte, trouver chaque occurrence de chaque motif en un seul passage linéaire. Il généralise l'algorithme de Knuth–Morris–Pratt (KMP), qui traite un seul motif, à plusieurs motifs à la fois, en fusionnant tous les motifs dans un trie commun et en calculant les liens d'échec par un parcours en largeur — exactement comme KMP calcule une fonction d'échec pour un seul motif. Le lien d'échec de chaque nœud pointe vers le plus long suffixe propre de sa chaîne qui soit aussi le préfixe d'un motif, et chaque nœud porte un ensemble de sorties « suffixe de dictionnaire » fusionné, obtenu en suivant les liens d'échec jusqu'à la racine. L'analyse d'un texte de longueur n ne coûte alors que O(n + m + z), où m est la longueur combinée des motifs et z le nombre de correspondances signalées. Grâce à cette efficacité, Aho–Corasick est à la base de l'utilitaire original fgrep/grep -F, des moteurs antivirus qui vérifient des fichiers par rapport à des milliers de signatures de logiciels malveillants à la fois, et des systèmes de détection d'intrusion réseau qui inspectent en temps réel le contenu des paquets à la recherche de chaînes d'attaque connues.

Questions fréquentes

En quoi Aho–Corasick diffère-t-il du simple lancement de KMP pour chaque motif séparément ?

Exécuter KMP séparément pour k motifs sur un texte de longueur n coûte O(k·n) dans le pire des cas, puisque chaque motif nécessite son propre passage. Aho–Corasick fusionne tous les motifs en un seul automate et analyse le texte exactement une fois, pour un coût de O(n + m + z) indépendamment du nombre de motifs, ce qui est bien plus rapide lorsqu'on recherche des centaines ou des milliers de motifs simultanément.

Qu'est-ce qu'un lien d'échec exactement, et pourquoi est-il nécessaire ?

Un lien d'échec depuis le nœud v pointe vers le nœud du trie représentant le plus long suffixe propre de la chaîne de v qui reste un préfixe d'un motif. Lorsque l'automate ne peut pas prolonger la correspondance en cours avec le caractère suivant, il suit les liens d'échec au lieu de repartir de la racine, si bien qu'aucun caractère d'entrée n'est jamais relu — c'est ce qui garde l'analyse linéaire en fonction de la longueur du texte.

Aho–Corasick peut-il trouver des correspondances qui se chevauchent, comme « he » et « hers » se terminant près de la même position ?

Oui. Comme chaque nœud du trie stocke un ensemble de sorties fusionné, obtenu en suivant les liens d'échec jusqu'à la racine (la chaîne de suffixes du dictionnaire), un seul état peut signaler plusieurs motifs qui sont des suffixes les uns des autres ou qui se terminent simplement à la même position du texte ; toutes les correspondances chevauchantes et imbriquées sont ainsi correctement signalées.

Où Aho–Corasick est-il utilisé en pratique ?

Au-delà de son usage d'origine dans l'utilitaire fgrep d'Unix, il alimente des moteurs antivirus qui comparent des fichiers à de vastes bases de signatures, des systèmes de détection d'intrusion réseau qui analysent les paquets à la recherche de chaînes d'attaque connues, des filtres anti-spam et de contenu, ainsi que des outils bio-informatiques qui recherchent de nombreux motifs courts à la fois dans des séquences d'ADN.