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 coincidencia de diccionario que localiza elementos de un conjunto finito de cadenas (el "diccionario") dentro de un texto de entrada. Coincide con 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, se devolverán múltiples coincidencias para una ubicación de cadena si coinciden múltiples subcadenas (por ejemplo, diccionario = a , aa , aaa , aaaa y la cadena de entrada es aaaa ).
De manera informal, el algoritmo construye una máquina de estados finitos que se asemeja a un trie con enlaces adicionales entre los diversos nodos internos. Estos enlaces internos adicionales permiten transiciones rápidas entre coincidencias de cadenas fallidas (por ejemplo, una búsqueda de cart en un trie que no contiene cart , pero sí art , y por lo tanto fallaría en el nodo prefijado por car ), a otras ramas del trie que comparten un sufijo común (por ejemplo, en el caso anterior, una rama para attribute podría ser la mejor transición lateral). Esto permite que el autómata realice 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 que se está fuera de línea y el autómata compilado se puede almacenar 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 Unix original fgrep .
En este ejemplo, consideraremos un diccionario que consta de las siguientes palabras: {a, ab, bab, bc, bca, c, caa}.
El gráfico a continuación es la estructura de datos de Aho–Corasick construida a partir del diccionario especificado, donde cada fila de la tabla representa un nodo en el trie y la ruta de la columna indica 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 del diccionario. Por lo tanto, si (bca) está en el diccionario, habrá nodos para (bca), (bc), (b) y (). Si un nodo está en el diccionario, será un nodo azul. De lo contrario, será un nodo gris.
Hay un arco "hijo" dirigido en negro desde cada nodo hasta un nodo cuyo nombre se encuentra agregando un carácter. Por lo tanto, hay un arco negro desde (bc) hasta (bca).
Hay un arco de "sufijo" dirigido de color azul desde cada nodo hasta el nodo que es el sufijo estricto más largo posible de este en el grafo. Por ejemplo, para el nodo (caa), sus sufijos estrictos son (aa) y (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 amplitud [el nodo de sufijo potencial siempre estará en el nivel inferior] comenzando desde la raíz. El objetivo para el 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 nuevamente 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).
Hay un arco de "sufijo de diccionario" verde desde cada nodo hasta el siguiente nodo del diccionario al que se puede llegar 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 cuando se siguen los arcos azules hasta (ca) y luego hasta (a). Los arcos verdes se pueden calcular en tiempo lineal recorriendo repetidamente los arcos azules hasta que se encuentra un nodo azul y memorizando esta información.
En cada paso, el nodo actual se extiende encontrando su hijo, y si no existe, encontrando el hijo de su sufijo, y si eso no funciona, encontrando el hijo del sufijo de su sufijo, y así sucesivamente, terminando finalmente en el nodo raíz si no se vio nada antes.
Cuando el algoritmo llega a un nodo, genera todas las entradas del 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 vínculos de sufijo del diccionario, comenzando desde ese nodo y continuando hasta llegar a un nodo sin vínculo de sufijo del diccionario. Además, se imprime el nodo mismo, si es una entrada del diccionario.
La ejecución de la cadena de entrada abccab produce los siguientes pasos:
El algoritmo original de Aho-Corasick supone 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 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 la 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. [2]
