Science Des Données Et Bases De Données
Conquérir la recherche de chaînes avec l'algorithme Aho-Corasick
La manipulation de chaînes et leur recherche de modèles sont des tâches fondamentales de la science des données et une tâche typique de tout programmeur.
Des algorithmes de chaînes efficaces jouent un rôle important dans de nombreux processus de science des données. Ce sont souvent 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 trouver des modèles dans une grande quantité de texte: l'algorithme Aho-Corasick. Cet algorithme utilise un structure de données trie (prononcé 'essayez') 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 quelle bulle de texte.
Un article précédent sur le blog d'ingénierie ApeeScape a présenté un algorithme de recherche de chaînes pour le même problème. L'approche adoptée dans cet article offre une meilleure complexité de calcul.
L'algorithme Knuth-Morris-Pratt (KMP)
Pour comprendre comment rechercher efficacement plusieurs motifs dans un texte, nous devons d'abord nous attaquer à un problème plus simple: rechercher un seul motif dans un texte donné.
Supposons que nous ayons une grande goutte de texte de longueur N et un motif (que nous voulons trouver dans le texte) de longueur M . Si nous voulons 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 alternative pour chaque préfixe du modèle.
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 est également le suffixe de cette chaîne. Nous marquerons la longueur de ce préfixe P [i].
Pour le motif «abracadabra», la fonction de préfixe produirait les positions de support suivantes:
Index (i) | 0 | un | 2 | 3 | 4 | 5 | 6 | sept | 8 | 9 | dix |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Personnage | à | b | r | à | c | à | ré | à | b | r | à |
Longueur du préfixe (P[i]) | 0 | 0 | 0 | un | 0 | un | 0 | un | 2 | 3 | 4 |
La fonction de préfixe identifie une caractéristique intéressante du modèle.
Prenons un préfixe particulier du motif comme exemple: 'abracadab'. La valeur de la fonction de préfixe pour ce préfixe est de 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 motif commence par «ab» et le préfixe se termine par «ab»). Il s'agit également de la correspondance la plus longue pour ce préfixe.
la mise en oeuvre
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]; // matriz con valores de función de prefijo result[0] = 0; // la función de prefijo siempre es cero para el primer símbolo (su caso degenerado) int k = 0; // valor actual de la función de prefijo para (int i = 1; i 0 && s[i] != s[k]) k = result[k - 1]; if (s[k] == s[i]) k++; // hemos encontrado el prefijo más largo - caso 1 result[i] = k; // almacenar este resultado en la matriz } resultado de devolución; } L'exécution de cette fonction dans un modèle légèrement plus long, 'abcdabcabcdabcdab' produit ceci:
comment écrire un langage de programmation
Index (i) | 0 | un | 2 | 3 | 4 | 5 | 6 | sept | 8 | 9 | dix | Onze | 12 | 13 | 14 | quinze | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Personnage | à | b | c | ré | à | b | c | à | b | c | ré | à | b | c | ré | à | b |
Fonction de préfixe (P[i]) | 0 | 0 | 0 | 0 | un | 2 | 3 | un | 2 | 3 | 4 | 5 | 6 | sept | 4 | 5 | 6 |
Complexité informatique
Même s'il y a deux boucles imbriquées, la complexité de la fonction de préfixe est simplement O (M) , où M est la longueur du motif S .
Cela peut être facilement expliqué en examinant le fonctionnement des boucles.
Toutes les itérations de la boucle externe via i Ils peuvent être divisés en trois cas:
-
Augmenter
kdans une. La boucle termine une itération. -
Ne modifie pas la valeur zéro de
k. La boucle termine une itération. -
Il ne change ni ne diminue une valeur positive de
k.
Les deux premiers cas peuvent être exécutés 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é des occurrences k1 - k2 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 exemple de modèle 'abcdabcabcdabcdab'. Voici comment la fonction de préfixe le traite, étape par étape:
-
Pour une sous-chaîne vide et la sous-chaîne 'a' de longueur un, la valeur de la fonction de préfixe est mise à zéro. (
k = 0) -
Regardez la sous-chaîne 'ab'. La valeur actuelle de
kest égal à 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 dekreste zéro et la valeur de la fonction de préfixe pour la sous-chaîne 'ab' est également zéro. -
Il en est de même pour les sous-chaînes 'abc' et 'abcd'. Il n'y a pas de préfixes qui sont également les suffixes de ces sous-chaînes. La valeur pour eux reste nulle.
-
Regardons maintenant un cas intéressant, la sous-chaîne 'abcda'. La valeur actuelle de
kil est toujours nul, mais le dernier caractère de notre sous-chaîne correspond à son premier caractère. Cela déclenche la condition des [k] == s [i], oùk == 0eti == 4. Le tableau a un index zéro etkest l'index du caractère suivant 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 dekest un, et donc la valeur de la fonction de préfixe P ('abcda') C'est un. -
Le même cas se produit également pour les deux sous-chaînes suivantes, P («abcdab») = 2 Oui P («abcdabc») = 3 . Ici, nous recherchons notre motif dans le texte, en comparant les chaînes caractère par caractère. Disons que les sept premiers caractères du modèle correspondent à environ sept caractères consécutifs du 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 devrions retourner sept caractères et recommencer le processus de comparaison à partir du premier caractère de notre modèle. Avec la valeur de la fonction prefix (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'). Au contraire, P («abc») = 0 et nous commencerons le processus de comparaison à partir du premier caractère du motif. Mais l'important est de ne pas revenir en arrière lors du traitement de texte.
-
La sous-chaîne suivante est 'abcdabca'. Dans la sous-chaîne ci-dessus, la fonction de préfixe était égale à trois. Cela signifie que
k = 3est 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 activons la condition des [k]! =S [i], et que le préfixe 'abcd' ne peut pas être le suffixe de notre chaîne. Nous devrions diminuer la valeur deket prenez le préfixe ci-dessus pour comparer, si possible. Comme nous l'avons décrit précédemment, le tableau a un index zéro etkest l'indice du caractère suivant que nous vérifions à partir du préfixe. Le dernier index du préfixe actuellement correspondant estk - 1. Nous prenons la valeur de la fonction de préfixe pour le préfixe correspondant actuellementk = resultado [k - 1]. Dans notre cas (le troisième cas), la longueur du préfixe maximum sera réduite à zéro puis sur la ligne suivante elle sera augmentée à un, car «a» est le préfixe maximum qui est aussi le suffixe de notre sous-chaîne. -
(Ici, nous continuons notre processus de calcul jusqu'à ce que nous arrivions à un cas plus intéressant.)
-
Nous commençons à traiter la sous-chaîne suivante: 'abcdabcabcdabcd'. La valeur actuelle de
kest sept. Comme pour 'abcdabca' ci-dessus, nous avons rencontré une non-correspondance: Parce 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. Maintenant, nous obtenons la valeur déjà calculée de la fonction de préfixe pour «abcdabc» (trois) et maintenant nous avons 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 sont quatre, car c'est la valeur actuelle dek. -
Nous continuons ce processus jusqu'à la fin du modèle.
En bref: les deux cycles ne prennent pas plus de 3M itérations, ce qui montre 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); // Calcular la función de prefijo para una cadena de patrón // La idea es la misma que en la función de prefijo descrita anteriormente, pero ahora // estamos comparando prefijos de texto y patrón. // El valor del prefijo de longitud máxima de la cadena del patrón que se encontró // en el texto: int maxPrefixLength = 0; for (int i = 0; i 0 && text[i] != s[maxPrefixLength]) maxPrefixLength = p[maxPrefixLength - 1]; // Si ocurrió una coincidencia, aumenta la longitud de la longitud máxima // prefijo. if (s[maxPrefixLength] == text[i]) maxPrefixLength++; // Si la longitud del prefijo tiene la misma longitud que la cadena del patrón, // significa que hemos encontrado una subcadena coincidente en el texto. if (maxPrefixLength == s.Length) { // Podemos devolver este valor o realizar esta operación. int idx = i - s.Length + 1; // Obtenga el prefijo de longitud máxima anterior y continúe la búsqueda. 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 à notre position précédente dans le texte. Nous connaissons le préfixe maximum de la sous-chaîne trouvée du motif; ce préfixe est également 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 pour la fonction de préfixe, ce qui rend la complexité globale du calcul O (N + M) avec O (M) Mémoire.
Trivia: Le
String.IndexOf ()etString.Contains ()dans le framework .NET, ils 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 y ait des modèles M de longueurs L1 , L2 , ..., Lm . Nous devons trouver toutes les correspondances de motifs à partir 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) , c'est-à-dire (M * N + L) .
Tout test suffisamment sérieux tue cet algorithme.
Prendre un dictionnaire avec les 1000 mots anglais les plus courants comme modèles et l'utiliser pour rechercher la version anglaise de «War and Peace» de Tolstoï prendrait un certain temps. Le livre compte plus de trois millions de caractères.
Si nous prenons les 10000 mots les plus courants en anglais, l'algorithme fonctionnera environ 10 fois plus lentement. Évidemment, sur des entrées supérieures à cela, le temps d'exécution augmentera également.
C'est là que l'algorithme Aho-Corasick opère sa magie.
La complexité de l'algorithme Aho-Corasick est O (N + L + Z) , où AVEC est le nombre de correspondances. Cet algorithme a été inventé par Alfred V. Aho Oui Margaret J. Corasick en 1975.
la mise en oeuvre
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 tout le 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; } // Enlaces a los vértices secundarios en el trie: // Clave: Un solo caracter // Valor: El ID del vértice public Hashtable Children; // Indica que una palabra del diccionario termina en este vértice public bool Leaf; // Enlace al vértice padre public int Parent; // Char que nos mueve desde el vértice padre al vértice actual public char ParentChar; // Enlace de sufijo del vértice actual (el equivalente de P [i] del algoritmo KMP) public int SuffixLink; // Enlace al vértice de hoja de la palabra de longitud máxima que podemos hacer con el prefijo actual public int EndWordLink; // Si el vértice es la hoja, guardamos el ID de la palabra public int WordID; } Il existe plusieurs façons d'implémenter des liens secondaires. L'algorithme aura une complexité de O (N + L + Z) dans le cas d'un tableau, mais cela nécessitera une mémoire supplémentaire 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 O (log (q)) accès à ses éléments, nous avons un besoin de mémoire supplémentaire de O (L) , mais la complexité de l'algorithme complet 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 tout 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 des caractères chinois.
Nous avons déjà une structure pour un sommet. Ensuite, nous allons définir une liste de sommets et démarrer le nœud racine du trie.
public class Aho { List Trie; List WordsLength; int size = 0; int root = 0; public Aho() { Trie = new List(); WordsLength = new List(); Init(); } private void Init() { Trie.Add(new Vertex()) size++; } } Ensuite, nous ajoutons tous les modèles au trie. Pour cela, nous avons besoin d'une méthode pour ajouter des mots au trie:
public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i À 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 du dictionnaire.
Pour être clair et simple à comprendre, je vais parcourir notre trie de la racine aux feuilles et faire des calculs similaires à ce que nous avons fait pour l'algorithme KMP, mais contrairement à l'algorithme KMP, où nous trouvons la longueur maximale du 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é; sera le lien vers le dernier caractère du suffixe maximum de la sous-chaîne courante. C'est ce que j'entends par le suffixe de lien d'un sommet.
Je traiterai les sommets par niveaux. Pour cela, j'utiliserai un algorithme recherche par largeur (BFS) :
Et ci-dessous est la mise en œuvre de ce crossover:
public void PrepareAho() { Queue vertexQueue = new Queue(); 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 est la méthode CalcSuffLink pour calculer la liaison 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; } // Procesamiento de hijos de la raíz (subcadenas de un caracter) 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; } // Los casos anteriores son casos degenerados en cuanto al cálculo de la función del prefijo; // el valor siempre es 0 y los enlaces al vértice raíz. // Para calcular el sufijo link para el vértice actual, necesitamos el sufijo // enlace para el padre del vértice y el personaje que nos movió a la // vértice actual. int curBetterVertex = Trie[Trie[vertex].Parent].SuffixLink; char chVertex = Trie[vertex].ParentChar; // Desde este vértice y su subcadena comenzaremos a buscar el máximo // prefijo para el vértice actual y su subcadena. while (true) { // Si hay una ventaja con el carácter necesario, actualizamos nuestro enlace de sufijo // y abandonar el ciclo if (Trie[curBetterVertex].Children.ContainsKey(chVertex)) { Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex]; break; } // De lo contrario, estamos saltando por enlaces de sufijo hasta que lleguemos a la raíz // (equivalente a k == 0 en el cálculo de la función de prefijo) o encontramos un // mejor prefijo para la subserie actual. if (curBetterVertex == root) { Trie[vertex].SuffixLink = root; break; } curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink } // Cuando completamos el cálculo del enlace de sufijo para el actual // vertex, debemos actualizar el enlace al final de la palabra de longitud máxima // que se puede producir a partir de la subcadena actual. 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é pourrait être ** O (L * log (q)) **.
Le test de complexité est similaire au test de la fonction de préfixe de complexité dans l'algorithme KMP.
Voyons l'image suivante. Ceci est un affichage du trie pour le dictionnaire {abba, cab, baba, caab, ac, abac, bac} avec toutes vos informations calculées:
Les bordures Trie sont bleu foncé, les liens de suffixe sont bleu clair et les suffixes de dictionnaire sont verts. Les nœuds correspondant aux entrées du dictionnaire sont surlignés en bleu.
Et maintenant, nous avons juste besoin d'une méthode de plus: traiter un bloc de texte que nous avons l'intention de rechercher:
public int ProcessString(String text) { // Estado actual del valor int currentState = root; // Valor de resultado apuntado int result = 0; for (int j = 0; j Et maintenant c'est prêt à être utilisé:
Dans l'entrée, nous avons une liste de modèles:
List patterns; Et recherchez du texte:
string text; Et voici comment coller le tout ensemble:
c société s société différence
// Inicia la estructura trie. Como parámetro opcional podemos poner el aproximado // tamaño del trie para asignar memoria solo una vez para todos los nodos. Aho ahoAlg = new Aho(); for (int i = 0; i Et c'est ça! Vous savez maintenant comment fonctionne cet algorithme simple mais puissant!
Aho-Corasick est vraiment flexible. Les modèles de recherche ne doivent pas être uniquement des mots, mais nous pouvons utiliser des phrases entières ou des chaînes 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 les plus courants en anglais et les 10 000 mots les plus courants en anglais.
Pour ajouter tous ces mots au dictionnaire et préparer la structure de données à travailler 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 secondes, alors qu'il fallait 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 qui sont divisés à la frontière entre les fragments? Ce problème peut être facilement résolu.
Laisser N soit la longueur de notre grand texte, S est la taille d'un fragment, et L être la longueur du plus grand motif du dictionnaire.
Nous pouvons maintenant utiliser une astuce simple. Nous divisons les morceaux avec un 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épart de la correspondance en cours et vérifier simplement que cet index est dans la plage de blocs sans chevauchement, [S * (i - 1), S * i - 1].
Un algorithme de recherche de chaînes polyvalent
L'algorithme Aho-Corasick est un puissant algorithme de combinaison 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 vérificateurs orthographiques, les filtres anti-spam, les moteurs de recherche, la bioinformatique / recherche de séquence ADN, etc. En fait, certains outils populaires que vous pouvez utiliser tous les jours utilisent cet algorithme dans les coulisses.
La fonction de préfixe de l'algorithme KMP lui-même est un outil intéressant qui réduit la complexité de la correspondance de motif unique au temps linéaire. L'algorithme Aho-Corasick suit une approche similaire et utilise une structure de données trie pour faire de même pour plusieurs modèles.
J'espère que vous avez trouvé ce tutoriel sur l'algorithme Aho-Corasick utile.
