Algoritmo de Aho-Corasick

En informática, el algoritmo Aho-Corasick es un algoritmo de búsqueda de cadenas inventado por Alfred V. Aho y Margaret J. Corasick en 1975. Es una especie de algoritmo de comparación de diccionarios que localiza elementos de un conjunto finito de cadenas (el "diccionario") dentro de un texto de entrada. Hace coincidir todas las cadenas simultáneamente. La complejidad del algoritmo es lineal en la longitud de las cadenas más la longitud del texto buscado más el número de coincidencias de salida. Tenga en cuenta que debido a que se encuentran todas las coincidencias, puede haber un número cuadrático de coincidencias si todas las subcadenas coinciden (por ejemplo, diccionario = a, aa, aaa, aaaa y la cadena de entrada es aaaa).

De manera informal, el algoritmo construye una máquina de estado finito que se parece a un trie con enlaces adicionales entre los distintos nodos internos. Estos enlaces internos adicionales permiten transiciones rápidas entre coincidencias de cadenas fallidas (por ejemplo, una búsqueda de gato en un trie que no contiene gato, pero contiene cart, y por lo tanto fallaría en el nodo con el prefijo ca), a otras ramas del trie que comparten un común prefijo (por ejemplo, en el caso anterior, una rama para atributo podría ser la mejor transición lateral). Esto permite que el autómata haga la transición entre coincidencias de cadenas sin necesidad de retroceder.

Cuando el diccionario de cadenas se conoce de antemano (por ejemplo, una base de datos de virus informáticos), la construcción del autómata se puede realizar una vez fuera de línea y el autómata compilado se almacena para su uso posterior. En este caso, su tiempo de ejecución es lineal en la longitud de la entrada más el número de entradas coincidentes.

El algoritmo de coincidencia de cadenas Aho-Corasick formó la base del comando fgrep original de Unix.

Ejemplo

En este ejemplo, consideraremos un diccionario que consta de las siguientes palabras: {a, ab, bab, bc, bca, c, caa}.

El siguiente gráfico es la estructura de datos Aho-Corasick construida a partir del diccionario especificado, con cada fila de la tabla representando un nodo en el trie, con la ruta de la columna indicando la secuencia (única) de caracteres desde la raíz hasta el nodo.

La estructura de datos tiene un nodo para cada prefijo de cada cadena en el diccionario. Entonces, si (bca) está en el diccionario, habrá nodos para (bca), (bc), (b) y (). Si un nodo está en el diccionario, entonces es un nodo azul. De lo contrario, es un nodo gris.

Hay un "niño" dirigido por negros. arco de cada nodo a un nodo cuyo nombre se encuentra agregando un carácter. Entonces hay un arco negro de (bc) a (bca).

Hay un "sufijo" arco desde cada nodo hasta el nodo que es el sufijo estricto más largo posible en el gráfico. Por ejemplo, para el nodo (caa), sus sufijos estrictos son (aa) y (a) y (). El más largo de estos que existe en el gráfico es (a). Así que hay un arco azul de (caa) a (a). Los arcos azules se pueden calcular en tiempo lineal realizando una búsqueda en anchura [el nodo de sufijo potencial siempre estará en el nivel inferior] comenzando desde la raíz. El destino del arco azul de un nodo visitado se puede encontrar siguiendo el arco azul de su padre hasta el nodo de sufijo más largo y buscando un hijo del nodo de sufijo cuyo carácter coincida con el del nodo visitado. Si el personaje no existe como hijo, podemos encontrar el siguiente sufijo más largo (siguiendo el arco azul nuevamente) y luego buscar el personaje. Podemos hacer esto hasta que encontremos el carácter (como hijo de un nodo) o lleguemos a la raíz (que siempre será un sufijo de cada cadena).

Hay un "sufijo de diccionario" arco de cada nodo al siguiente nodo en el diccionario al que se puede llegar siguiendo los arcos azules. Por ejemplo, hay un arco verde de (bca) a (a) porque (a) es el primer nodo en el diccionario (es decir, un nodo azul) que se alcanza al seguir los arcos azules a (ca) y luego a (a). Los arcos verdes se pueden calcular en tiempo lineal recorriendo repetidamente los arcos azules hasta encontrar un nodo azul y memorizando esta información.

Una visualización del trie para el diccionario a la derecha. Suffix links están en azul; diccionario sufijo enlaces en verde. Los nodos correspondientes a las entradas del diccionario se destacan en azul.

En cada paso, el nodo actual se amplía encontrando su hijo, y si eso no existe, encontrando su hijo del sufijo, y si que no funciona, encontrando su hijo de sufijo, y así sucesivamente, finalmente terminando en el nodo raíz si no se ha visto nada antes.

Cuando el algoritmo llega a un nodo, genera todo el diccionario entradas que terminan en la posición actual del carácter en el texto de entrada. Esto esta hecho imprimiendo cada nodo alcanzado siguiendo los enlaces de sufijos del diccionario, comenzando desde ese nodo, y continúa hasta que llega a un nodo sin enlace de sufijo de diccionario. Además, se imprime el propio nodo, si es una entrada de diccionario.

La ejecución en la cadena de entrada abccab produce los siguientes pasos:

Lista de búsqueda dinámica

El algoritmo Aho-Corasick original asume que el conjunto de cadenas de búsqueda es fijo. No se aplica directamente a las aplicaciones en las que se agregan nuevas cadenas de búsqueda durante la aplicación del algoritmo. Un ejemplo es un programa de indexación interactivo, en el que el usuario recorre el texto y resalta nuevas palabras o frases para indexar a medida que las ve. Bertrand Meyer introdujo una versión incremental del algoritmo en el que el conjunto de cadenas de búsqueda se puede ampliar de forma incremental durante la búsqueda, conservando la complejidad algorítmica del original.