Conquiste la búsqueda de cadenas con el algoritmo Aho-Corasick

Manipular cadenas y buscar patrones en ellas son tareas fundamentales en ciencia de datos, y una tarea típica para cualquier programador.

Los algoritmos de cadena eficientes juegan un papel importante en muchos procesos de ciencia de datos. A menudo son los que hacen que tales procesos sean lo suficientemente viables para su uso práctico.

En este artículo, aprenderá sobre uno de los algoritmos más poderosos para buscar patrones en una gran cantidad de texto: el algoritmo Aho-Corasick. Este algoritmo utiliza una estructura de datos trie (pronunciado "try") para realizar un seguimiento de los patrones de búsqueda y utiliza un método simple para encontrar de manera eficiente todas las apariciones de un conjunto determinado de patrones en cualquier blob de texto.

Un artículo anterior en el blog de ingeniería de Toptal demostró un algoritmo de búsqueda de cadenas para el mismo problema. El enfoque adoptado en este artículo ofrece una mayor complejidad computacional.

El algoritmo Knuth-Morris-Pratt (KMP)

Para comprender cómo podemos buscar múltiples patrones en un texto de manera eficiente, primero debemos abordar un problema más fácil: buscar un solo patrón en un texto determinado.

Supongamos que tenemos una gran cantidad de texto de longitud N y un patrón (que queremos buscar en el texto) de longitud M. Ya sea que queramos buscar una sola ocurrencia de este patrón, o todas las ocurrencias, podemos lograr una complejidad computacional de O(N + M) usando el algoritmo KMP.

Función de prefijo

El algoritmo KMP funciona calculando una función de prefijo del patrón que estamos buscando. La función de prefijo calcula previamente una posición de reserva para cada prefijo del patrón.

Definamos nuestro patrón de búsqueda como una cadena, etiquetada como S . Para cada subcadena S[0..i] , donde i >= 1 , encontraremos el prefijo máximo de esta cadena que también resulta ser el sufijo de esta cadena. Etiquetaremos la longitud de este prefijo P[i] .

Para el patrón "abracadabra", la función de prefijo produciría las siguientes posiciones alternativas:

La función de prefijo identifica una característica interesante del patrón.

Tomemos un prefijo particular del patrón como ejemplo: "abracadab". El valor de la función de prefijo para este prefijo es dos. Esto indica que para este prefijo “abracadab”, existe un sufijo de longitud dos que coincide exactamente con el prefijo de longitud dos (es decir, el patrón comienza con “ab” y el prefijo termina con “ab”). Además, esto es la coincidencia más larga para este prefijo.

Implementación

Aquí hay una función de C# que se puede usar para calcular la función de prefijo para cualquier cadena:

 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; }

Ejecutar esta función en un patrón un poco más largo "abcdabcabcdabcdab" produce esto:

Complejidad computacional

A pesar de que hay dos bucles anidados, la complejidad de la función de prefijo es solo O(M) , donde M es la longitud del patrón S.

Esto se puede explicar fácilmente observando cómo funcionan los bucles.

Todas las iteraciones de bucle externo a través de i se pueden dividir en tres casos:

1. Aumenta k en uno. El ciclo completa una iteración.

2. No cambia el valor cero de k . El ciclo completa una iteración.

3. No cambia o disminuye un valor positivo de k .

Los dos primeros casos pueden ejecutarse como máximo M veces.

Para el tercer caso, definamos P(s, i) = k1 y P(s, i + 1) = k2, k2 <= k1 . Cada uno de estos casos debe estar precedido por k1 - k2 ocurrencias del primer caso. El conteo de disminuciones no excede k1 - k2 + 1 . Y en total no tenemos más de 2*M de iteraciones.

Explicación del segundo ejemplo

Veamos el segundo patrón de ejemplo “abcdabcabcdabcdab”. Así es como la función de prefijo lo procesa, paso a paso:

1. Para una subcadena vacía y la subcadena "a" de longitud uno, el valor de la función de prefijo se establece en cero. ( k = 0 )

2. Mira la subcadena "ab". El valor actual de k es cero y el carácter "b" no es igual al carácter "a". Aquí tenemos el segundo caso del apartado anterior. El valor de k permanece en cero y el valor de la función de prefijo para la subcadena "ab" también es cero.

3. Es el mismo caso para las subcadenas "abc" y "abcd". No hay prefijos que sean también los sufijos de estas subcadenas. El valor para ellos se mantiene en cero.

4. Ahora veamos un caso interesante, la subcadena "abcda". El valor actual de k sigue siendo cero, pero el último carácter de nuestra subcadena coincide con su primer carácter. Esto desencadena la condición de s[k] == s[i] , donde k == 0 y i == 4 . La matriz tiene un índice cero y k es el índice del siguiente carácter para el prefijo de longitud máxima. Esto significa que hemos encontrado el prefijo de longitud máxima para nuestra subcadena que también es un sufijo. Tenemos el primer caso, donde el nuevo valor de k es uno, y por tanto el valor de la función de prefijo P(“abcda”) es uno.

5. El mismo caso también ocurre para las siguientes dos subcadenas, P(“abcdab”) = 2 y P(“abcdabc”) = 3 . Aquí, estamos buscando nuestro patrón en el texto, comparando cadenas carácter por carácter. Digamos que los primeros siete caracteres del patrón coincidieron con unos siete caracteres consecutivos de texto procesado, pero en el octavo carácter no coincide. ¿Qué debería pasar después? En el caso de coincidencia de cadenas ingenuas, debemos devolver siete caracteres y comenzar el proceso de comparación nuevamente desde el primer carácter de nuestro patrón. Con el valor de la función de prefijo (aquí P(“abcdabc”) = 3 ) sabemos que nuestro sufijo de tres caracteres ya coincide con tres caracteres de texto. Y si el siguiente carácter en el texto es "d", la longitud de la subcadena coincidente de nuestro patrón y la subcadena en el texto aumenta a cuatro ("abcd"). De lo contrario, P(“abc”) = 0 y comenzaremos el proceso de comparación desde el primer carácter del patrón. Pero lo importante es que no volvemos durante el procesamiento del texto.

6. La siguiente subcadena es "abcdabca". En la subcadena anterior, la función de prefijo era igual a tres. Esto significa que k = 3 es mayor que cero, y al mismo tiempo tenemos una discrepancia entre el siguiente carácter del prefijo ( s[k] = s[3] = "d" ) y el siguiente carácter del sufijo ( s[i] = s[7] = "a" ). Esto significa que activamos la condición de s[k] != s[i] , y que el prefijo “abcd” no puede ser el sufijo de nuestra cadena. Deberíamos disminuir el valor de k y tomar el prefijo anterior para comparar, cuando sea posible. Como describimos anteriormente, la matriz tiene un índice cero y k es el índice del siguiente carácter que verificamos del prefijo. El último índice del prefijo coincidente actualmente es k - 1 . Tomamos el valor de la función de prefijo para el prefijo actualmente coincidente k = result[k - 1] . En nuestro caso (el tercer caso) la longitud del prefijo máximo se reducirá a cero y luego en la siguiente línea se aumentará a uno, porque “a” es el prefijo máximo que también es el sufijo de nuestra subcadena.

7. (Aquí continuamos nuestro proceso de cálculo hasta llegar a un caso más interesante).

8. Comenzamos a procesar la siguiente subcadena: “abcdabcabcdabcd”. El valor actual de k es siete. Al igual que con "abcdabca" arriba, encontramos una no coincidencia: debido a que el carácter "a" (el séptimo carácter) no es igual al carácter "d", la subcadena "abcdabca" no puede ser el sufijo de nuestra cadena. Ahora obtenemos el valor ya calculado de la función de prefijo para "abcdabc" (tres) y ahora tenemos una coincidencia: el prefijo "abcd" también es el sufijo de nuestra cadena. Su prefijo máximo y el valor de la función de prefijo para nuestra subcadena es cuatro, porque ese es el valor actual de k .

9. Continuamos este proceso hasta el final del patrón.

En resumen: ambos ciclos no requieren más de 3 M de iteraciones, lo que demuestra que la complejidad es O(M). El uso de memoria también es O(M).

Implementación del algoritmo 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; }

El algoritmo anterior itera a través del texto, carácter por carácter, e intenta aumentar el prefijo máximo tanto para nuestro patrón como para algunas secuencias de caracteres consecutivos en el texto. En caso de falla, no regresaremos a nuestra posición anterior en el texto. Conocemos el prefijo máximo de la subcadena encontrada del patrón; este prefijo es también el sufijo de esta subcadena encontrada y simplemente podemos continuar la búsqueda.

La complejidad de esta función es la misma que la de la función de prefijo, lo que hace que la complejidad computacional general sea O(N + M) con memoria O(M) .

Trivia: Los métodos String.IndexOf() y String.Contains() en el marco .NET tienen un algoritmo con la misma complejidad bajo el capó.

El algoritmo de Aho-Corasick

Ahora queremos hacer lo mismo para múltiples patrones.

Supongamos que hay M patrones de longitudes L1 , L2 , …, Lm . Necesitamos encontrar todas las coincidencias de patrones de un diccionario en un texto de longitud N .

Una solución trivial sería tomar cualquier algoritmo de la primera parte y ejecutarlo M veces. Tenemos una complejidad de O(N + L1 + N + L2 + … + N + Lm) , es decir, O(M * N + L) .

Cualquier prueba lo suficientemente seria mata este algoritmo.

Tomar un diccionario con las 1,000 palabras en inglés más comunes como patrones y usarlo para buscar la versión en inglés de “Guerra y paz” de Tolstoi llevaría bastante tiempo. El libro tiene más de tres millones de caracteres.

Si tomamos las 10.000 palabras en inglés más comunes, el algoritmo funcionará unas 10 veces más lento. Obviamente, en entradas mayores que esta, el tiempo de ejecución también crecerá.

Aquí es donde el algoritmo Aho-Corasick hace su magia.

La complejidad del algoritmo de Aho-Corasick es O(N + L + Z) , donde Z es el recuento de coincidencias. Este algoritmo fue inventado por Alfred V. Aho y Margaret J. Corasick en 1975.

Implementación

Aquí, necesitamos un intento, y agregamos a nuestro algoritmo una idea similar a las funciones de prefijo descritas anteriormente. Calcularemos los valores de la función de prefijo para todo el diccionario.

Cada vértice en el trie almacenará la siguiente información:

 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; }

Hay varias formas de implementar enlaces secundarios. El algoritmo tendrá una complejidad de O(N + L + Z) en el caso de un arreglo, pero este tendrá un requerimiento de memoria adicional de O(L * q) , donde q es la longitud del alfabeto, ya que eso es el número máximo de hijos que puede tener un nodo.

Si usamos alguna estructura con acceso O(log(q)) a sus elementos, tenemos un requisito de memoria adicional de O(L) , pero la complejidad de todo el algoritmo será O((N + L) * log(q) +Z) .

En el caso de una tabla hash, tenemos memoria adicional O(L) , y la complejidad de todo el algoritmo será O(N + L + Z) .

Este tutorial utiliza una tabla hash porque también funcionará con diferentes conjuntos de caracteres, por ejemplo, caracteres chinos.

Ya tenemos una estructura para un vértice. A continuación, definiremos una lista de vértices e inicializaremos el nodo raíz del 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++; } }

Luego agregamos todos los patrones al trie. Para esto, necesitamos un método para agregar palabras al 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); }

En este punto, todas las palabras de patrón están en la estructura de datos. Esto requiere una memoria adicional de O(L) .

A continuación, debemos calcular todos los enlaces de sufijo y enlaces de entrada de diccionario.

Para que sea claro y fácil de entender, recorreré nuestro trie desde la raíz hasta las hojas y haré cálculos similares a los que hicimos para el algoritmo KMP, pero en contraste con el algoritmo KMP, donde encontramos la longitud máxima prefijo que también era el sufijo de la misma subcadena, ahora encontraremos el sufijo de longitud máxima de la subcadena actual que también es el prefijo de algún patrón en el trie. El valor de esta función no será la longitud del sufijo encontrado; será el enlace al último carácter del sufijo máximo de la subcadena actual. Esto es lo que quiero decir con el enlace de sufijo de un vértice.

Procesaré los vértices por niveles. Para eso, usaré un algoritmo de búsqueda primero en amplitud (BFS):

Y a continuación se muestra la implementación de este recorrido:

 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]); } } }

Y debajo está el método CalcSuffLink para calcular el enlace del sufijo para cada vértice (es decir, el valor de la función del prefijo para cada subcadena en el 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 complejidad de este método es O(L) ; dependiendo de la implementación de la colección secundaria, la complejidad podría ser O(L * log(q)) .

La prueba de complejidad es similar a la función de prefijo de prueba de complejidad en el algoritmo KMP.

Miremos la siguiente imagen. Esta es una visualización del trie para el diccionario { abba, cab, baba, caab, ac, abac, bac } con toda su información calculada:

Los bordes de Trie son de color azul oscuro, los enlaces de sufijo son de color azul claro y los enlaces de sufijo de diccionario son de color verde. Los nodos correspondientes a las entradas del diccionario están resaltados en azul.

Y ahora solo necesitamos un método más: procesar un bloque de texto en el que pretendemos buscar:

 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; }

Y, ahora esto está listo para usar:

En la entrada, tenemos una lista de patrones:

 List<string> patterns;

Y texto de búsqueda:

 string text;

Y aquí está cómo pegarlo:

 // 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);

¡Y eso es! ¡Ahora sabe cómo funciona este algoritmo simple pero poderoso!

Aho-Corasick es realmente flexible. Los patrones de búsqueda no tienen que ser solo palabras, sino que podemos usar oraciones completas o cadenas aleatorias de caracteres.

Rendimiento

El algoritmo se probó en un procesador Intel Core i7-4702MQ.

Para las pruebas, tomé dos diccionarios: Las 1,000 palabras en inglés más comunes y las 10,000 palabras en inglés más comunes.

Para agregar todas estas palabras al diccionario y preparar la estructura de datos para trabajar con cada uno de los diccionarios, el algoritmo requirió 55ms y 135ms respectivamente.

El algoritmo procesó libros reales de 3 a 4 millones de caracteres en 1,0 a 1,3 segundos, mientras que un libro con alrededor de 30 millones de caracteres tardó 9,6 segundos.

Paralelización del algoritmo de Aho-Corasick

Ir en paralelo con el algoritmo Aho-Corasick no es un problema en absoluto:

Un texto grande se puede dividir en varios fragmentos y se pueden utilizar varios subprocesos para procesar cada fragmento. Cada hilo tiene acceso al trie generado basado en el diccionario.

¿Qué pasa con las palabras que se dividen en el límite entre fragmentos? Este problema se puede resolver fácilmente.

Sea N la longitud de nuestro texto grande, S el tamaño de un fragmento y L la longitud del patrón más grande del diccionario.

Ahora podemos usar un truco simple. Dividimos fragmentos con cierta superposición al final, por ejemplo, tomando [S * (i - 1), S * i + L - 1] , donde i es el índice del fragmento. Cuando obtenemos una coincidencia de patrón, podemos obtener fácilmente el índice de inicio de la coincidencia actual y simplemente verificar que este índice esté dentro del rango de fragmentos sin superposiciones, [S * (i - 1), S * i - 1] .

Un algoritmo de búsqueda de cadenas versátil

El algoritmo Aho-Corasick es un poderoso algoritmo de coincidencia de cadenas que ofrece la mejor complejidad para cualquier entrada y no requiere mucha memoria adicional.

El algoritmo se usa a menudo en varios sistemas, como correctores ortográficos, filtros de spam, motores de búsqueda, bioinformática/búsqueda de secuencias de ADN, etc. De hecho, algunas herramientas populares que puede estar usando todos los días están usando este algoritmo detrás de escena.

La función de prefijo del algoritmo KMP en sí misma es una herramienta interesante que reduce la complejidad de la coincidencia de patrones únicos al tiempo lineal. El algoritmo de Aho-Corasick sigue un enfoque similar y utiliza una estructura de datos trie para hacer lo mismo con varios patrones.

Espero que hayas encontrado útil este tutorial sobre el algoritmo Aho-Corasick.