Algoritmo de búsqueda de cadenas Aho-Corasick
En Ciencias de la Computación, el Algoritmo de búsqueda de cadenas Aho–Corasick es un algoritmo de búsqueda de cadenas inventado por Alfred V. Aho y Margaret J. Corasick. Es un algoritmo que busca elementos (patrones) de un conjunto finito de cadenas (diccionario) dentro de un texto. Una de las ventajas que presenta es que procesa el texto de entrada solamente una vez, es decir, realiza la búsqueda de todos los patrones de forma simultánea. Si se considera el tamaño del alfabeto al cual pertenecen los patrones como constante, entonces la complejidad temporal del algoritmo es lineal en cuanto a la suma de las longitudes de los patrones más la longitud del texto. Si además se quieren conocer todas las ocurrencias de forma explícita, al orden del algoritmo hay que sumarle la cantidad de ocurrencias. Es necesario destacar que si se buscan todas las ocurrencias, entonces puede haber un número cuadrático de ellas si cada subcadena es una ocurrencia. Por ejemplo si el diccionario es a, aa, aaa, aaaa y la cadena de entrada es aaaa).
Informalmente, el algoritmo construye un autómata finito determinista similar a un trie con enlaces adicionales entre los nodos internos. Estos enlaces extras permiten llevar a cabo transiciones bastante rápidas entre correspondencias fallidas de patrones (ejemplo, una búsqueda para cat en un trie que no contiene a cat, pero contiene cart, y de esta manera fallaría en el nodo prefijado por ca), a otras ramificaciones del trie que comparten prefijos comunes (ejemplo, en el caso anterior, una ramificación para attribute pudiera ser la mejor transición a efectuar). Esto le permite al autómata realizar transiciones entre ocurrencias de patrones sin necesidad de backtracking.
Cuando el diccionario de patrones se conoce de antemano (por ejemplo, en una base de datos de virus), la construcción del autómata se puede llevar a cabo y se guarda el autómata compilado para uso futuro. En este caso, la complejidad temporal es lineal en cuanto a la longitud de la entrada más el número de entradas encontradas.
El gráfico que se muestra a continuación es la estructura Aho-Corasick construida a partir del diccionario especificado, con cada fila en la tabla representando un nodo en el trie, y la columna Camino indicando la (única) secuencia de caracteres desde la raíz del trie al nodo en cuestión.
La estructura de datos tiene un nodo para cada prefijo de cada cadena en el diccionario. De esta manera, si (bca) está en el diccionario, entonces estarán presentes nodos para (bca), (bc), (b) y (). Hay un arco dirigido "hijo" negro desde cada nodo a un nodo cuyo Camino se obtiene añadiendo un carácter. Por lo tanto, hay un arco negro de (bc) a (bca). Hay un arco dirigido "sufijo" de cada nodo al nodo correspondiente a su sufijo propio más largo en el grafo. Por ejemplo, para el nodo (caa), su sufijos propios son (aa), (a) y (). El más largo de estos que existe en el grafo es (a), por lo que hay un arco azul de (caa) a (a). Hay un arco verde "sufijo en diccionario" desde cada nodo al siguiente nodo en el diccionario que puede ser alcanzado siguiendo arcos azules. Por ejemplo, hay un arco verde de (bca) a (a) porque (a) es el primer nodo correspondiente a uno de los patrones en el diccionario (nodo blanco) que se alcanza siguiendo los arcos azules a (ca) y luego a (a).
| Camino | En Diccionario | Enlace sufijo | Enlace sufijo en Dicc |
|---|---|---|---|
| () | - | ||
| (a) | + | () | |
| (ab) | + | (b) | |
| (b) | - | () | |
| (bc) | + | (c) | (c) |
| (bca) | + | (ca) | (a) |
| (c) | + | () | |
| (ca) | - | (a) | (a) |
| (caa) | + | (a) | (a) |
A la hora de encontrar las occurrencias en un texto, en cada paso el nodo actual se extiende encontrando su hijo con el carácter correspondiente, y si no existe, se busca su "hijo sufijo" utilizado en enlace sufijo y se continúa de esta manera hasta encontrar un nodo que tenga una transición con el carácter actual o hasta que se llegue al nodo raíz.
Cuando el algoritmo alcanza un nodo, devuelve todas las entradas en el diccionario que terminan en la posición del carácter actual en el texto de entrada. Esto se hace imprimiendo cada nodo alcanzado siguiendo los "enlaces sufijo en diccionario", comenzando por ese nodo, y continuando hasta alcanzar un nodo que no tenga "enlace sufijo en diccionario".
La ejecución con la cadena de entrada abccab produce los siguientes pasos:
| Nodo | Cadena que queda | Salida: Posición final | Transición | Salida |
|---|---|---|---|---|
| () | abccab | comenzar en la raíz | ||
| (a) | bccab | a:1 | () a hijo (a) | Nodo actual |
| (ab) | ccab | ab:2 | (a) a hijo (ab) | Nodo actual |
| (bc) | cab | bc:3, c:3 | (ab) a sufijo (b) a hijo (bc) | Nodo actual, Enlace sufijo en dicc |
| (c) | ab | c:4 | (bc) a sufijo (c) a sufijo () a hijo (c) | Nodo actual |
| (ca) | b | a:5 | (c) a hijo (ca) | Nodo sufijo en dicc |
| (ab) | ab:6 | (ca) a sufijo (a) a hijo (ab) | Nodo actual |
Referencias editar
- Aho, Alfred V.; Corasick, Margaret J. (junio de 1975). «Efficient string matching: An aid to bibliographic search». Communications of the ACM 18 (6): 333-340. doi:10.1145/360825.360855. (El acceso al texto completo puede estar restringido.)
Enlaces externos editar
- Set Matching and Aho–Corasick Algorithm, Conferencia en diapositivas por Pekka Kilpeläinen
- Entrada Aho–Corasick entry en el Diccionario de estructuras de datos y algoritmos de NIST
- Aho–Corasick string matching in C# Archivado el 15 de enero de 2012 en Wayback Machine., un tutorial en CodeProject escrito por Tomáš Petříček
- Aho-Corasick C implementation, bueno para patrones de longitud pequeña.
- Explicación del Aho-Corasick usando Python Archivado el 13 de diciembre de 2013 en Wayback Machine.
- Implementación del Aho-Corasick en Java
- Animated Aho-Corasick, Una implementación animada del Aho-Corasick con propósitos académicos
- Aho-Corasick C++ implementation, Esta librería en C++ también implementa otros algoritmos relacionados
Datos: Q402342
Multimedia: Aho–Corasick algorithm / Q402342
