L'automate d'Aho-Corasick est un algorithme puissant de recherche de motifs multiples, permettant de localiser toutes les occurrences d'un ensemble de mots-clés (motifs) à l'intérieur d'un texte donné. Il combine les concepts d'un arbre de préfixes (Trie) et de la fonction d'échec de l'algorithme de Knuth-Morris-Pratt (KMP) pour réaliser une recherhce efficace en temps linéaire par rapport à la longueur du texte et des motifs.
Structure Fondamentale
L'automate est construit sur deux composants principaux :
- Le Trie (Arbre de Préfixes) : Il stocke tous les motifs. Chaque nœud de l'arbre représente un préfixe commun des motifs, et un chemin de la racine à un nœud donné forme un préfixe ou un motif complet.
- Les Liens d'Échec (Failure Links) : Pour chaque nœud du Trie, un lien d'échec pointe vers le nœud le plus long préfixe propre du chemin menant au nœud actuel qui est également un suffixe du chemin actuel. Ces liens sont cruciaux pour le retour rapide lors d'une non-correspondance, évitant de redémarrer la recherche depuis le début.
Construction de l'Automate
1. Insertion des Motifs dans le Trie
La première étape consiste à insérer tous les motifs dans un Trie. Chaque nœud du Trie représente un état de l'automate. Lorsque nous insérons un motif, nous créons des nœuds pour chaque caractère successif. Un compteur ou un drapeau à la fin du chemin d'un motif indique qu'un mot se termine à ce nœud.
void insererMotif(const std::string& motif) {
int noeudActuel = 0; // Commencer à la racine du Trie
for (char c : motif) {
int index = c - 'a'; // Supposons des caractères minuscules 'a'-'z'
if (transitions[noeudActuel][index] == 0) {
transitions[noeudActuel][index] = ++compteurNoeuds;
}
noeudActuel = transitions[noeudActuel][index];
}
nombreOccurrences[noeudActuel]++; // Marque la fin d'un motif
}
2. Construction des Liens d'Échec
Les liens d'échec sont construits en utilisant un parcours en largeur (BFS). La racine a un lien d'échec vers elle-même (ou vers un nœud fictif, souvent 0). Pour tous les enfants des nœuds déjà traités, leur lien d'échec est déterminé en suivant le lien d'échec de leur parent et en essayant de trouver une transition pour le même caractère. Si une transition existe, le lien d'échec est défini sur ce nœud ; sinon, il suit la chaîne des lians d'échec jusqu'à ce qu'une transition soit trouvée ou que la racine soit atteinte.
void construireLiensEchec() {
std::queue<int> q;
// Initialiser les liens d'échec pour les enfants directs de la racine
// et les ajouter à la file
for (int i = 0; i < ALPHABET_SIZE; ++i) {
if (transitions[0][i] != 0) {
liensEchec[transitions[0][i]] = 0; // Les enfants de la racine échouent vers la racine
q.push(transitions[0][i]);
}
}
while (!q.empty()) {
int noeudActuel = q.front();
q.pop();
for (int i = 0; i < ALPHABET_SIZE; ++i) {
if (transitions[noeudActuel][i] != 0) {
// Si l'enfant existe, son lien d'échec pointe vers
// la transition pour le même caractère à partir du lien d'échec du parent.
liensEchec[transitions[noeudActuel][i]] = transitions[liensEchec[noeudActuel]][i];
q.push(transitions[noeudActuel][i]);
} else {
// Si l'enfant n'existe pas, optimiser le Trie en le faisant pointer
// directement vers la transition correspondante via le lien d'échec.
// Cela permet de ne pas remonter explicitement le lien d'échec à chaque pas lors de la recherche.
transitions[noeudActuel][i] = transitions[liensEchec[noeudActuel]][i];
}
}
}
}
Recherche des Motifs dans le Texte
Pour rechercher des motifs dans un texte, nous traversons le texte caractère par caractère. À chaque caractère, nous passons à l'état suivant dans le Trie. Si une correspondance est trouvée (c'est-à-dire que nous atteignons un nœud où un motif se termine), nous ajoutons le nombre d'occurrences. Ensuite, nous utilisons les liens d'échec pour remonter et trouver d'autres motifs qui pourraient se terminer à cette position ou être des suffixes du motif actuel. Les nœuds de motif trouvés sont souvent marqués (par exemple, en mettant leur compteur à -1) pour éviter de les compter plusieurs fois si plusieurs chemins y mènent.
int rechercherMotifs(const std::string& texte) {
int noeudActuel = 0;
int totalMotifsTrouves = 0;
for (char c : texte) {
int index = c - 'a';
// Avancer dans le Trie ou suivre les liens d'échec implicitement
noeudActuel = transitions[noeudActuel][index];
// Remonter les liens d'échec pour trouver tous les motifs se terminant ici
// et leurs suffixes qui sont aussi des motifs
for (int j = noeudActuel; j != 0 && nombreOccurrences[j] != -1; j = liensEchec[j]) {
totalMotifsTrouves += nombreOccurrences[j];
nombreOccurrences[j] = -1; // Marquer comme visité pour éviter le double comptage
}
}
return totalMotifsTrouves;
}
Code C++ Complet
Voici une implémentation complète de l'automate d'Aho-Corasick pour des caractères minuscules de 'a' à 'z'.
#include <iostream>
#include <string>
#include <vector>
#include <queue>
// Taille de l'alphabet (26 pour les lettres minuscules 'a'-'z')
const int ALPHABET_SIZE = 26;
// Nombre maximal de nœuds dans le Trie (somme des longueurs des motifs + 1)
const int MAX_NODES = 2 * 1000000 + 10;
// Tableau des transitions du Trie
int transitions[MAX_NODES][ALPHABET_SIZE];
// Compteur pour les motifs qui se terminent à un nœud donné
int nombreOccurrences[MAX_NODES];
// Liens d'échec (failure links) pour chaque nœud
int liensEchec[MAX_NODES];
// Compteur pour attribuer un ID unique à chaque nouveau nœud du Trie
int compteurNoeuds = 0;
/**
* @brief Insère un motif dans le Trie.
* @param motif La chaîne de caractères à insérer.
*/
void insererMotif(const std::string& motif) {
int noeudActuel = 0; // Commencer à la racine du Trie
for (char c : motif) {
int index = c - 'a';
if (transitions[noeudActuel][index] == 0) {
transitions[noeudActuel][index] = ++compteurNoeuds;
}
noeudActuel = transitions[noeudActuel][index];
}
nombreOccurrences[noeudActuel]++; // Marque la fin d'un motif
}
/**
* @brief Construit tous les liens d'échec de l'automate à l'aide d'un BFS.
*/
void construireLiensEchec() {
std::queue<int> q;
// Les enfants directs de la racine ont un lien d'échec vers la racine elle-même (nœud 0)
for (int i = 0; i < ALPHABET_SIZE; ++i) {
if (transitions[0][i] != 0) {
liensEchec[transitions[0][i]] = 0;
q.push(transitions[0][i]);
}
}
while (!q.empty()) {
int noeudActuel = q.front();
q.pop();
for (int i = 0; i < ALPHABET_SIZE; ++i) {
if (transitions[noeudActuel][i] != 0) {
// Si une transition pour le caractère 'i' existe depuis le noeud actuel,
// son lien d'échec est la transition pour 'i' à partir du lien d'échec du parent.
liensEchec[transitions[noeudActuel][i]] = transitions[liensEchec[noeudActuel]][i];
q.push(transitions[noeudActuel][i]);
} else {
// Si la transition n'existe pas, optimiser le Trie en la faisant pointer
// directement vers la transition correspondante via le lien d'échec du parent.
// Cela évite de remonter explicitement les liens d'échec pendant la recherche.
transitions[noeudActuel][i] = transitions[liensEchec[noeudActuel]][i];
}
}
}
}
/**
* @brief Recherche toutes les occurrences des motifs dans un texte donné.
* Les motifs trouvés sont marqués comme visités pour éviter le double comptage.
* @param texte Le texte dans lequel rechercher les motifs.
* @return Le nombre total d'occurrences de motifs trouvées.
*/
int rechercherMotifs(const std::string& texte) {
int noeudActuel = 0;
int totalMotifsTrouves = 0;
for (char c : texte) {
int index = c - 'a';
// Se déplacer dans l'automate. Grâce à la construction des liens d'échec,
// cette étape gère automatiquement les cas d'échec sans boucle explicite.
noeudActuel = transitions[noeudActuel][index];
// Parcourir les liens d'échec pour compter tous les motifs se terminant à la position actuelle
// ou qui sont des suffixes valides.
for (int j = noeudActuel; j != 0 && nombreOccurrences[j] != -1; j = liensEchec[j]) {
totalMotifsTrouves += nombreOccurrences[j];
nombreOccurrences[j] = -1; // Marquer ce motif comme compté
}
}
return totalMotifsTrouves;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n; // Nombre de motifs
std::cin >> n;
// Insérer tous les motifs dans le Trie
for (int i = 0; i < n; ++i) {
std::string motif;
std::cin >> motif;
insererMotif(motif);
}
// Construire les liens d'échec
construireLiensEchec();
std::string textePrincipal; // Le texte dans lequel rechercher
std::cin >> textePrincipal;
// Effectuer la recherche et afficher le résultat
std::cout << rechercherMotifs(textePrincipal) << std::endl;
return 0;
}
Complexité
La complexité de l'algorithme d'Aho-Corasick est très efficace :
- Construction du Trie : O(L), où L est la somme des longueurs de tous les motifs.
- Construction des liens d'échec : O(L * Σ), où Σ est la taille de l'alphabet. Une optimisation pour la phase de construction des liens d'échec peut réduire cela à O(L) en utilisant les transitions précalculées pour les liens d'échec.
- Recherche : O(M + K), où M est la longueur du texte et K est le nombre total de motifs trouvés (en tenant compte de l'optmiisation de marquage pour éviter les doubles comptages). Sans cette optimisation de marquage, le coût pourrait être plus élevé en cas de nombreux motifs chevauchants, mais l'approche de marquage assure que chaque contribution est comptée une seule fois par chemin d'échec.