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).

Diccionario {a, ab, bc, bca, c, caa}
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:


Análisis de la cadena abccab
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

  • 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