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. ^{[ 1 ]} Es un tipo de algoritmo de comparación de diccionarios que localiza elementos de un conjunto finito de cadenas (el "diccionario") dentro de un texto de entrada. Compara 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. Debido a que se encuentran todas las coincidencias, se devolverán múltiples coincidencias para una posición de cadena si varias cadenas del diccionario coinciden en esa posición (por ejemplo, diccionario = a , aa , aaa , aaaa y la cadena de entrada es aaaa ).

De manera informal, el algoritmo crea un trie utilizando las cadenas del diccionario y luego construye una máquina de estados finitos a partir del trie agregando enlaces adicionales entre los nodos. Estos enlaces adicionales permiten transiciones rápidas entre coincidencias de cadenas fallidas (por ejemplo, una búsqueda de " carrito" en un trie que no contiene "carrito" , pero sí "arte" , y que por lo tanto fallaría en el nodo con el prefijo " car "), hacia otras ramas del trie que comparten un sufijo común (por ejemplo, en el caso anterior, una rama para "atributo" podría ser la mejor transición lateral). Esto permite que el autómata transite entre coincidencias de cadenas sin necesidad de retroceso.

Cuando se conoce de antemano el diccionario de cadenas (por ejemplo, una base de datos de virus informáticos ), la construcción del autómata puede realizarse una sola vez sin conexión y el autómata compilado puede almacenarse para su uso posterior. En este caso, su tiempo de ejecución es lineal con respecto a la longitud de la entrada más el número de entradas coincidentes.

El algoritmo de búsqueda de cadenas de Aho-Corasick constituyó la base del comando original de Unix, fgrep .

Al igual que muchos inventos en Bell Labs en ese momento, el algoritmo Aho-Corasick se creó de forma fortuita a partir de una conversación entre ambos después de un seminario impartido por Aho. Corasick era una científica de la información que había obtenido su doctorado un año antes en la Universidad de Lehigh . Allí, realizó su disertación sobre la seguridad de los datos propietarios dentro de sistemas abiertos, desde la perspectiva de las estructuras comerciales, legales y gubernamentales, así como de las herramientas técnicas que estaban surgiendo en ese momento. ^{[ 2 ]} En un ámbito similar, en Bell Labs , estaba desarrollando una herramienta para que los investigadores pudieran conocer el trabajo actual que realizaban los contratistas gubernamentales mediante la búsqueda en cintas de publicaciones proporcionadas por el gobierno.

Ella había escrito un programa de búsqueda primitivo, palabra por palabra, para encontrar las palabras clave seleccionadas dentro de las cintas, pero su rendimiento era deficiente con muchas palabras clave; uno de los bibliógrafos que utilizó su algoritmo alcanzó el límite de uso de 600 dólares en las máquinas de Bell Labs antes de que terminara su búsqueda.

Finalmente, asistió a un seminario sobre diseño de algoritmos impartido por Aho, y después hablaron sobre su trabajo y este problema. Aho sugirió mejorar la eficiencia del programa utilizando el enfoque del algoritmo Aho-Corasick, y Corasick diseñó un programa basado en esas ideas. Esto redujo el costo de ejecución de la búsqueda de ese bibliógrafo de más de 600 dólares a tan solo 25 dólares. ^{[ 3 ]}

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

El gráfico que se muestra a continuación representa la estructura de datos Aho-Corasick construida a partir del diccionario especificado, donde cada fila de la tabla representa un nodo en el trie, y la columna "path" indica la secuencia (única) de caracteres desde la raíz hasta el nodo.

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

Existe un arco negro dirigido "hijo" desde cada nodo hasta un nodo cuyo nombre se obtiene añadiendo un carácter. Por lo tanto, hay un arco negro desde (bc) hasta (bca).

Existe un arco azul dirigido de "sufijo" desde cada nodo hasta el nodo que es el sufijo estricto más largo posible en el grafo. Por ejemplo, para el nodo (caa), sus sufijos estrictos son (aa), (a) y (). El más largo de estos que existe en el grafo es (a). Por lo tanto, hay un arco azul desde (caa) hasta (a). Los arcos azules se pueden calcular en tiempo lineal realizando una búsqueda en anchura [el nodo de sufijo potencial siempre estará en un 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 su 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 carácter no existe como hijo, podemos encontrar el siguiente sufijo más largo (siguiendo de nuevo el arco azul) y luego buscar el carácter. 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).

Existe un arco verde, denominado "sufijo del diccionario", que conecta cada nodo con el siguiente nodo del diccionario, al cual se puede acceder siguiendo los arcos azules. Por ejemplo, hay un arco verde desde (bca) hasta (a) porque (a) es el primer nodo del diccionario (es decir, un nodo azul) al que se llega siguiendo los arcos azules hasta (ca) y luego hasta (a). Los arcos verdes se pueden calcular en tiempo lineal recorriendo repetidamente los arcos azules hasta encontrar un nodo azul y almacenando esta información en la memoria.

En cada paso, el nodo actual se extiende buscando a su hijo, y si este no existe, buscando al hijo de su sufijo, y si eso no funciona, buscando al hijo del sufijo de su sufijo, y así sucesivamente, terminando finalmente en el nodo raíz si no se ha encontrado nada antes.

Cuando el algoritmo llega a un nodo, imprime todas las entradas del diccionario que terminan en la posición del carácter actual en el texto de entrada. Esto se logra imprimiendo cada nodo alcanzado siguiendo los enlaces de sufijo del diccionario, comenzando desde ese nodo y continuando hasta llegar a un nodo sin enlace de sufijo. Además, se imprime el nodo en sí, si se trata de una entrada del diccionario.

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

El algoritmo original de Aho-Corasick asume que el conjunto de cadenas de búsqueda es fijo. No se aplica directamente a aplicaciones en las que se añaden nuevas cadenas de búsqueda durante la ejecución del algoritmo. Un ejemplo es un programa de indexación interactiva, en el que el usuario recorre el texto y resalta las nuevas palabras o frases que desea indexar a medida que las encuentra. Bertrand Meyer introdujo una versión incremental del algoritmo en la que el conjunto de cadenas de búsqueda se puede ampliar incrementalmente durante la búsqueda, manteniendo la complejidad algorítmica del original. ^{[ 4 ]}

• Algoritmo Commentz-Walter

• Aho—Corasick en el Diccionario de algoritmos y estructuras de datos del NIST (15 de julio de 2019)