Construcción práctica del autómata Aho‑Corasick para búsqueda de múltiples patrones
El algoritmo Aho‑Corasick convierte un trie en un autómata con enlaces de sufijo y salida, permitiendo detectar simultáneamente todas las ocurrencias de un conjunto de palabras en tiempo lineal.
El artículo expone paso a paso la construcción de un autómata Aho‑Corasick, una técnica clásica de búsqueda de múltiples patrones que se basa en un trie y en dos tipos de enlaces: sufijo y salida.
Tries y enlaces de sufijo
Un trie almacena un conjunto de cadenas compartiendo prefijos comunes. Cada nodo representa la concatenación de las etiquetas de sus aristas. Para que el autómata recupere la coincidencia cuando una transición falla, se añaden enlaces de sufijo. El enlace de un nodo apunta al nodo que representa el prefijo más largo que también sea un sufijo del camino que lleva al nodo. La construcción de estos enlaces se hace en un recorrido BFS: el nodo raíz y sus hijos enlazan a la raíz; para cualquier otro nodo se sigue el enlace de sufijo del padre y se busca una arista con la etiqueta del nodo. Si no existe, se sube siguiendo enlaces de sufijo hasta llegar a la raíz.
Ejemplo práctico: con los patrones item y suits, el nodo que representa suit tiene como enlace de sufijo el nodo que representa it. Así, al escanear la cadena suitems, cuando la transición a e falla, el autómata vuelve al nodo it y continúa, lo que permite detectar item dentro de suitems.
Enlaces de salida
Cuando se inserta un patrón, el último nodo alcanzado se marca como de salida, guardando el patrón. Un nodo puede tener varias coincidencias: además de su patrón propio, puede haber patrones en los nodos que se alcanzan siguiendo enlaces de sufijo. Los enlaces de salida apuntan a esos nodos de salida más cortos, garantizando que todas las coincidencias se reporten en el orden correcto.
En el ejemplo con cadence y facade, el nodo que representa cad enlaza de salida a la raíz (no hay coincidencia), mientras que el nodo que representa faca enlaza a cad, permitiendo reconocer cadence cuando se está leyendo una cadena que contenga faca.
Ventajas y uso
La construcción es lineal en el tamaño total de los patrones y el autómata permite procesar una cadena de longitud m en O(m) tiempo, sin volver a la raíz cada vez que falla una transición. Es la base de herramientas como grep, antivirus y motores de búsqueda de texto.
Referencias
Para profundizar en la teoría original y en la discusión comunitaria, puedes consultar los documentos enlazados.
