Maîtrisez la recherche de chaînes avec l'algorithme Aho-Corasick

La manipulation de chaînes et la recherche de modèles dans celles-ci sont des tâches fondamentales en science des données et une tâche typique pour tout programmeur.

Les algorithmes de chaîne efficaces jouent un rôle important dans de nombreux processus de science des données. Souvent, ce sont eux qui rendent ces processus suffisamment réalisables pour une utilisation pratique.

Dans cet article, vous découvrirez l'un des algorithmes les plus puissants pour rechercher des motifs dans une grande quantité de texte : l'algorithme Aho-Corasick. Cet algorithme utilise une structure de données trie (prononcé « essayer ») pour garder une trace des modèles de recherche et utilise une méthode simple pour trouver efficacement toutes les occurrences d'un ensemble donné de modèles dans n'importe quel blob de texte.

Un article précédent sur le Toptal Engineering Blog a démontré un algorithme de recherche de chaîne pour le même problème. L'approche adoptée dans cet article offre une complexité de calcul améliorée.

L'algorithme de Knuth-Morris-Pratt (KMP)

Pour comprendre comment nous pouvons rechercher efficacement plusieurs modèles dans un texte, nous devons d'abord nous attaquer à un problème plus simple : rechercher un seul modèle dans un texte donné.

Supposons que nous ayons une grande masse de texte de longueur N et un motif (que nous voulons rechercher dans le texte) de longueur M . Que nous voulions rechercher une seule occurrence de ce modèle, ou toutes les occurrences, nous pouvons atteindre une complexité de calcul de O(N + M) en utilisant l'algorithme KMP.

Fonction de préfixe

L'algorithme KMP fonctionne en calculant une fonction de préfixe du motif que nous recherchons. La fonction de préfixe précalcule une position de repli pour chaque préfixe du motif.

Définissons notre modèle de recherche comme une chaîne, étiquetée S . Pour chaque sous-chaîne S[0..i] , où i >= 1 , nous trouverons le préfixe maximum de cette chaîne qui se trouve être également le suffixe de cette chaîne. Nous allons étiqueter la longueur de ce préfixe P[i] .

Pour le modèle "abracadabra", la fonction de préfixe produirait les positions de repli suivantes :

La fonction de préfixe identifie une caractéristique intéressante du motif.

Prenons un préfixe particulier du modèle comme exemple : "abracadab". La valeur de la fonction de préfixe pour ce préfixe est deux. Cela indique que pour ce préfixe "abracadab", il existe un suffixe de longueur deux qui correspond exactement au préfixe de longueur deux (c'est-à-dire que le modèle commence par "ab" et le préfixe se termine par "ab"). la plus longue correspondance de ce type pour ce préfixe.

Mise en œuvre

Voici une fonction C# qui peut être utilisée pour calculer la fonction de préfixe pour n'importe quelle chaîne :

 public int[] CalcPrefixFunction(String s) { int[] result = new int[s.Length]; // array with prefix function values result[0] = 0; // the prefix function is always zero for the first symbol (its degenerate case) int k = 0; // current prefix function value for (int i = 1; i < s.Length; i++) { // We're jumping by prefix function values to try smaller prefixes // Jumping stops when we find a match, or reach zero // Case 2 if we stop at a zero-length prefix // Case 3 if we stop at a match while (k > 0 && s[i] != s[k]) k = result[k - 1]; if (s[k] == s[i]) k++; // we've found the longest prefix - case 1 result[i] = k; // store this result in the array } return result; }

L'exécution de cette fonction sur un modèle légèrement plus long "abcdabcabcdabcdab" produit ceci :

Complexité informatique

Malgré le fait qu'il y a deux boucles imbriquées, la complexité de la fonction de préfixe est juste O(M) , où M est la longueur du motif S .

Cela s'explique facilement en observant le fonctionnement des boucles.

Toutes les itérations de la boucle externe jusqu'à i peuvent être divisées en trois cas :

1. Augmente k de un. La boucle effectue une itération.

2. Ne change pas la valeur zéro de k . La boucle effectue une itération.

3. Ne change pas ou diminue une valeur positive de k .

Les deux premiers cas peuvent s'exécuter au plus M fois.

Pour le troisième cas, définissons P(s, i) = k1 et P(s, i + 1) = k2, k2 <= k1 . Chacun de ces cas doit être précédé de k1 - k2 occurrences du premier cas. Le nombre de diminutions ne dépasse pas k1 - k2 + 1 . Et au total nous n'avons pas plus de 2 * M itérations.

Explication du deuxième exemple

Regardons le deuxième modèle d'exemple "abcdabcabcdabcdab". Voici comment la fonction de préfixe le traite, étape par étape :

1. Pour une sous-chaîne vide et la sous-chaîne "a" de longueur un, la valeur de la fonction de préfixe est définie sur zéro. ( k = 0 )

2. Regardez la sous-chaîne "ab". La valeur actuelle de k est zéro et le caractère "b" n'est pas égal au caractère "a". Ici, nous avons le deuxième cas de la section précédente. La valeur de k reste à zéro et la valeur de la fonction de préfixe pour la sous-chaîne "ab" est également zéro.

3. C'est le même cas pour les sous-chaînes "abc" et "abcd". Il n'y a pas de préfixes qui soient également les suffixes de ces sous-chaînes. La valeur pour eux reste à zéro.

4. Examinons maintenant un cas intéressant, la sous-chaîne « abcda ». La valeur actuelle de k est toujours zéro, mais le dernier caractère de notre sous-chaîne correspond à son premier caractère. Cela déclenche la condition de s[k] == s[i] , où k == 0 et i == 4 . Le tableau est indexé à zéro et k est l'index du caractère suivant pour le préfixe de longueur maximale. Cela signifie que nous avons trouvé le préfixe de longueur maximale pour notre sous-chaîne qui est également un suffixe. Nous avons le premier cas, où la nouvelle valeur de k est un, et donc la valeur de la fonction de préfixe P(“abcda”) est un.

5. Le même cas se produit également pour les deux sous-chaînes suivantes, P("abcdab") = 2 et P("abcdabc") = 3 . Ici, nous recherchons notre modèle dans le texte, en comparant les chaînes caractère par caractère. Supposons que les sept premiers caractères du modèle correspondent à environ sept caractères consécutifs de texte traité, mais que le huitième caractère ne correspond pas. Que devrait-il se passer ensuite ? Dans le cas d'une correspondance de chaîne naïve, nous devons renvoyer sept caractères en arrière et recommencer le processus de comparaison à partir du premier caractère de notre modèle. Avec la valeur de la fonction de préfixe (ici P("abcdabc") = 3 ), nous savons que notre suffixe à trois caractères correspond déjà à trois caractères de texte. Et si le caractère suivant dans le texte est "d", la longueur de la sous-chaîne correspondante de notre modèle et de la sous-chaîne dans le texte est augmentée à quatre ("abcd"). Sinon, P(“abc”) = 0 et nous commencerons le processus de comparaison à partir du premier caractère du motif. Mais ce qui est important, c'est qu'on ne revienne pas pendant le traitement du texte.

6. La sous-chaîne suivante est "abcdabca". Dans la sous-chaîne précédente, la fonction de préfixe était égale à trois. Cela signifie que k = 3 est supérieur à zéro, et en même temps nous avons une discordance entre le caractère suivant dans le préfixe ( s[k] = s[3] = "d" ) et le caractère suivant dans le suffixe ( s[i] = s[7] = "a" ). Cela signifie que nous avons déclenché la condition de s[k] != s[i] , et que le préfixe « abcd » ne peut pas être le suffixe de notre chaîne. Nous devrions diminuer la valeur de k et prendre le préfixe précédent pour comparaison, si possible. Comme nous l'avons décrit ci-dessus, le tableau est indexé à zéro et k est l'index du prochain caractère que nous vérifions à partir du préfixe. Le dernier index du préfixe actuellement mis en correspondance est k - 1 . Nous prenons la valeur de la fonction de préfixe pour le préfixe actuellement apparié k = result[k - 1] . Dans notre cas (le troisième cas), la longueur du préfixe maximum sera réduite à zéro, puis dans la ligne suivante, elle sera augmentée jusqu'à un, car "a" est le préfixe maximum qui est également le suffixe de notre sous-chaîne.

7. (Ici, nous continuons notre processus de calcul jusqu'à ce que nous arrivions à un cas plus intéressant.)

8. Nous commençons à traiter la sous-chaîne suivante : "abcdabcabcdabcd". La valeur actuelle de k est sept. Comme avec "abcdabca" ci-dessus, nous avons rencontré une non-correspondance : étant donné que le caractère "a" (le septième caractère) n'est pas égal au caractère "d", la sous-chaîne "abcdabca" ne peut pas être le suffixe de notre chaîne. Nous obtenons maintenant la valeur déjà calculée de la fonction de préfixe pour « abcdabc » (trois) et nous avons maintenant une correspondance : le préfixe « abcd » est également le suffixe de notre chaîne. Son préfixe maximum et la valeur de la fonction de préfixe pour notre sous-chaîne est de quatre, car c'est ce que la valeur actuelle de k est devenue.

9. Nous continuons ce processus jusqu'à la fin du motif.

En bref : Les deux cycles ne prennent pas plus de 3 M itérations, ce qui prouve que la complexité est O(M). L'utilisation de la mémoire est également O(M).

Implémentation de l'algorithme KMP

 public int KMP(String text, String s) { int[] p = CalcPrefixFunction(s); // Calculate prefix function for a pattern string // The idea is the same as in the prefix function described above, but now // we're comparing prefixes of text and pattern. // The value of maximum-length prefix of the pattern string that was found // in the text: int maxPrefixLength = 0; for (int i = 0; i < text.Length; i++) { // As in the prefix function, we're jumping by prefixes until k is // greater than 0 or we find a prefix that has matches in the text. while (maxPrefixLength > 0 && text[i] != s[maxPrefixLength]) maxPrefixLength = p[maxPrefixLength - 1]; // If a match happened, increase the length of the maximum-length // prefix. if (s[maxPrefixLength] == text[i]) maxPrefixLength++; // If the prefix length is the same length as the pattern string, it // means that we have found a matching substring in the text. if (maxPrefixLength == s.Length) { // We can return this value or perform this operation. int idx = i - s.Length + 1; // Get the previous maximum-length prefix and continue search. maxPrefixLength = p[maxPrefixLength - 1]; } } return -1; }

L'algorithme ci-dessus parcourt le texte, caractère par caractère, et essaie d'augmenter le préfixe maximum pour notre modèle et une séquence de caractères consécutifs dans le texte. En cas d'échec nous ne reviendrons pas sur notre position antérieure dans le texte. Nous connaissons le préfixe maximum de la sous-chaîne trouvée du motif ; ce préfixe est aussi le suffixe de cette sous-chaîne trouvée et nous pouvons simplement continuer la recherche.

La complexité de cette fonction est la même que celle de la fonction de préfixe, ce qui rend la complexité de calcul globale O(N + M) avec une mémoire O(M) .

Trivia : Les méthodes String.IndexOf() et String.Contains() dans le framework .NET ont un algorithme avec la même complexité sous le capot.

L'algorithme Aho-Corasick

Maintenant, nous voulons faire la même chose pour plusieurs modèles.

Supposons qu'il existe M motifs de longueurs L1 , L2 , …, Lm . Nous devons trouver toutes les correspondances de motifs d'un dictionnaire dans un texte de longueur N .

Une solution triviale serait de prendre n'importe quel algorithme de la première partie et de l'exécuter M fois. Nous avons une complexité de O(N + L1 + N + L2 + … + N + Lm) , soit O(M * N + L) .

Tout test suffisamment sérieux tue cet algorithme.

Prendre un dictionnaire avec les 1 000 mots anglais les plus courants comme modèles et l'utiliser pour rechercher la version anglaise de "Guerre et Paix" de Tolstoï prendrait un certain temps. Le livre compte plus de trois millions de caractères.

Si nous prenons les 10 000 mots anglais les plus courants, l'algorithme fonctionnera environ 10 fois plus lentement. Évidemment, sur des entrées supérieures à celle-ci, le temps d'exécution augmentera également.

C'est là que l'algorithme Aho-Corasick fait sa magie.

La complexité de l'algorithme Aho-Corasick est O(N + L + Z) , où Z est le nombre de correspondances. Cet algorithme a été inventé par Alfred V. Aho et Margaret J. Corasick en 1975.

Mise en œuvre

Ici, nous avons besoin d'un trie, et nous ajoutons à notre algorithme une idée similaire aux fonctions de préfixe décrites ci-dessus. Nous calculerons les valeurs des fonctions de préfixe pour l'ensemble du dictionnaire.

Chaque sommet du trie stockera les informations suivantes :

 public class Vertex { public Vertex() { Children = new Hashtable(); Leaf = false; Parent = -1; SuffixLink = -1; WordID = -1; EndWordLink= -1; } // Links to the child vertexes in the trie: // Key: A single character // Value: The ID of vertex public Hashtable Children; // Flag that some word from the dictionary ends in this vertex public bool Leaf; // Link to the parent vertex public int Parent; // Char which moves us from the parent vertex to the current vertex public char ParentChar; // Suffix link from current vertex (the equivalent of P[i] from the KMP algorithm) public int SuffixLink; // Link to the leaf vertex of the maximum-length word we can make from the current prefix public int EndWordLink; // If the vertex is the leaf, we store the ID of the word public int WordID; }

Il existe plusieurs façons d'implémenter des liens enfants. L'algorithme aura une complexité de O(N + L + Z) dans le cas d'un tableau, mais cela aura un besoin supplémentaire en mémoire de O(L * q) , où q est la longueur de l'alphabet, puisque c'est le nombre maximum d'enfants qu'un nœud peut avoir.

Si nous utilisons une structure avec un accès O(log(q)) à ses éléments, nous avons un besoin supplémentaire en mémoire de O(L) , mais la complexité de l'ensemble de l'algorithme sera O((N + L) * log(q) + Z) .

Dans le cas d'une table de hachage, nous avons O(L) mémoire supplémentaire, et la complexité de l'ensemble de l'algorithme sera O(N + L + Z) .

Ce didacticiel utilise une table de hachage car il fonctionnera également avec différents jeux de caractères, par exemple les caractères chinois.

Nous avons déjà une structure pour un sommet. Ensuite, nous allons définir une liste de sommets et initialiser le nœud racine du trie.

 public class Aho { List<Vertex> Trie; List<int> WordsLength; int size = 0; int root = 0; public Aho() { Trie = new List<Vertex>(); WordsLength = new List<int>(); Init(); } private void Init() { Trie.Add(new Vertex()) size++; } }

Ensuite, nous ajoutons tous les motifs au trie. Pour cela, nous avons besoin d'une méthode pour ajouter un mot au trie :

 public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i < s.Length; ++i) // Iterating over the string's characters { char c = s[i]; // Checking if a vertex with this edge exists in the trie: if (!Trie[curVertex].Children.ContainsKey(c)) { Trie.Add(new Vertex()); Trie[size].SuffixLink = -1; // If not - add vertex Trie[size].Parent = curVertex; Trie[size].ParentChar = c; Trie[curVertex].Children[c] = size; size++; } curVertex = (int)Trie[curVertex].Children[c]; // Move to the new vertex in the trie } // Mark the end of the word and store its ID Trie[curVertex].Leaf = true; Trie[curVertex].WordID = wordID; WordsLength.Add(s.Length); }

A ce stade, tous les mots de modèle sont dans la structure de données. Cela nécessite une mémoire supplémentaire de O(L) .

Ensuite, nous devons calculer tous les liens de suffixe et les liens d'entrée de dictionnaire.

Pour le rendre clair et simple à comprendre, je vais parcourir notre trie de la racine aux feuilles et faire des calculs similaires à ceux que nous avons faits pour l'algorithme KMP, mais contrairement à l'algorithme KMP, où nous trouvons la longueur maximale préfixe qui était également le suffixe de la même sous-chaîne, nous allons maintenant trouver le suffixe de longueur maximale de la sous-chaîne actuelle qui est également le préfixe d'un motif dans le trie. La valeur de cette fonction ne sera pas la longueur du suffixe trouvé ; ce sera le lien vers le dernier caractère du suffixe maximum de la sous-chaîne courante. C'est ce que je veux dire par le lien suffixe d'un sommet.

Je vais traiter les sommets par niveaux. Pour cela, je vais utiliser un algorithme de recherche en largeur (BFS) :

Et ci-dessous est la mise en œuvre de cette traversée:

 public void PrepareAho() { Queue<int> vertexQueue = new Queue<int>(); vertexQueue.Enqueue(root); while (vertexQueue.Count > 0) { int curVertex = vertexQueue.Dequeue(); CalcSuffLink(curVertex); foreach (char key in Trie[curVertex].Children.Keys) { vertexQueue.Enqueue((int)Trie[curVertex].Children[key]); } } }

Et ci-dessous se trouve la méthode CalcSuffLink pour calculer le lien de suffixe pour chaque sommet (c'est-à-dire la valeur de la fonction de préfixe pour chaque sous-chaîne du trie):

 public void CalcSuffLink(int vertex) { // Processing root (empty string) if (vertex == root) { Trie[vertex].SuffixLink = root; Trie[vertex].EndWordLink = root; return; } // Processing children of the root (one character substrings) if (Trie[vertex].Parent == root) { Trie[vertex].SuffixLink = root; if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; return; } // Cases above are degenerate cases as for prefix function calculation; the // value is always 0 and links to the root vertex. // To calculate the suffix link for the current vertex, we need the suffix // link for the parent of the vertex and the character that moved us to the // current vertex. int curBetterVertex = Trie[Trie[vertex].Parent].SuffixLink; char chVertex = Trie[vertex].ParentChar; // From this vertex and its substring we will start to look for the maximum // prefix for the current vertex and its substring. while (true) { // If there is an edge with the needed char, we update our suffix link // and leave the cycle if (Trie[curBetterVertex].Children.ContainsKey(chVertex)) { Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex]; break; } // Otherwise, we are jumping by suffix links until we reach the root // (equivalent of k == 0 in prefix function calculation) or we find a // better prefix for the current substring. if (curBetterVertex == root) { Trie[vertex].SuffixLink = root; break; } curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink } // When we complete the calculation of the suffix link for the current // vertex, we should update the link to the end of the maximum length word // that can be produced from the current substring. if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; }

La complexité de cette méthode est O(L) ; selon l'implémentation de la collection enfant, la complexité peut être O(L * log(q)) .

La preuve de complexité est similaire à la fonction de préfixe de preuve de complexité dans l'algorithme KMP.

Regardons l'image suivante. Ceci est une visualisation du trie pour le dictionnaire { abba, cab, baba, caab, ac, abac, bac } avec toutes ses informations calculées :

Les bords des tris sont bleu foncé, les liens de suffixe sont en bleu clair et les liens de suffixe du dictionnaire en vert. Les nœuds correspondant aux entrées du dictionnaire sont surlignés en bleu.

Et maintenant, nous n'avons besoin que d'une seule méthode de plus - traiter un bloc de texte dans lequel nous avons l'intention de rechercher :

 public int ProcessString(String text) { // Current state value int currentState = root; // Targeted result value int result = 0; for (int j = 0; j < text.Length; j++) { // Calculating new state in the trie while (true) { // If we have the edge, then use it if (Trie[currentState].Children.ContainsKey(text[j])) { currentState = (int)Trie[currentState].Children[text[j]]; break; } // Otherwise, jump by suffix links and try to find the edge with // this char // If there aren't any possible edges we will eventually ascend to // the root, and at this point we stop checking. if (currentState == root) break; currentState = Trie[currentState].SuffixLink; } int checkState = currentState; // Trying to find all possible words from this prefix while (true) { // Checking all words that we can get from the current prefix checkState = Trie[checkState].EndWordLink; // If we are in the root vertex, there are no more matches if (checkState == root) break; // If the algorithm arrived at this row, it means we have found a // pattern match. And we can make additional calculations like find // the index of the found match in the text. Or check that the found // pattern is a separate word and not just, eg, a substring. result++; int indexOfMatch = j + 1 - WordsLength[Trie[checkState].WordID]; // Trying to find all matched patterns of smaller length checkState = Trie[checkState].SuffixLink; } } return result; }

Et maintenant c'est prêt à l'emploi :

En entrée, nous avons une liste de motifs :

 List<string> patterns;

Et texte de recherche :

 string text;

Et voici comment le coller ensemble :

 // Init the trie structure. As an optional parameter we can put the approximate // size of the trie to allocate memory just once for all nodes. Aho ahoAlg = new Aho(); for (int i = 0; i < patterns.Count; i++) { ahoAlg.AddString(patterns[i], i); // Add all patterns to the structure } // Prepare algorithm for work (calculates all links in the structure): ahoAlg.PrepareAho(); // Process the text. Output might be different; in my case, it's a count of // matches. We could instead return a structure with more detailed information. int countOfMatches = ahoAlg.ProcessString(text);

Et c'est tout! Vous savez maintenant comment fonctionne cet algorithme simple mais puissant !

Aho-Corasick est vraiment flexible. Les modèles de recherche ne doivent pas nécessairement être uniquement des mots, mais nous pouvons utiliser des phrases entières ou des chaînes de caractères aléatoires.

Performance

L'algorithme a été testé sur un Intel Core i7-4702MQ.

Pour les tests, j'ai pris deux dictionnaires : Les 1 000 mots anglais les plus courants et les 10 000 mots anglais les plus courants.

Pour ajouter tous ces mots au dictionnaire et préparer la structure de données pour fonctionner avec chacun des dictionnaires, l'algorithme a nécessité respectivement 55 ms et 135 ms.

L'algorithme a traité de vrais livres de 3 à 4 millions de caractères en 1,0 à 1,3 seconde, alors qu'il a fallu 9,6 secondes pour un livre d'environ 30 millions de caractères.

Paralléliser l'algorithme Aho-Corasick

Aller en parallèle avec l'algorithme Aho-Corasick n'est pas du tout un problème :

Un texte volumineux peut être divisé en plusieurs morceaux et plusieurs threads peuvent être utilisés pour traiter chaque morceau. Chaque thread a accès au trie généré en fonction du dictionnaire.

Qu'en est-il des mots divisés à la frontière entre les morceaux ? Ce problème peut être résolu facilement.

Soit N la longueur de notre grand texte, S la taille d'un morceau et L la longueur du plus grand motif du dictionnaire.

Maintenant, nous pouvons utiliser une astuce simple. Nous divisons les morceaux avec un certain chevauchement à la fin, par exemple en prenant [S * (i - 1), S * i + L - 1] , où i est l'indice du morceau. Lorsque nous obtenons une correspondance de modèle, nous pouvons facilement obtenir l'index de début de la correspondance actuelle et vérifier simplement que cet index se trouve dans la plage de blocs sans chevauchements, [S * (i - 1), S * i - 1] .

Un algorithme de recherche de chaînes polyvalent

L'algorithme Aho-Corasick est un puissant algorithme de correspondance de chaînes qui offre la meilleure complexité pour n'importe quelle entrée et ne nécessite pas beaucoup de mémoire supplémentaire.

L'algorithme est souvent utilisé dans divers systèmes, tels que les correcteurs orthographiques, les filtres anti-spam, les moteurs de recherche, la recherche de séquences bioinformatiques/ADN, etc. En fait, certains outils populaires que vous utilisez peut-être tous les jours utilisent cet algorithme dans les coulisses.

La fonction de préfixe de l'algorithme KMP en elle-même est un outil intéressant qui ramène la complexité de l'appariement à un seul motif au temps linéaire. L'algorithme Aho-Corasick suit une approche similaire et utilise une structure de données en trie pour faire la même chose pour plusieurs modèles.

J'espère que vous avez trouvé ce tutoriel sur l'algorithme Aho-Corasick utile.