En informática , el algoritmo Aho-Corasick es un algoritmo de búsqueda de cadenas inventado por Alfred V. Aho y Margaret J. Corasick. [1] Es una especie de algoritmo de búsqueda de diccionario que ubica elementos de un conjunto finito de cadenas (el "diccionario") dentro de un texto de entrada. Coincide con todas las cadenas de forma simultánea. 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 cada subcadena coincide (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 gato en un trie que no contiene cat , pero contiene carro y, por lo tanto, fallaría en el nodo con el prefijo ca ), a otras ramas del trie que comparten un prefijo 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 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 puede realizarse una vez fuera de línea y el autómata compilado puede almacenarse 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 de Aho-Corasick formó la base del comando original de Unix fgrep .
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 del diccionario. Entonces, si (bca) está en el diccionario, entonces 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 arco "hijo" dirigido en negro desde cada nodo a un nodo cuyo nombre se encuentra agregando un carácter. Entonces hay un arco negro de (bc) a (bca).
Hay un arco de "sufijo" dirigido en azul 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). Entonces hay un arco azul de (caa) a (a). Los arcos azules se pueden calcular en tiempo lineal realizando una búsqueda de amplitud primero [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 personaje no existe cuando era niño, podemos buscar 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 arco verde de "sufijo de diccionario" desde cada nodo hasta el 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 hasta (ca) y luego a ( a). Los arcos verdes se pueden calcular en tiempo lineal atravesando repetidamente los arcos azules hasta que se encuentre un nodo azul y memorizando esta información.
Camino | En diccionario | Enlace de sufijo | Vínculo de sufijo Dict |
---|---|---|---|
() | - | ||
(a) | + | () | |
(ab) | + | (B) | |
(B) | - | () | |
(licenciado en Letras) | - | (a) | (a) |
(bab) | + | (ab) | (ab) |
(antes de Cristo) | + | (C) | (C) |
(bca) | + | (California) | (a) |
(C) | + | () | |
(California) | - | (a) | (a) |
(caa) | + | (a) | (a) |
En cada paso, el nodo actual se extiende encontrando su hijo, y si ese no existe, encontrando el hijo de su sufijo, y si eso no funciona, encontrando el hijo del sufijo de su sufijo, y así sucesivamente, finalmente terminando en la raíz. nodo si no se ha visto nada antes.
Cuando el algoritmo llega a un nodo, genera todas las entradas del diccionario que terminan en la posición actual del carácter en el texto de entrada. Esto se hace imprimiendo cada nodo alcanzado siguiendo los enlaces de sufijo de diccionario, comenzando desde ese nodo y continuando hasta llegar a un nodo sin enlace de sufijo de diccionario. Además, se imprime el nodo en sí, si es una entrada de diccionario.
Ejecución en cadena de entrada abccab produce los siguientes pasos:
Nodo | Cadena restante | Salida: posición final | Transición | Producción |
---|---|---|---|---|
() | abccab | empezar en la raíz | ||
(a) | bccab | a: 1 | () al niño (a) | Nodo actual |
(ab) | ccab | ab: 2 | (a) a niño (ab) | Nodo actual |
(antes de Cristo) | taxi | antes de Cristo: 3, c: 3 | (ab) al sufijo (b) al niño (bc) | Nodo actual, nodo de sufijo Dict |
(C) | ab | c: 4 | (bc) al sufijo (c) al sufijo () al niño (c) | Nodo actual |
(California) | B | a: 5 | (c) a niño (ca) | Nodo de sufijo Dict |
(ab) | ab: 6 | (ca) al sufijo (a) al niño (ab) | Nodo actual |
Lista de búsqueda dinámica
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 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 revisa 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 extender de forma incremental durante la búsqueda, conservando la complejidad algorítmica del original. [2]
Ver también
Referencias
- ^ Aho, Alfred V .; Corasick, Margaret J. (junio de 1975). "Coincidencia de cadenas eficiente: una ayuda para la búsqueda bibliográfica". Comunicaciones de la ACM . 18 (6): 333–340. doi : 10.1145 / 360825.360855 . Señor 0371172 .
- ^ Meyer, Bertrand (1985). "Coincidencia incremental de cadenas" (PDF) . Cartas de procesamiento de información . 21 : 219-227. doi : 10.1016 / 0020-0190 (85) 90088-2 .
enlaces externos
- Aho-Corasick en el Diccionario de algoritmos y estructuras de datos del NIST (2019-07-15)
- Visualización Aho-Corasick
- Implementación de Aho-Corasick (C ++) en GitHub
- Una implementación de Golang del algoritmo de coincidencia de cadenas Aho-Corasick en GitHub
- Una implementación rápida de Aho-Corasick en Rust en GitHub